double arrow

Как вычислять выражение, записанное в виде обратной польской строки?

1

Обратная польская строка (ОПС)

Рассмотрим теперь реализацию всего вышеперечисленного в трансляторах.

Лукашевич предложил:

· Инфиксная форма (стандартная)

· Префиксная (прямая)

· Постфиксная (обратная) запись выражений

Займемся постфиксной формой.

ОПС определяется рекурсивно таким образом:

Если операция бинарная, т.е. требует 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:=


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  


1

Сейчас читают про: