Метод трансляции на основе Польской Инверсной Записи

Томский государственный университет 
Факультет прикладной математики и кибернетики 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Метод трансляции на основе Польской Инверсной Записи 
 
Учебно-методическое пособие 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Томск 
2017 

© Томский государственный университет, 2017

Введение 
 
Методы трансляции программ делятся на 2 группы: 
1. Прямые методы – ориентированы на конкретные языки. 
Для каждой конструкции языка подбирается индивидуальный 
алгоритм на основе некоторой общей идеи. 
2. Синтаксические методы – ориентированы не на конкретный язык, а на класс языков, имеющих одинаковый способ описания синтаксиса языка. Эти методы основаны на теории формальных грамматик. 
Один из прямых методов использует для трансляции Польскую Инверсную Запись (ПОЛИЗ). Метод предложен польским 
ученым Яном Лукашевичем. 
 
1. Трансляция выражений 
 
1.1. Определение ПОЛИЗ 
 
Первые языки программирования высокого уровня предназначались для решения инженерных и научно-технических задач вычислительного характера. Значительную часть таких программ составляют различные арифметические и логические выражения. Для трансляции выражений разработаны различные 
методы, но классическим стал метод перевода выражений в 
промежуточную форму – ПОЛИЗ. 
Рассмотрим суть этого метода на примере. 
Пусть дано выражение  a + b * c – d/(a + b). 
Представим его вычисление в виде дерева: в корень дерева 
поместим последнюю выполняемую операцию; ветви будут соответствовать операндам. В каждой ветви операциям, которые 
выполняются раньше, соответствуют нижележащие узлы. Висячие вершины называются листьями дерева, они соответствуют 
операндам. 

Выполним левый обход этого дерева по правилу:  
начать с листа самой левой ветви  дерева и обойти все узлы и 
листья дерева так, чтобы ветви рассматривались слева направо, 
а узлы – после обхода всех ветвей, исходящих из них (правило 
обхода «влево – вправо – в корень»). Тогда последовательность 
обхода задает польскую инверсную запись 
 
 
a b c * + d a b + / - 
 
Свойства ПОЛИЗ: 
1) бесскобочная запись; 
2) операнды – в том же порядке, что и в исходном выражении; 
3) операции – в порядке их выполнения; 
4) операции располагаются сразу после своих операндов – 
постфиксная запись. 
Отсюда название – инверсная (или обратная) запись. Эти 
свойства позволяют вычислить выражение за один проход слева 
направо по простому правилу. 

1.2. Правило вычисления ПОЛИЗ 
 
Просматривать ПОЛИЗ слева направо, как строку элементов. 
Операнды пропускать, а при появлении операции выполнять её 
над ближайшими к ней слева операндами. После этого операция 
и операнды вычеркиваются из строки, вместо них записывается 
результат операции. Запись должна сократиться до одного элемента – результата вычисления выражения. 
Для нашего примера запишем действия в таблицу: здесь r1, r2 – 
рабочие переменные. 
                              

ПОЛИЗ
Вычисления 

a b c * + d a b + / –
r1 = b * c

a r1 + d a b + / –
r1 = a + r1

r1 d a b + / –
r2 = a + b

r1 d r2 / –
r2 = d / r2

r1 r2 –
r1 = r1 – r2

r1
результат

Записанные действия легко перевести на язык Ассемблера. 
Трансляция ПОЛИЗа на язык Ассемблера производится по 
тому же правилу, что и вычисление ПОЛИЗ, но действия задаются соответствующими командами. Для хранения промежуточных данных (результатов операций) будем использовать рабочие переменные (регистры или вспомогательные ячейки памяти) по следующим правилам (по принципу «не брать лишних, 
не портить нужных»): 
1) если среди операндов операции нет рабочих переменных, то 
вводится новая рабочая переменная, в которую заносится результат операции; 
2) если среди операндов есть одна или несколько рабочих переменных, то результат записывается в переменную с минимальным номером, все остальные освобождаются. 
Этих правил мы придерживались в приведенном примере; 
выполним для него трансляцию на язык Ассемблера (nasm для 
ОС Linux).  

ПОЛИЗ
Вычисления
Команды Ассемблера

a b c * + d a b + / –
r1 = b * c
Mov ax, [b]
Imul [c]             ; r1 – ax

a r1 + …
r1 = a + r1
Add ax, [a]

r1 d a b + …
r2 = a + b
Mov bx, [a]
Add bx, [b]       ; r2 – bx

r1 d  r2 / –
r2 = d/r2
Mov cx, ax
; r1 – cx 

Mov ax, [d] 
Mov dx,0    ; если d>=0 
Idiv bx        ; r2 – ax

r1 r2 –
r1 = r1 – r2
Sub cx, ax  ; результат

  
1.3 Алгоритм вычисления ПОЛИЗ со стеком операндов 
Рассмотренное выше правило вычисления ПОЛИЗ малопригодно для реализации на ЭВМ по двум причинам: 
1) использует неэффективные операции вычеркивания элементов из строки и вставки в строку; 
2) строка должна хранить разнотипные данные – числовые 
(результаты вычислений)  и символьные (переменные, знаки 
операций). Рассмотрим другой способ вычислений с использованием стека. 
Стек – структура данных, представляющая собой одномерный динамический набор элементов. Причем добавление и удаление элементов выполняется с одного конца – вершины стека – 
по принципу LIFO (Last In – First Out), как в стопке тарелок. 
              указатель на вершину стека 
ak
…
a1
a0
дно 
Дно стека неподвижно. Элементы, расположенные ниже элемента ak в вершине стека,  недоступны. На языке Си добавление 
в стек элемента x: a[++k] = x; извлечение  x = a[k– –]. 

Для вычисления ПОЛИЗ будем использовать стек операндов. 
К моменту выполнения каждой операции её операнды должны 
быть в стеке. Заметим, что у операции может быть разное количество операндов: 
унарные имеют один операнд:  -, ~, ! 
бинарные – два: +, –, /, *, % 
тернарные – три: ? : 
 
Алгоритм вычисления ПОЛИЗ со стеком операндов: 
 
1. Рассматривая ПОЛИЗ как строку элементов, операнды заносим в стек. 
2. При встрече знака операции извлекаем из стека нужное 
число операндов, применяем к ним операцию и результат заносим в стек. 
Примечание. Нужно учитывать, что операнды извлекаются 

из стека в обратном порядке. Например, для двуместной операции сначала второй, затем первый. 

 
3. В конце работы в стеке должно остаться одно значение, 
которое и является результатом вычислений. Если в стеке остается несколько значений либо он пустеет раньше времени, то 
либо исходное выражение неверно, либо ПОЛИЗ построен неправильно. 
Для нашего примера 
a b c * + d a b + / − 
пусть a = 4, b = 3,  c = 2, d  = 14 

4

3

4

*

2

3

4

+
6

10

+
4
3

14

10

/
7
14

10
2
−

8

b
a

a – b, а не b – a

1.4. Алгоритм Дейкстры формирования ПОЛИЗ простого 
арифметического выражения 
 
Мы формировали ПОЛИЗ на основе дерева выражения. Этот 
способ мало подходит для реализации его на ЭВМ. Э. Дейкстра 
предложил использовать для формирования ПОЛИЗ стек операций с приоритетами. Основная задача для формирования 
ПОЛИЗ – переставить знаки операций в порядке исполнения, 
который зависит от приоритетов операций и круглых скобок: 
чем больше приоритет операции, тем раньше она исполняется. 
Таблица приоритетов некоторых операций языка С для алгоритма Дейкстры: 
 

Знаки
Сравнительный

приоритет

Стековый
приоритет

if ( { [
0
0

, ; ) } else
1
1

]
1
10

=
9
2

||
3
3

&&
4
4

< <= == != >= >
5
5

+ −
6
6

* / %
7
7

! ~ ++ − −
8
8

 
Алгоритм Дейкстры. 
Исходное выражение просматривается последовательно как 
строка элементов. Операнды сразу заносятся в ПОЛИЗ, а операции - через стек по следующему правилу: 
1) если стек пуст, то любой знак сразу заносится в стек; 
2) знаки с нулевым приоритетом также заносятся сразу в 
стек; 

3) иначе сравниваются приоритеты входного знака и знака в 
вершине стека 
а) если приоритет входного знака больше приоритета знака в 
вершине стека, то входной знак заносится в стек; 
б) иначе входной знак сначала выталкивает из стека в 
ПОЛИЗ все знаки с бóльшим или равным приоритетом, а затем 
заносится в стек; 
4) особым образом обрабатываются круглые скобки. Скобка 
‘(’, имея приоритет 0, сразу заносится в стек. Скобка ‘)’, имея 
приоритет 1, выталкивает из стека все знаки до ближайшей ‘(‘ 
по общему правилу. Далее отличие – скобки взаимно уничтожаются; 
5) когда закончится выражение, стек очищается: все знаки из 
него выталкиваются в ПОЛИЗ. 
Схематично работу алгоритма можно изобразить так: 
 

 

a b +… 
(a + b)* c…

операнды

стек

операций

операции

ПОЛИЗ
входная строка

Пример 1. 
 

ПОЛИЗ
a b c * + d
a
b + / −

Стек
    опе 
       ра 
         ций 

                + 
                (                  ( 
   *           /                  / 

+   
−
−

Исходное выражение
a + b * c  − d / ( a  + b )

 
Пример 2.  
  

ПОЛИЗ
a   b − c  d    10 a * + * −

Стек
   опе 
     ра 
      ций 

*

             +                 
             ( 
             *                        * 

−
− −
− 

Исходное выражение
a − b − c * ( d + 10 * a )

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