Обратная польская строка (ОПС)
Рассмотрим теперь реализацию всего вышеперечисленного в трансляторах.
Лукашевич предложил:
· Инфиксная форма (стандартная)
· Префиксная (прямая)
· Постфиксная (обратная) запись выражений
Займемся постфиксной формой.
ОПС определяется рекурсивно таким образом:
Если операция бинарная, т.е. требует 2 операнда, то пишется 1й операнд, второй, операция. В унарных операциях: операнд, операция. В ОПС унарный и бинарный минусы – разные знаки. Скобки не требуются. Любой операнд может быть результатом другой операции. Поэтому можно записывать сколь угодно сложные логические выражения.
(a+b)*(c-d)-d*x = ab+cd-* dx*- (1)
Разность между унарным и бинарным минусом:
-x +b в обычной форме
x-‘b+ унарный минус
Присваивание – для переменной икс задать новое значение, т.е. первый операнд – не само значение, а переменная.
Как вычислять выражение, записанное в виде обратной польской строки?
Простота вычисления выражений объясняет то, почему ОПС является универсальным промежуточным языком.
|
|
Алгоритм:
В алгоритме используется стек, куда записываются значения операндов и результаты операций. ОПС просматривается слева-направо.
Если очередной просматриваемый элемент ОПС – операнд, то его значение записывается в стек. Если же очередной элемент ОПС – операция, то она исполняется над верхними элементами стека. Из стека эти переменные удаляются, результат операции записывается в стек.
Выражение (1):
Стек: a, b после «+» становится a+b, c,d после «–» становится a+b, c-d после «*» становится ()*(), d,x после «*» становится ()*(), d*x после «–» получаем результат
Если бы мы хотели присвоить результат y, то записали бы так
y ab+cd-* dx*-:=
и после выполнения стек бы очистился.
Чтобы получить ОПС, нужно дополнить синтаксический анализатор семантическими программами.
Пусть у нас есть построенный по заданной грамматике анализатор LL(1) (по грамматике простых алгебраических выражений). Его нужно дополнить такими семантическими программами, чтобы на выходе выдавалась ОПС, соответствующая входному значению.
S0→(S)F’T’_|_ | aF’T’ _|_
S→(S) F’T’ | a F’T’
T’→λ|+TT’
T→ (S)F’|aF’
F’→ λ|*FF’
F→(S)|a
Грамматика, преобразованная к нормальной форме Грейбах.
Для семантических программ для каждой ячейки стека создадим ячейку в дополнительном стеке. Для каждой правой части снизу дорисуем такие элементы, которые будут заноситься во второй стек.
S0→(S)F’T’_|_ | aa F’T’ _|_
S→(S) F’T’ | aa F’T’
T’→λ|+TT’+
T→ (S)F’|aa F’
F’→ λ|*FF’*
F→(S)|aa
Когда мы удаляем какой-то элемент из стека и если в дополнительном стеке соответствующий элемент, записываем его в выходную ОПС.
|
|
a1+a2*(a3+a4) ^
доп стек: | стек: S0 | |
доп стек: а Доп стек: | стек: ^, T’, F’, a1 стек: ^, T’, F’ | ОПС: а1 |
Доп стек: | стек: ^, T’ | |
Доп стек:,, + | стек: ^, T’, T’, T, + | |
Доп стек:,, + | стек: ^, T’, T’, T | |
Доп стек:,, +,, a2 | стек: ^, T’, T’, F’, a | |
Доп стек:,, +, | стек: ^, T’, T’, F’, | ОПС: a1, a2 |
Доп стек:,, +, * | стек: ^, T’, T’, F’, F, * | |
Доп стек:,, +, * | стек: ^, T’, T’, F’,), S, ( | |
Доп стек:,, +, * | стек: ^, T’, T’, F’,), S | |
Доп стек:,, +, *,,,, a3 | стек: ^, T’, T’, F’,), T’, F’, a | |
Доп стек:,, +, *, | стек: ^, T’, T’, F’,), T’, F’ | ОПС: а3 |
Доп стек:,, +, *, | стек: ^, T’, T’, F’,), T’ | |
Доп стек:,, +, *,, + | стек: ^, T’, T’, F’,), T’, T | |
Доп стек:,, +, *,, +,, a4 Доп стек:,, +, *,, +, | стек: ^, T’, T’, F’,), T’, F’, a стек: ^, T’, T’, F’,), T’, F’, | ОПС: а4 |
Доп стек:,, +, *,, +, | стек: ^, T’, T’, F’,), T’, | |
Доп стек:,, +, *,, | стек: ^, T’, T’, F’,), | ОПС + |
Доп стек:,, +, *, | стек: ^, T’, T’, F’, | |
Доп стек:,, +, | стек: ^, T’, T’, | ОПС: * |
Доп стек:,, | стек: ^, T’, | ОПС:a1,a2,a3, +,*,+ |
Доп стек:,, | стек: ^, |
Рассмотрим еще один пример. Пример анализатора, основанный на грамматиках операторного предшествования.
S→S+T+|T
T→T*F*|F
F→(S)|aa
Генерация ОПС – в момент сворачивания. При некоторых сворачиваниях может ничего не генерироваться.
Т.е и для анализа снизу-вверх можно определить такие синтаксические действия, которые будут генерировать ОПС.
Обобщение ОПС
Проблема: для некоторых переменных в стек записывается значение, а для некоторых – указатель.
Проще всего бороться с этой проблемой следующим образом:
В момент вычисления для каждого элемента задаем признак того, что хранится в стеке (значение или ссылка). Тогда при записи в стек переменной мы на всякий случай можем помещать не значение, а ссылку, по которой потом всегда можно извлечь значение. При вычислении результата мы записываем значение и признак «Значение», а не ссылку. Любая операция должна проверять содержимое ячейки стека и выполнять соответствующие действия.
Для чего нужны ссылки? Для операции индексирования элементов массива. (если переменная является массивом)
Если нужен элемент x[i], то пишем (<адрес начала>+i)/
X I ind (x – ссылка, i – выражение). Операция в итоге выдает ссылку.
X[i+1] = x i 1 + ind
Y[i,j] = y i j ind2
Y[0..9,0..19] получаем адрес y[i,j] <адр y> + i*10 +j
Операция с n операндами: A1…..An N Опер
Чтобы все правильно реализовывалось нужно расширить грамматику так, чтобы в ней были операции индексирования.
Т.е. теперь все правила начинаются с терминальных символов, кроме нуль-порождений.
a1:=a2; a3:=a4 _|_
ОПC: a1a2:=a3a4:=
a1:=a2; a3:=a4 _|_
ОПC: a1a2:=a3a4:=
a1[a2]:=a3[a4+a5]_|_
\\|A'|S |:=|D |a |
|:=| | | |a1|
\\|A'|S |:=|] |S |[ |
|:=| | |[]| | |
\\|A'|S |:=|] |T'|F'|D |a |
|:=| | |[]| | | |a2|
\\|A'|T'|F'|D |a |
|:=| | | |a3|
\\|A'|T'|F'|] |S |[
|:=| | |[]| |
\\|A'|T'|F'|] |T'|F'|D |a |
\\|:=| | |[]| | | |a4|
\\|A'|T'|F'|] |T'|F'|F |* |
\\|:=| | |[]| |* | | |
\\|A'|T'|F'|] |T'|F'|D |a |
\\|:=| | |[]| |* | |a5|
\\|
\\|
ОПС: a1a2 ind a3a4a5* ind:=