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

Основными терминальными символами, из которых состоит промежуточ­ная программа, являются операторы и операнды. Различные формы представ­ления промежуточной программы различаются, в основном, способом соединения операторов и операндов. В общем случае состав операторов про­межуточного языка напоминает основные операторы машинного мнемокода, а операндами являются имена переменных, процедур, констант и т.д. из исход­ной программы и имена промежуточных переменных, меток и т.д., генерируе­мых самим компилятором. Внутри компилятора операторы представляются обычно числовыми кодами, а операнда — указателями на соответствующие элементы таблицы идентификаторов.

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

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

· тетрады;

· триады;

· связные списочные структуры и др.

Примеры таких представлений рассмотрим для программы, приведченной на рис. 4.6. В качестве языка, на котором будем записывать промежуточную программу, будем использовать язык, основные операторы которого приведе­ны в табл. 4.1 [11].

Постфиксная форма записи (польская инверсная запись — ПОЛИЗ), впервые примененная польским логиком Я. Лукашевичем, в отличие от обычной (инфикс­ной) записи просто и точно указывает порядок выполнения операций. Так, напри­мер, арифметическое выражение а + b*с + d в ПОЛИЗ будет выглядеть a b с * + d +. В ПОЛИЗ операторы следуют непосредственно за своими операндами, поэтому не нужны скобки и не нужно учитывать приоритеты операций (конечно приорите­ты учитываются, но на этапе построения ПОЛИЗ). Распространению ПОЛИЗ спо­собствовало то, что для них существует очень простой алгоритм интерпретации выражений: выражение просматривается слева направо, и элементы его помеща­ются в стек до тех пор, пока рассматриваемый элемент не знак операции. Если же это знак операции, то два верхних элемента (в случае двухместной операции) вы­талкиваются из стека, над ними выполняется операция, после чего результат поме­щается в стек, операция удаляется из входной строки и просмотр продолжается.

Рис. 4.6. Учебный пример Паскаль — программы

Ниже приведен пример вычисления выражения 2 3 * 4 + с использова­нием данного алгоритма.

СОДЕРЖИМОЕ МАГАЗИНА	ВХОДНАЯ СТРОКА
#	23*4 +
#2	3*4 +
#23	* 4 +
#6	4 +
#64	+
#10

В ранних компиляторах, использующих, так называемые «прямые методы трансляции», основные синтаксические единицы программы переводились в постфиксные выражения, а затем уже из ПОЛИЗ осуществлялся синтез объек­тной программы. С основными алгоритмами такого перевода можно ознако­миться в [16, 2].

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

· обход левого поддерева снизу;

· обход правого поддерева снизу;

· посещение корня.

Таблица 4.1 Основные операторы промежуточного языка

Оператор	Мнемокод	Операнды	Семантика оператора
Начало блока	BLOCK		Инициализирует действие генератора кода, связанные с входом в блок
Конец блока	BLKEND		Аналогично BLOCK, но при выходе из блока
Переход по условию = > < <= >=	BZ BP BM BMZ BPZ	M, P	Переход на М (М – метка, номер тетрады, или позиции символа в прграмме) при выполнении условия для значения из Р
Безусловный переход	BR	M	Безусловный переход на М (М – метка, номер тетрады, или позиции)
Вычислить адрес элемента массива	SUBS	I, J, A, R	Вычисляет адрес элемента массива А[I, J] и помещает в ячейку R, число аргументов может быть переменным
Арифметические операторы	+, -, *, /	R1, R2, R3	Выполнение арифметических операций над операндами R1 и R2, результат – в R3

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

if  <ВЫРАЖЕНИЕ> then <ОПЕРАТОР 1> else <ОПЕРАТОР 2>,

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

<ВЫРАЖЕНИЕ> <МЕТКА 1> BZ <ОПЕРАТОР 1>

<МЕТКА 2> BR <МЕТКА 1> <ОПЕРАТОР 2> <МЕТКА 2>

Рис. 4.7. Схемы выполнения условного оператора и оператора цикла

Здесь предполагается, что для любого выражения 0 означает ложь, а не 0 – истину, BZ – бинарная операция, которая осуществляет переход на <МЕТКА 1>, если значение <ВЫРАЖЕНИЕ> – ложь и BR – унарная операция, осуществляет безусловный переход на <МЕТКА 2>. Оператор цикла

for i:=1 to10 do <OПEPATOP>

в ПОЛИЗ будет выглядеть:

i 1 := <МЕТКА 1 > i 10 — <МЕТКА 2> ВР <ОПЕРАТОР> i i 1

+ := <МЕТКА 1 > BR <METKA 2>

Схема выполнения этого оператора цикла показана на рис. 4.7.

С учетом приведенных представлений для операторов условного перехода и цикла, польская запись программы, приведенной на рис. 4.6, будет иметь вид:

(1) BLOCK S1 0:=S20:=

(8) i 1 :=i 10 — 46ВР

(16) i A SUBS 0 — 32BMZ

(23) S1 S1 i A SUBS + := 39 BR

(32)S2 S2 i ASUBS + :=

(39)i i 1 + :=11 BR

(46)BLKEND

Здесь слева в скобках для каждой строки указаны номера позиций крайних левых символов строки, номер позиции используется и в операторах перехода в качестве

значений соответствующих меток.

Многоадресный код (тетрады). Другой метод кодирования синтаксичес­кого дерева программы — применение многоадресного кода. Удобной фор­мой представления является тетрада — код с явно именуемыми результатами операторов:

<операция>, <операнд1>, <операнд2>, <результат>.

Таким образом, выражение a+b*c+d можно представить в виде следующей последовательности тетрад:

*, b, c, t1

+, a, t1, t2

+, t2, d, t3

Здесь tl, t2 и t3 соответствуют промежуточным переменным, генерируе­мым компилятором. Представление в виде многоадресного кода, в данном случае трехадресного, удобно для фазы оптимизации, так как внести изме­нения здесь значительно проще, чем в польское представление промежу­точной программы.

Представление программы, приведенной на рис. 4.6, в виде последователь­ности тетрад будет иметь вид:

(1) (1) BLOCK                                                                        (9) +, t3, S1, S1

(2) :=, 0, , S1                                                                            (10) BR 13

(3) :=, 0, , S1                                                                            (11) SUBS, i, A, t4

(4) –, i, 10, t1                                                                           (12) +, t4, S2, S2

(5) BP, 15, t1                                                                           (13) +, i, 1, i

(6) SUBS, i, A, t2                                                                     (14) BR, 4

(7) BMZ, 11, t2                                                                        (15) BLKEND

(8) SUBS, i, A, t3

В качестве меток в операторах перехода здесь используются номера соот­ветствующих тетрад.

С другими формами представления промежуточной программы можно по­знакомиться в работах [11, 9]. На практике обычно используется некоторое смешанное представление, зависящее, как отмечается в [11], от личных жела­ний и склонностей разработчика компилятора.