3 Часть Обратная польская строка (опс)
Рассмотрим теперь реализацию всего вышеперечисленного в трансляторах.
Лукашевич предложил:
Инфиксная форма (стандартная)
Префиксная (прямая)
Постфиксная (обратная) запись выражений
Займемся постфиксной формой.
ОПС определяется рекурсивно таким образом:
Если операция бинарная, т.е. требует 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, то записали бы так
yab+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
Генерация ОПС – в момент сворачивания. При некоторых сворачиваниях может ничего не генерироваться.
Т.е и для анализа снизу-вверх можно определить такие синтаксические действия, которые будут генерировать ОПС.