Вычисления арифметических записей на основе ПОЛИЗ

Существует два способа записи арифметических выражений: 1) инфиксная (традиционная) и 2) постфиксная (ПОЛИЗ)

Таблица 5.1

Инфиксная	Постфиксная
a*b+c	ab*c+
a+b*c	abc*+
a+b*c-d/(a+b)	abc*+dab+/-

 

Отличие ПОЛИЗ от инфиксной формы состоит в отсутствии круглых скобок () и порядок следования операндов и операций. Вычислять выражения на основе ПОЛИЗ значительно проще, так как отсутствие скобок, переопределяющих приоритет выполнения операций, исключает дополнительный алгоритм порядка выполнения операций. В ПОЛИЗ алгоритм выполнения жёстко определён по правилу: операция справа — результат выполнения двух операндов слева, при этом цепочка ПОЛИЗ просматривается слева направо.

Пример 5.6. Рассмотрим польскую запись ab*c+

Просматривая цепочку слева направо дойдём до знака *. Эта операция выполняется для операндов a и b, в результате образуется цепочка Zc+, где Z = a + b. Просматривая теперь эту цепочку до знака +, выполняем операцию R = Z + c.

Перевод инфиксной формы в ПОЛИЗ. Существует много способов перевода инфиксной записи в постфиксную. Наиболее удачным является алгоритмы Дейкстра и Гриса. Алгоритм Дейкстра основан на использовании стекового механизма с учётом приоритетов.

 

 

Алгоритм Дейкстра:

 

 

 

Рис 5.21. Стековый алгоритм

 

1. Входная строка – арифметическое или логическое выражение – помещается в стек и анализируется слева направо, то есть в вершине стека находится 1 левый символ.

2. Операнды переписываются в стек 2 без изменений. Знаки операций помещаются вначале в стек 3, а затем пересылаются в стек 2 по следующему правилу.

 

	Если приоритет входного знака равен 0 или больше приоритета знака, находящегося в вершине, то новый знак добавляется в стек 3, в противоположном случае из стека 3 выталкивается в стек 2 знак, находящийся в вершине, а так же следующие за ним знаки с приоритетом больше или равным приоритету входного знака. После этого входной знак добавляется в стек операций.

 

 

3. Открывающаяся скобка ‘(’ заносится в стек операций сразу, так как имеет минимальный приоритет , равный нулю, её не может вытолкнуть ни один знак, кроме закрывающейся скобки ‘)’, которая имеет приоритет, равный 1, и не превосходит другие приоритеты операций. И поэтому появление на входе закрывающейся скобки ‘)’ вызывает выталкивание всех знаков из стека 3, до тех пор, пока не появится открывающаяся скобка ‘(’, которая единственная имеет меньший приоритет. В стек закрывающаяся скобка ‘)’ не заносится. Появление в вершине стека 1 закрывающейся скобки ‘)’ и в вершине стека 3 открывающейся скобки ‘(’, вызывает их взаимное уничтожение и разбор продолжается с пункта 1.

 

Таким образом в стеке 2 образуется ПОЛИЗ без скобок!

Пусть дано выражение a+b*c-d/(a+b). Требуется перевести его в ПОЛИЗ. Рассмотрим перевод из инфиксной записи в постфиксную по шагам.

 

 

 

 

 

 

 

 

 

 

 

Таким образом инфиксное выражение a+b*c-d/(a+b) в ПОЛИЗ выглядит так: abc*+dab+/-

После перевода инфиксной записи в ПОЛИЗ алгоритм вычисления арифметический выражений упрощается и состоит в следующем.

	ПОЛИЗ просматривается слева направо. Если анализируемый символ — операнд, то просматривается следующий элемент. Если рассматриваемый символ — операция, то её необходимо выполнить над двумя слева стоящими от неё операндами. Результат рассматривается как операнд в анализируемой строке. Это повторяется до последнего анализируемого символа в строке.

 

 

Пример 5.7. abc*+dab+/-

1)

2)

3)

4)

5)

Алгоритм Дейкстры является эвристическим и трудно реализуется логически. Этого недостатка лишён алгоритм Гриса [1] или транслирующих грамматик, который использует формальные методы анализа и в связи с этим имеет строгую простую реализацию.

 

 

Алгоритм Гриса. (Транслирующих грамматик.)

Пустьграмматика арифметикиG[<AB>] определена как:

1. <AB> ® <AB>+T

2. <AB> ® T

3. T ® T*O

4. T ® O

5. O ® (<AB>)

6. O ® a | b | c

 

Введём семантические атрибуты в правилах 1, 3, 6.

 

1. <AB> ® <AB>+Ty₂

3. T ® T*Oy₁

6. O ® ay₃ | by₃ | cy₃

 

где y_i (i=1,2,3) – это запись соответствующего терминального символа в стек ПОЛИЗ.

Пример 5.8. Проанализируем выражение (a+b)*c с помощью процедуры выводимости, учитывая семантическую атрибутику

<AB> Þ T Þ T*O Þ (<AB>)*Oy₁ Þ (<AB>+Ty₂)*Oy₁ Þ

Þ (ay₃+Ty₂)*Oy₁ Þ (ay₃+by₃y₂)*Oy₁ Þ (ay₃+by₃y₂)*cy₃y₁

 

Выстроим семантические атрибуты в той последовательности, в которой они появляются в процедуре разбора, в результате получим ПОЛИЗ

y₃ y₃ y₂ y₃ y₁

¯ ¯ ¯ ¯ ¯

a b + c *

 

Алгоритм транслирующих грамматик, как это видно из примера, отличается простотой, оригинальностью и, самое главное, строгой формальной схемой. В отличие от эвристики Дейкстра, этот алгоритм основан на теории синтаксически ориентированных методов.

Отметим, что ПОЛИЗ используется в семантике компиляторов не только для арифметических выражений, но и для других языковых конструкций – деклараций, операторов цикла, условных операторов и т. д.