Польская запись

Польская запись позволяет преобразовывать выражения в удобную для машинного перевода (трансляции) форму. Обычная форма записи предполагает запись знака операции между операндами, например:

1. ,

2. ,

3. .

Такая запись называется инфиксной.

Прямая польская запись (префиксная) – запись, когда обозначения операции записываются до операндов:

1. ,

2. 

3. 

Скобки при такой записи отсутствуют. Приоритет выполнения операции очевиден. Однако прямая польская запись для трансляции не используется. Используется обратная польская запись – постфиксная.

Она требует, чтобы знаки операции записывались после соответствующих операндов:

1. 

2. 

3. 

В дальнейшем будем использовать именно эту форму.

Польской такая нотация названа в честь ее изобретателя польского математика Я.Лукасевича(1878-1956). Для обратной польской записи введено сокращение ПОЛИЗ. При записи в ПОЛИЗ операнды записываются в порядке следования в исходном выражении, а операции после своих операндов в порядке выполнения.

Примеры:

1. 

2. 

3. 

4. 

Свойства ПОЛИЗ:

1. однозначно определяется порядок выполнения операции;

2. запись имеет простую синтаксическую структуру.

Свяжем с каждым элементом ПОЛИЗ некоторый весв соответствии со следующим правилом:

если – переменная или константа, то,

если – знак унарной операции, то,

если – знак бинарной операции, то,

если – знак-местной операции, то.

Определим некоторую функцию: .

Тогда для правильного выражения справедливо .

для выражения из элементов. Выражение можно изобразить в виде дерева (семантического дерева выражений). Вершины – операции, ветви – операнды.

Наши выражения из примера 1 могут быть записаны в виде деревьев:

В виде ПОЛИЗ представляются и другие конструкции языка, а именно: переменные с индексами, указатели функции, условные выражения, циклы. Правило общее: знак операции следует непосредственно за соответствующими ему операндами. Для представления других конструкций вводятся специальные операции ПОЛИЗ. Например, чтобы описать элементы массива, вводится дополнительная операция вычисления элемента массива. Она обозначается SUBS. Ее операндом является имя массива и значение индексов. Число операндов k зависит от размерности массива n и определяется: k=n+1.

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

будет иметь вид:

Сама польская запись имеет вид:

Указатели функции - вводится дополнительная операция – CALL, имеющая переменное число операндов k, и зависящая от числа аргументов в вызванной функции k=n+1.

Вычислить

afij1+3CALL+

Перевод других конструкций требует других операторов, их рассмотрим позже.

Алгоритм вычисления выражений в обратной польской записи

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

Например, необходимо вычислить 7+5*2 : 752*+

Вход	Действия	Магазин (стек)
752*+	Записать в стек операнд (7)	7
52*+	Записать в стек операнд (5)	57
2*+	Записать в стек операнд (2)	257
*+	прочитать операнд (2) прочитать операнд (5) выполнить операцию (*) записать результат в стек (10)	10 7
+	прочитать из магазина (10) прочитать из магазина (7) выполнить операцию (+) записать результат	17