Смекни!
smekni.com

Проектирование трансляторов (стр. 21 из 31)

│ 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>

В тетраде отсутствует поле результата. Если позже какой-ли-

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

нее непосредственно ссылаться.

Существуют и другие формы внутреннего представления.