6.2. Представления промежуточной программы

Промежуточная программа должна, с одной стороны, отражать синтаксическую структуру исходной программы, а с другой стороны, каждый оператор промежуточной программы должен относительно просто транслироваться в машинный код.

Наиболее распространенными способами представления промежуточной программы являются :

1) постфиксная польская запись ;

2) префиксная польская запись ;

3) списочные структуры, представляющие деревья ;

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

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

Рассмотрим эти способы представления на примере оператора присваивания :

A:=B+C* (- D ) ,

постфиксная и префиксная формы польской записи этого оператора имеют вид :

A B C D - * + := ; - постфиксная форма ;

:= A + B * C - D ; - префиксная форма .

Эти формы записи являются линейными представлениями синтаксического дерева , показанного на рис. 6.1.

Рис.6.1

Правило построения синтаксического дерева следующее :

внутренние вершины дерева представляют операции , операндами которых служат их (вершины) прямые потомки .

Можно использовать три способа обхода дерева : слева - направо, сверху - вниз, снизу - вверх . Легко видеть, что между этими способами обхода и формами записи существует соответствие :

обход слева - направо ® инфиксная форма (обычная)

A :=B + C *- D ;

обход сверху - вниз ® префиксная форма := A + B * C - D ;

обход снизу - вверх ® постфиксная форма A B C D - * + := .

Синтаксическое дерево можно закодировать списочной структурой. Тогда эта структура будет являться промежуточной программой.

Другой метод кодирования синтаксического дерева - применение многоадресного кода с явно именуемыми результатами. Используя этот код, синтаксическое дерево (рис.6.1) можно представить в виде последовательности следующих элементарных кодов :

T₁ ¬ - D,

T₂ ¬ * C T₁,

T₃ ¬ + B T₂,

A ¬ T₃ .

Код вида А¬ Q B₁¼B_n означает, что n - местную операцию Q необходимо применить к текущим значениям переменных (операндов) B₁¼B_n, и полученное значение присвоить переменной А. В таком коде используется ряд промежуточных переменных для запоминания результатов. Можно избежать их использования, если применить многоадресный код с неявно именуемыми результатами. Для этого каждый элементарный код помечается числом, затем левая часть кода убирается и обращение к промежуточному результату происходит при помощи этого приписанного числа. Для рассматриваемого примера последовательность кодов с неявно именуемыми результатами выглядит следующим образом :

1 : - D,

2 : * C (1),

3 : + B (2),

4 : = A (3).

Число в скобках здесь означает адрес выражения, помеченного этим числом. Проиллюстрируем еще раз технику представления промежуточной программы на примере оператора “ если ” , следующего вида :

if i = j then S₁ else S₂ ,

где S₁ и S₂ - некоторые произвольные операторы.

Возможное постфиксное польское представление этого оператора имеет вид i j EQUAL L₂ JFALSE L JAMP ,

где и - постфиксное представление операторов S₁ и S₂ соответственно ;

EQUAL - бинарная операция проверки на равенство операндов (принимает значение истина или ложь ) ;

L₂ - метка начала ;

JFALSE - бинарная операция , вызывающая переход по второму аргументу , если значение первого - ложь , и не вызывающая никаких действий , если значение первого - истина ;

L - метка первой команды следующей за ;

JUMP - унарная операция, вызывающая переход на точку, задаваемую аргументом .

Левый анализатор построил бы для данного оператора “если” его левый разбор p, которому соответствует дерево вывода, показанное на рис. 6.2.

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

Сравнивая рис. 6.2 и 6.3 легко видеть , что дерево вывода и синтаксическое дерево тесно связаны. Как правило, синтаксическое дерево является деревом вывода , в котором удалены цепные правила . В то же время анализатор или генератор кода легко может заменить номера правил разбора p на команды построения синтаксического дерева, поэтому разборы p, порождаемые анализаторами, можно считать компактными представлениями промежуточных программ.

Рис. 6.3

В заключение приведем два примера без комментариев.

Пример 6.1. Задан оператор A := ( B - C ) / ( B + C ). Синтаксическое дерево, представляющее этот оператор, показано на рис. 6.4.

Постфиксное польское представление имеет вид

ABC - BC + / := .

Рис. 6.4

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

T₁ ¬ - BC,

T₂ ¬ +BC,

T₃ ¬ / T₁ T₂ ,

A ¬ T₃ .

Пример 6.2. Задан оператор :

if B > C then

if D > E then A := B + С

else A := B - C

else A := B * C

Синтаксическое дерево для этого оператора показано на рис. 6.5.

Постфиксное польское представление имеет вид

B C GT L₂ JFALSE D E GT L₃ JFALSE A B C + := L JUMP

A B C-:= L JUMP A B C * := .

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

T₁ ¬ > BC

JFALSE T₁ L₂

T₂ ¬ > D E

JFALSE T₂ L₃

T₃ ¬ + B C

A ¬ T₃

JUMP L

L₃ : T₄ ¬ - B C

A ¬ T₄

JUMP L

L₂ : T₅ ¬ * B C

A ¬ T₅

Рис. 6.5