Польская инверсная запись — это постфиксная запись операций. Она была предложена польским математиком Я. Лукашевичем, откуда и происходит ее название.
В этой записи знаки операций записываются непосредственно за операндами. По сравнению с обычной (инфиксной) записью операций в польской записи операнды следуют в том же порядке, а знаки операций — строго в порядке их выполнения. Тот факт, что в этой форме записи все операции выполняются в том порядке, в которой они записаны, делает ее чрезвычайно удобной для вычисления выражений на компьютере. Польская запись не требует учитывать приоритет операций, в ней не употребляются скобки, и в этом ее основное преимущество.
Она чрезвычайно эффективна в тех случаях, когда для вычислений используется стек. Ниже будет рассмотрен алгоритм вычисления выражений в форме обратной польской записи с использованием стека.
Главный недостаток обратной польской записи также проистекает из метода вычисления выражений в ней: поскольку используется стек, то для работы с ним всегда доступна только верхушка стека, а это делает крайне затруднительной оптимизацию выражений в форме обратной польской записи. Практически выражения в форме обратной польской записи почти не поддаются оптимизации.
|
|
Но там, где оптимизация вычисления выражений не требуется или не имеет большого значения, обратная польская запись оказывается очень удобным методом внутреннего представления программы.
Перевод в ПОЛИЗ выражений.
Пример Для выражения в обычной (инфиксной записи) a *(b + c)-(d - e)/ f ПОЛИЗ будет иметь вид: abc+ * de - f /-.
Справедливы следующие формальные определения.
Определение Если Е является единственным операндом, то ПОЛИЗ выражения Е – это этот операнд.
Определение ПОЛИЗ выражения Е1 q Е2, где q - знак бинарной операции, Е 1 и Е 2 – операнды для q, является запись , где - ПОЛИЗ выражений Е 1 и Е 2 соответственно.
Определение ПОЛИЗ выражения qЕ, где q - знак унарной операции, а Е – операнд q, есть запись , где - ПОЛИЗ выражения Е.
Определение ПОЛИЗ выражения (Е) есть ПОЛИЗ выражения Е.
Перевод в ПОЛИЗ операторов.
Каждый оператор языка программирования может быть представлен как n -местная операция с семантикой, соответствующей семантике оператора.
Оператор присваивания I:=E в ПОЛИЗе записывается:
I E:=,
где «:=» - двуместная операция,
I, E – операнды операции присваивания;
I – означает, что операндом операции «:=» является адрес переменной I, а не ее значение.
Пример Оператор x:= x +9 в ПОЛИЗе имеет вид: x x 9 +:=.
Оператор перехода в терминах ПОЛИЗа означает, что процесс интерпретации необходимо продолжить с того элемента ПОЛИЗа, который указан как операнд операции перехода. Чтобы можно было ссылаться на элементы ПОЛИЗа, будем считать, что все они пронумерованы, начиная с единицы (например, последовательные элементы одномерного массива). Пусть ПОЛИЗ оператора, помеченного меткой L, начинается с номера p, тогда оператору безусловного перехода goto L в ПОЛИЗе будет соответствовать:
|
|
p!, где! – операция выбора элемента ПОЛИЗа, номер которого равен p.
Условный оператор. Введем вспомогательную операцию – условный переход «по лжи» с семантикой if (not B) then goto L. Это двуместная операция с операндами B и L. Обозначим ее! F, тогда в ПОЛИЗе она будет записываться:
B p! F, где p – номер элемента, с которого начинается ПОЛИЗ оператора, помеченного меткой L.
С использованием введенной операции условный оператор if B then S 1 else S 2 в ПОЛИЗе будет записываться:
B p 1 ! F S 1 p 2 ! S 2, где p 1 – номер элемента, с которого начинается ПОЛИЗ оператора S 2, а p 1 – оператора, следующего за условным оператором.
Пример ПОЛИЗ оператора if x >0 then x:= x +8 else x:= x -3 представлен в таблице 4.3
Таблица 4.3 – ПОЛИЗ оператора if
лексема | x | > | ! F | x | x | + | := | ! | x | x | - | := | … | |||||
номер |
Оператор цикла. С учетом введенных операций оператор цикла while B do S в ПОЛИЗе будет записываться:
B p 1 ! F S p o!, где p o – номер элемента, с которого начинается ПОЛИЗ выражения B, а p 1 – оператора, следующего за данным оператором цикла.
Операторы ввода и вывода языка М одноместные. Пусть R – обозначение операции ввода, а W – обозначение операции вывода, тогда оператор read (I) в ПОЛИЗе запишется как I R, а оператор write (E) – E W.
Составной оператор begin S 1; S 2;...; S n end в ПОЛИЗе записывается как S 1 S 2 ... S n.
Пример ПОЛИЗ оператора while n >3 do begin write (n*n -1); n:= n -1 end представлен в таблице 4.4
Таблица 4.4 – ПОЛИЗ оператора while
лексема | n | > | ! F | n | n | * | - | W | n | n | - | := | ! | … | |||||
номер |