Язык внутреннего представления программы

Основные свойства языка внутреннего представления программ:

- он позволяет фиксировать синтаксическую структуру исходной программы;

- текст на нем можно автоматически генерировать во время синтаксического анализа;

- его конструкции должны относительно просто транслироваться в объектный код либо достаточно эффективно интерпретироваться.

Некоторые общепринятые способы внутреннего представления программ:

- постфиксная запись;

- префиксная запись;

- многоадресный код с явно именуемыми результатами;

- многоадресный код с неявно именуемыми результатами;

- связные списочные структуры, представляющие синтаксическое дерево.

В основе каждого из этих способов лежит некоторый метод представления синтаксического дерева.

Обычно синтаксическим деревом называют дерево вывода исходной цепочки, в котором удалены вершины, соответствующие цепным правилам вида A ® B, где A, B Î VN.

Выберем в качестве языка для представления промежуточной программы постфиксную запись (ее часто называют ПОЛИЗ - польская инверсная запись).

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

Например, обычной (инфиксной) записи выражения a*(b+c)-(d-e)/f

соответствует такая постфиксная запись: abc+*de-f/-.

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

Более формально постфиксную запись выражений можно определить таким образом:

1) если Е является единственным операндом, то ПОЛИЗ выражения Е - это этот операнд;

2) ПОЛИЗом выражения Е₁ q Е₂, где q - знак бинарной операции,
Е₁ и Е₂ операнды для q, является запись E₁’ E₂’ q , где E₁’ и E₂’ - ПОЛИЗ выражений Е₁ и Е₂ соответственно;

3) ПОЛИЗом выражения q E, где q- знак унарной операции, а Е - операнд q, является запись E’ q, где E’ - ПОЛИЗ выражения Е;

4) ПОЛИЗом выражения (Е) является ПОЛИЗ выражения Е.

Запись выражения в такой форме очень удобна для последующей интерпретации (то есть вычисления значения этого выражения) с помощью стека: выражение просматривается один раз слева направо, при этом

(1) если очередной элемент ПОЛИЗа - это операнд, то его значение заносится в стек;

(2) если очередной элемент ПОЛИЗа - это операция, то на "верхушке" стека сейчас находятся ее операнды (это следует из определения ПОЛИЗа и предшествующих действий алгоритма); они извлекаются из стека, над ними выполняется операция, результат снова заносится в стек;

(3) когда выражение, записанное в ПОЛИЗе, прочитано, в стеке останется один элемент - это значение всего выражения.

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

Может оказаться так, что знак бинарной операции по написанию совпадает со знаком унарной; например, знак "-" в большинстве языков программирования означает и бинарную операцию вычитания, и унарную операцию изменения знака. В этом случае во время интерпретации операции "-" возникнет неоднозначность: сколько операндов надо извлекать из стека и какую операцию выполнять. Устранить неоднозначность можно, по крайней мере, двумя способами:

1) заменить унарную операцию бинарной, то есть считать, что "-а" означает "0-а";

2) либо ввести специальный знак для обозначения унарной операции; например, "-а" заменить на "&a" (это изменение касается только внутреннего представления программы и не требует изменения входного языка).

Теперь необходимо разработать ПОЛИЗ для операторов входного языка.

Каждый оператор языка программирования может быть представлен как n-местная операция с семантикой, соответствующей семантике этого оператора.