│ 21 │ 16 │ │ - │ 53 │ 2 │ 1 │ I │
├────┼────┼────┼───────┼────┼────┼────┼────────┤
│ 22 │ 1 │ 45 │ 45 │ 55 │ 2 │ 1 │ I │
├────┼────┼────┼───────┼────┼────┼────┼────────┤
│ 24 │ 8 │ │ BMZ │ 57 │ 1 │ 1 │ 1 │
├────┼────┼────┼───────┼────┼────┼────┼────────┤
│ 25 │ 2 │ 4 │ K │ 59 │ 14 │ │ + │
├────┼────┼────┼───────┼────┼────┼────┼────────┤
│ 27 │ 2 │ 4 │ K │ 60 │ 7 │ │ := │
├────┼────┼────┼───────┼────┼────┼────┼────────┤
│ 29 │ 2 │ 1 │ I │ 61 │ 1 │ 5 │ 5 │
├────┼────┼────┼───────┼────┼────┼────┼────────┤
│ 31 │ 2 │ 2 │ 7 │ 63 │ 10 │ │ BRL │
├────┼────┼────┼───────┼────┼────┼────┼────────┤
│ 33 │ 16 │ │ - │ 64 │ 12 │ │ BLCEND │
├────┼────┼────┼───────┼────┼────┼────┼────────┤
│ 34 │ 2 │ 3 │ A │ │ │ │ │
└────┴────┴────┴───────┴────┴────┴────┴────────┘
Внутреннее представление польской записи
- операторы занимают по одной ячейке и представлены числами:
6 = SUBS, 7 = :=, 8 = BMZ, 9 = BR, 10 = BRL, 11 = BLOCK,
12 = BLCKEND, 13 = ADEC, 14 = +, 15 = *, 16 = -.
Константа занимает два слова: первое 1, второе - значение
ее. Для идентификатора аналогично: первое слово 2, второе - ад-
рес (индекс) элемента таблицы символов идентификатора.
Метки, генерируемые для внутренних переходов равны соот-
ветств. номерам ячеек.
ТЕТРАДЫ.
1) Арифметические выражения:
(<оператор>,<операнд1>,<операнд2>,<результат>)
т.о. 1. А * В => *,А,В,Т, где Т некоторая переменная, кото-
рой присваивает результат вычисления А * В.
2. А * В + С * D => *, A, B, T1 ┐ тетрады располагаются в
*, C, D, T2 ├ том порядке, в котором
+, T1, T2, T3 ┘ они должны вычисляться
Для унарных операторов (-А) <операнд2> остается пустым
(-,А, ,Т) 2)
2) Тетрады для других операторов.
1] BR i - переход на i-ю тетраду
2] BZ i,P - переход по "0" (BP - по "+", BM - по "-")
3] BG i, P1, P2 - переход, если значение в P1 > чем в P2
( BL - < , BE - = )
4] BRL P - переход на тетраду, номер которой в Р-м
элементе таблицы символов
5] +[*,/,-] P1, P2, P3
6] := P1, ,P3
7] CVRI P1, ,P3 - преобразование значения, описанного в Р1,
из REAL в INT и запоминание в Р3
8] BLOCK
9] BLCKEND
10] BOUNDS P1, P2 - Р1 и Р2 описывают граничную пару массива
11] ADEC P1 - массив описан в Р1. Если он имеет размер-
ность n, то этой тетраде предшествует опе-
ратор BOUNDS, задающий n граничных пар.
ИНДЕКСИРОВАНИЕ
Пример С := А [i, B[j]], если d1
описывает диапазон изменения *, ,d1,T1
второго индекса массива А, то +,T1,B[j],T2
получим следующее представление :=,A[T2], ,C
(1) BLOCK (10) + K,T4,T5
(2) -I,j,T1 (11) := T5, , K
(3) BOUNDSI,T1 (12) BR18
(4) ADEC A (13) +I,1,T6
(5) := 0, ,K (14) := T6, ,I
(6) -I,j,T2 (15) +I,1,T7
(7) BMZ13,T2 (16) := T7, ,I
(8) -I,j,T3 (17) BRL L
(9) *A[T3],6,T4 (18) BLCKEND
ТРИАДЫ
<оператор><операнд1><операнд2>
В ней нет поля результата. За счет этого сокращается запись
и количество временных переменных. При обработке триады, ре-
зультат которой будет в дальнейшем использоваться, генератор ко-
да должен сгенерировать описание ее результата, которое уничто-
жается после его использования.
(1) BLOCK (10) + K,(9)
(2) -I,j (11) := (10), K
(3) BOUNDS 1,(2) (12) BR (18)
(4) ADEC A (13) + I, 1
(5) := 0,K (14) := (13), I
(6) -I,j (15) + I, 1
(7) BMZ(13),(6) (16) := (15), I
(8) -I,j (17) BRL L
(9) * A[(8)],(6) (18) BLCKEND
Здесь (2) - ссылка на результат второй триады. Компилятор
заводит новый тип операнда для результата триад (первое слово
операнда)
ДЕРЕВЬЯ
Для любого арифметического выражения можно построить дерево,
корню которого соответствует последняя триада. Каждая i-я триада
соответствует поддереву, оператор триады - корень поддерева, опе-
ранд - либо идентификатор(лист), либо номер триады, описывающий
поддерево. От того, как рассматриваются триады (как последова-
тельность операций в порядке их выполнения или как дерево), су-
щественным образом зависит генерируемый объектный код. Дерево
иногда позволяет сгенерировать более эффективный объектный код.
Пример 1. A * B + C - D * E
-
┌───┴───┐ (1) ( * A,B )
+ * (2) ( + (1),C )
┌──┴──┐ ┌──┴──┐ (3) ( * D,E )
* C D E (4) ( - (2),(3) )
┌──┴──┐
A B
Пример 2 BEGIN A := B; B := C; D := C; END
<составная инстр.>
┌───────────────────────┼───────────────────────┐
BEGIN <список инстр.> END
┌─────────┬──────────┬──────────┐
<инстр.> <инстр.> <инстр.> <инстр.>
Дерево │ │ │ │ Триады
-------- := := := <пусто> --------
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ (1) (:=B,A)
A B B C D C (2) (:=C,B)
(3) (:=C,D)
При представлении инструкций, блоков, описаний и т.д. триа-
ды не образуют уже полного дерева, т.к. связи между различными
инструкциями и описаниями явно не заданы.
В дереве отражены прямые связи (указатели) с инструкциями, в
то время как в триадах эти связи подразумеваются.
Промежуточная форма исходной программы
Первоначальная исходная программа переводится в некоторую
внутреннюю форму, удобную для простой машинной обработки. Внут-
реннее представление исохдной программы в значительной степени
зависит от дальнейшего использования. Это может быть дерево, от-
ражающее синтаксис исходной программы. Это может быть исходная
программа в польской записи. Используется также форма - список
тетрад (операнд, операнд, операнд, результат) в порядке их выпол-
нения.
После синтаксического анализа можно считать, что исходная
программа преобразована в дерево, называемое синтаксическим. В
этом дереве внутренние вершины в основном соответствуют опера-
циям, а листья представляют операнды, состаящие из указателей
входов в таблицу имен. Структура синтаксического дерева отражает
синтаксические языка программирования, на котором написана исход-
ная программа. Для физического представления существует нес-
колько способов. Во внутренней форме операторы не изменяют поря-
док следования. Все внутренние представления обычно содержат 2
вещи: операторы и операнды. Различие состоит в том, как эти опе-
раторы и операнды соединяются.
Промежуточная программа должна отражать синтаксическую
структуру исходной программы. Операндами являются простые имена
(переменные, константы, процедуры и т.д.). Компиляторы, осущес-
твляющие значительную работу по оптимизации кода, создают де-
тальное представление промежуточной программы, точно описывающее
порядок выполнения исходной программы. В других компиляторах
представлением промежуточной программы служит простое представле-
ние синтаксического дерева, такое как польская запись.
Польская запись
Для представления арифметических и логических выражений ис-
пользуется польская запись. Она имеет ряд преимуществ перед ин-
фиксной: формула может быть записана без скобок; эта форма пред-
ставления очень удобна для ЭВМ со стековой адресацией; если зна-
ки операций в инфиксной форие различаются по старшинству, то
польская запись устраняет эту систему приоритетов).
В польской записи операнды следуют непосредственно за опера-
торами. Вычисление таких записей производится с помощью стека,
где будут находиться все операнды, встретившиеся при просмотре
выражения.
Просмотр начинается с самого левого символа. Прочитав его и
обработав, переходим к следующему. Последовательность обработки
такова:
1) если сканирующий символ - идентификатор или константа, то
его значение заносится в стек и осуществляется переход к следую-
щему;
2) если сканирующий символ-бинарный оператор, то он приме-
няется к двум верхним операндам в стеке и затем они заменяются на
полученный результат;
3) если сканирующий символ - унарный оператор, то он приме-
няется к верхнему операнду в стеке, который затем заменяется на
полученный результат.
Тетрады
Для бинарных операций удобной формой представления являются
тетрады. Тетрада имеет вид: <оператор> <операнд1> <операнд2>
В тетраде отсутствует поле результата. Если позже какой-ли-
бо операнд окажется результатом данной операции, то он будет на
нее непосредственно ссылаться.
Существуют и другие формы внутреннего представления.