Язык внутреннего представления программы
Основные свойства языка внутреннего представления программ:
a) он позволяет фиксировать синтаксическую структуру исходной программы;
b) текст на нем можно автоматически генерировать во время синтаксического анализа;
c) его конструкции должны относительно просто транслироваться в объектный код либо достаточно эффективно интерпретироваться.
Некоторые общепринятые способы внутреннего представления программ:
a) постфиксная запись
b) префиксная запись
c) многоадресный код с явно именуемыми результатами
d) многоадресный код с неявно именуемыми результатами
e) связные списочные структуры, представляющие синтаксическое дерево.
В основе каждого из этих способов лежит некоторый метод представления синтаксического дерева.
Замечание: чаще всего синтаксическим деревом называют дерево вывода исходной цепочки, в котором удалены вершины, соответствующие цепным правилам вида A ® B, где A, B Î VN.
Выберем в качестве языка для представления промежуточной программы постфиксную запись (ее часто называют ПОЛИЗ - польская инверсная запись).
В ПОЛИЗе операнды выписаны слева направо в порядке их использования. Знаки операций стоят таким образом, что знаку операции непосредственно предшествуют ее операнды.
Например, обычной (инфиксной) записи выражения
a*(b+c)-(d-e)/f
соответствует такая постфиксная запись:
abc+*de-f/-
Замечание: обратите внимание на то, что в ПОЛИЗе порядок операндов остался таким же, как и в инфиксной записи, учтено старшинство операций, а скобки исчезли.
Более формально постфиксную запись выражений можно определить таким образом:
(1) если Е является единственным операндом, то ПОЛИЗ выражения Е - это этот операнд;
(2) ПОЛИЗом выражения Е1 q Е2, где q - знак бинарной операции,
Е1 и Е2 операнды для q, является запись E1’ E2’ q , где E1’ и E2’ - ПОЛИЗ выражений Е1 и Е2 соответственно;
(3) ПОЛИЗом выражения q E, где q- знак унарной операции, а Е - операнд q, является запись E’ q, где E’ - ПОЛИЗ выражения Е;
(4) ПОЛИЗом выражения (Е) является ПОЛИЗ выражения Е.
Запись выражения в такой форме очень удобна для последующей интерпретации (т.е. вычисления значения этого выражения) с помощью стека: выражение просматривается один раз слева направо, при этом
(1) если очередной элемент ПОЛИЗа - это операнд, то его значение заносится в стек;
(2) если очередной элемент ПОЛИЗа - это операция, то на "верхушке" стека сейчас находятся ее операнды (это следует из определения ПОЛИЗа и предшествующих действий алгоритма); они извлекаются из стека, над ними выполняется операция, результат снова заносится в стек;
(3) когда выражение, записанное в ПОЛИЗе, прочитано, в стеке останется один элемент - это значение всего выражения.
Замечание: для интерпретации, кроме ПОЛИЗа выражения, необходима дополнительная информация об операндах, хранящаяся в таблицах.
Замечание: может оказаться так, что знак бинарной операции по написанию совпадает со знаком унарной; например, знак "-" в большинстве языков программирования означает и бинарную операцию вычитания, и унарную операцию изменения знака. В этом случае во время интерпретации операции "-" возникнет неоднозначность: сколько операндов надо извлекать из стека и какую операцию выполнять. Устранить неоднозначность можно, по крайней мере, двумя способами:
a) заменить унарную операцию бинарной, т.е. считать, что "-а" означает
"0-а";
b) либо ввести специальный знак для обозначения унарной операции; например, "-а" заменить на "&a". Важно отметить, что это изменение касается только внутреннего представления программы и не требует изменения входного языка.
Теперь необходимо разработать ПОЛИЗ для операторов входного языка. Каждый оператор языка программирования может быть представлен как n-местная операция с семантикой, соответствующей семантике этого оператора.
Оператор присваивания
I := E
в ПОЛИЗе будет записан как
I E :=
где ":=" - это двухместная операция, а I и Е - ее операнды; I означает, что операндом операции ":=" является адрес переменной I, а не ее значение.
Оператор перехода в терминах ПОЛИЗа означает, что процесс интерпретации надо продолжить с того элемента ПОЛИЗа, который указан как операнд операции перехода.
Чтобы можно было ссылаться на элементы ПОЛИЗа, будем считать, что все они перенумерованы, начиная с 1 (допустим, занесены в последовательные элементы одномерного массива).
Пусть ПОЛИЗ оператора, помеченного меткой L, начинается с номера p, тогда оператор перехода gotoL в ПОЛИЗе можно записать как
p !
где ! - операция выбора элемента ПОЛИЗа, номер которого равен p.
Немного сложнее окажется запись в ПОЛИЗе условных операторов и операторов цикла.
Введем вспомогательную операцию - условный переход "по лжи" с семантикой
if (not B) then goto L
Это двухместная операция в операндами B и L. Обозначим ее !F, тогда в ПОЛИЗе она будет записана как
B p !F
где p - номер элемента, с которого начинается ПОЛИЗ оператора, помеченного меткой L.
Семантика условного оператора
ifBthenS1elseS2
с использованием введенной операции может быть описана так:
if (not B) then goto L2; S1; goto L3; L2: S2; L3: ...
Тогда ПОЛИЗ условного оператора будет таким:
B p2 !F S1 p3 ! S2 ... ,
где pi - номер элемента, с которого начинается ПОЛИЗ оператора, помеченного меткой Li, i = 2,3.
Семантика оператора цикла whileBdoSможет быть описана так:
L0: if (not B) then goto L1; S; goto L0; L1: ... .
Тогда ПОЛИЗ оператора цикла while будет таким:
B p1 !F S p0 ! ... ,
где pi - номер элемента, с которого начинается ПОЛИЗ оператора, помеченного меткой Li, i = 0,1.
Операторы ввода и вывода М-языка являются одноместными операциями. Пусть R - обозначение операции ввода, W - обозначение операции вывода.
Тогда оператор ввода read(I) в ПОЛИЗе будет записан как I R;
оператор вывода write(E) - как E W.
Постфиксная польская запись операторов обладает всеми свойствами, характерными для постфиксной польской записи выражений, поэтому алгоритм интерпретации выражений пригоден для интерпретации всей программы, записанной на ПОЛИЗе (нужно только расширить набор операций; кроме того, выполнение некоторых из них не будет давать результата, записываемого в стек).
Постфиксная польская запись может использоваться не только для интерпретации промежуточной программы, но и для генерации по ней объектной программы. Для этого в алгоритме интерпретации вместо выполнения операции нужно генерировать соответствующие команды объектной программы.