Польская инверсная запись

Вместо традиционного инфиксного (скобочного) представления арифметических и логических выражений в различных вычислителях часто используется польская инверсная запись (ПОЛИЗ), которая просто и точно указывает порядок выполнения операций без использования скобок. В этой записи, впервые примененной польским математиком Я.Лукашевичем, операторы располагаются непосредственно за операндами над которыми они выполняются в порядке их выполнения. Поэтому иногда ПОЛИЗ называют суффиксной или постфиксной записью. Например, A+B записывается как AB+, A*B+C – как AB*C+, A*(B+C/D) – как ABCD/+*, а A*B+C*D – как AB*CD*+.

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

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

2). Операторы в ПОЛИЗе следуют в том порядке, в каком они должны вычисляться (слева направо).

3). Операторы располагаются непосредственно за своими операндами.

Таким образом, мы могли бы записать следующие синтаксические правила:

<операнд>::=идентификаторôконстантаô<операнд><операнд><оператор>

<оператор>::=+ô-ô*ô/ô¼

Унарный минус и другие унарные операторы можно представить двумя способами: либо записывать их бинарными операторами, то есть вместо -B писать 0-B, либо для унарного минуса можно ввести новый специальный символ, например @, и использовать еще одно синтаксическое правило <:операнд>::=<операнд>@. Таким образом выражение A+(-B+C*D) мы могли бы записать AB@CD*++.

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

ПОЛИЗ расширяется достаточно просто. Нужно только придерживаться правила, что за операндами следует соответствующий им оператор. Так присваивание <переменная>:=<выражение> в ПОЛИЗе примет вид <переменная><выражение>:=. Например, присваивание А:=B*C+D*100 запишется в ПОЛИЗе как АBC*D100*+:=.

Индексированную переменную в ПОЛИЗе, а точнее вычисление ее адреса можно представить в виде:

идентификатор<индексные выражения>константа[ ,

где [ – обозначает знак операции вычисления индекса, идентификатор – имя (базовый адрес) индексированной переменной, а константа – количество индексов (мерность массива). Так переменную A[i,j+k] можно представить в виде Аijk+2[ .

Условный оператор

IF <выр> THEN <инстр ₁> ELSE <инстр ₂>

в ПОЛИЗе будет иметь вид:

<выр> < m > УПЛ <инстр ₁> < n > БП <инстр ₂> , где

· <выр> – логическое выражение (условие), которое может принимать значения – 0 (FALSE, ложь) или 1 (TRUE, истина);

· < m > – номер (место, позиция, индекс) символа ПОЛИЗа, с которого начинается <инстр ₂>;

· УПЛ (Условный Переход по Лжи) – оператор с двумя операндами <выр> и < m >, смысл которого состоит в том, что он изменяет традиционный порядок вычислений и осуществляет переход на символ строки ПОЛИЗа с номером < m >, если (и только если) <выр> – ложно (равно 0);

· < n > – номер символа, следующего за <инстр ₂>;

· БП (Безусловный Переход) – оператор с одним операндом < n >, который также изменяет порядок вычислений по ПОЛИЗу и осуществляет переход на символ с номером < n >.

Операторы условного и безусловного перехода, как в свое время было показано Дейкстрой, составляют основу внутреннего представления любой структурной управляющей конструкции (циклов типа FOR, WHILE, REPEAT, оператора выбора и т.п.). В рассматриваемых нами примерах потребуется только один условный оператор – УПЛ, хотя никто не мешает определить целую группу таких операторов (смотри, например, мнемонику команды условного перехода языка ассемблера для ПЭВМ с процессором Intel 8086).

Пример 7.1.

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

IF (x<y) AND (a< >0) THEN b:=a+b*c ELSE b:=(a+b)*c; x:=a*b+c*d;

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

xy< a 0 < > AND 19 УПЛ b a b c * + := 26 БП b a b + c * := x a b * c d * + :=

Интерпретация ПОЛИЗа

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

1). Если сканируемый символ идентификатор или константа, то соответствующее им значение заносится в стек и осуществляется переход к следующему символу строки ПОЛИЗа. Это соответствует использованию правила <:операнд>::=идентификаторôконстанта

2). Если сканируемый символ унарный оператор, то он применяется к верхнему операнду в стеке, который затем заменяется на полученный результат. С точки зрения семантики это соответствует применению правила

<:операнд>::= <операнд><оператор>.

3). Если сканируемый символ бинарный арифметический или логический оператор, то он применяется к двум верхним операндам в стеке, и затем они заменяются на полученный результат. Это соответствует использованию правила <:операнд>::= <операнд><операнд><оператор>.

Одно из исключений – бинарный оператор присваивания, который в ПОЛИЗе имеет вид <пер><выр>:=. После его выполнения и <пер>, и <выр> должны быть исключены из стека, так как оператор ‘:=’ не имеет результирующего значения. При этом в стеке должно находится не значение <пер>, а ее адрес, так как значение <выр> должно сохраняться по адресу <пер>.

4). Бинарный оператор УПЛ, операндами которого является уже вычисленное значение логического выражения <выр> и номер символа строки ПОЛИЗа – <m>, также удаляет оба операнда из стека и не формирует в нем результата. Его действие состоит в том, что он анализирует значение выражения, и если оно равно 1 (истинно), то следующим сканируется символ, расположенный сразу за УПЛ. Если же значение выражения – 0 (ложно), то мы перемещаемся по строке ПОЛИЗа к символу, позиция которого указана в операнде <m>.

5). Унарный оператор БП, удаляя свой параметр, – номер символа < n > из стека, просто переводит сканирование к указанной позиции ПОЛИЗа.

Пример 7.2.

На рис. 7.1 показан пример интерпретации строки ПОЛИЗа AB@CD*++ , полученной из инфиксного выражения A+(-B+C*D). Значения в стеке отделены друг от друга вертикальной чертой.

Поиск по сайту: