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

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

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

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

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