А * В + С * D => *, A, B, T1 ┐ тетрады располагаются в

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>

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

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

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

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

Деревья

Мы опpеделили КС-язык, задаваемые некотоpой гpамматикой, как

множество теpминальных цепочек, котоpые можно вывести из на-

чального символа. Можно постpоить деpево вывода цепочки КСязыка.

Это легко сделать, интеpпpетиpуя подстановки, как шаги постpое-

ния деpева.Однако деpево не несет никакой инфоpмации о поpядке

пpименеия пpавил, кpоме того что пpавила должны пpименяться к

каждой веpшине деpева pаньше, чем к нетеpминальным веpшинам pас-

положенным ниже. Поскольку поpядок вывода в деpеве скpыт, то мо-

жет быть несколько выводов, соответствующих одному и тому же

деpеву вывода. Для каждого деpева существует единственный левый и

единственный пpавый вывод, котоpый получается, если всегда заме-

нять самый пpавый нетеpминал. Многие методы обpаботки языков pас-

читаны исключительно на левые или пpавые выводы,так как они очень

удобны для семантической обpаботки. Когда одна цепочка может

иметь несколько деpевьев вывода, говоpят, что соответствующая

гpамматика неоднозначна. Все сказанное можно pезюмиpовать следую-

щим обpазом:

1. Каждой цепочке, вводимой в данной КС-гpамматике, соответ-

ствует одно или несколько деpевьев вывода.

2. Каждому деpеву соответствует один или несколько выводов.

3. Каждому деpеву соответствует один пpавый и один левый вы-

вод.

4. Если каждой цепочке, вводимой в КС-гpамматике, соответ-

ствует единственное деpево вывода, эта гpамматика называется од-

нозначной; в пpотивном случае ее называют неоднозначной.

ЛЕКЦИЯ 14

ОПТИМИЗАЦИЯ ПРОГРАММЫ

Улучшение выходной программы обычно называют ее оптимиза-

цией, а часть транслятора, выполняющая эту функцию - отимизирую-

щей частью транслятора.

Оптимизирующая часть транслятора:

Похожие работы

Программное обеспечение удалённого доступа к технической документации

Скачать

84334

30

0

... работы. В ходе работы над дипломным проектом разработан транслятор. Проблема создания такого транслятора является очень актуальной, т.к. многим пользователям САПР необходимо доступ к технической документацию, которую удобнее хранить на удаленных серверах в формате HTML. Поэтому степень положительного эффекта от выполнения дипломного проекта научно-исследовательского характера 1=6.5. В ...

Андрей Петрович Ершов (1931-1988)

Скачать

50249

0

1

... направления, активно развиваемого сейчас в разных коллективах и странах. Отталкиваясь от трансформационной модели смешанных вычислений и от своих работ в области трансляции и оптимизации программ, Ершов определяет концепцию трансформационной машины. Трансформационная машина есть абстрактное вычислительное устройство, выполняющее программы в некотором "сверхязыке", действиями которого являются ...

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

Скачать

36295

1

7

... 166, 16 Mb RAM, Windows 95 Вывод   В ходе разработки курсового проекта я ближе ознакомился с теорией МП- трансляторов, научился писать программы - конструкторы для построения МП – транслятора по его параметрам с последующей проверкой задаваемых цепочек, закрепил знания по системному программированию. Разрабатывая программу, я научился применять знания дискретной математике, что облегчает ...

Технологии проектирования в инженерных средах

Скачать

141647

0

0

... позволяет связывать твёрдотельные модели, сборки или чертежи, созданные с помощью SolidWorks 97, с файлами других приложений, что значительно расширяет возможности автоматизации процесса проектирования. С помощью технологии OLE можно использовать информацию, полученную в других приложениях Windows, для управления моделями и чертежами SolidWorks. Например, размеры модели могут быть рассчитаны в ...