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) (по грамматике простых алгебраических выражений). Его нужно дополнить такими семантическими программами, чтобы на выходе выдавалась ОПС, соответствующая входному значению.

S₀→(S)F’T’_|_ | aF’T’ _|_

S→(S) F’T’ | a F’T’

T’→λ|+TT’

T→ (S)F’|aF’

F’→ λ|*FF’

F→(S)|a

Грамматика, преобразованная к нормальной форме Грейбах.

Для семантических программ для каждой ячейки стека создадим ячейку в дополнительном стеке. Для каждой правой части снизу дорисуем такие элементы, которые будут заноситься во второй стек.

S₀→(S)F’T’_|_ | a_a F’T’ _|_

S→(S) F’T’ | a_a F’T’

T’→λ|+TT’₊

T→ (S)F’|a_a F’

F’→ λ|*FF’_*

F→(S)|a_a

Когда мы удаляем какой-то элемент из стека и если в дополнительном стеке соответствующий элемент, записываем его в выходную ОПС.

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)|a_a

Генерация ОПС – в момент сворачивания. При некоторых сворачиваниях может ничего не генерироваться.

Т.е и для анализа снизу-вверх можно определить такие синтаксические действия, которые будут генерировать ОПС.