46023 (665330), страница 15

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

└───┴───┴─────────────────────────────────────┘

Перменная с индексами

┌───┬───┬─────────────────┬───┬───┬───────────────┐

│ 4 │ I │ ук-ль на эл-т │ х │ I │ ук-ль на эл-т │

│ │ │ с именем массива│ │ │ с индексом │

└───┴───┴─────────────────┴───┴───┴───────────────┘

┌─────────────────────────┘

│ описание индексов

х = 1 - указатель на табл. символов

2 - указатель на табл. констант

3 - указатель на табл. временных переменных

Форматы операндов

Польская запись

1.Польский логик Я.Лукашевич впервые применил запись арифмети-

ческих и логических выражений, которая без скобок указывает точ-

ный порядок выполнения операций. В ней операторы следуют непос-

редственно за операндами (постфиксная запись). Она определяется

следующими правилами:

1) операнды следуют в том же порядке, как они представлены в

префиксной записи;

2) операторы следуют в том же порядке, в каком они должны

вычисляться (слева направо);

3) опер-ры располаг-ся непосредственно за своими оп-дами.

Это можно представить следующими правилами: <операн-

д>::=|

::= + | - | / | * | ... Для унарных оперций можно

ввести новый символ ( например @ для -) и еще одно правило

::=@ Пример A * ( B + C / D ) ABCD / + *

A + ( -B + C * D ) AB@CD * + +

(C таким же успехом можно применять префиксную запись).

Вычисление арифметических выражений

Данные правила определяют порядок обработки выражения с по-

мощью стека за один просмотр выражения слева направо, начиная с

самого левого символа входной цепочки:

1. Если сканируемый символ идентификатор, то его значение

заносим в стек и переходим к следующему символу (правило <оп-

реанд>::= идентификатор)

2. Если сканируемый символ - бинарный оператор, он приме-

няется к двум верхним операндам в стеке и замещает их на получен-

ный результат, что эквивалентно правилу ::= <о-

перанд>.

3. Если сканируемый символ - унарный оператор, то он приме-

няется к верхнему символу стека и затем замещает его результатом

(правило ::= [ Д/З - стр.282 ]

Включение в польскую запись других операторов

1) Присваивание ::= ( := )

прим.: А := В * С + D АВС * D + :=

- После выполнения оператора := из стека исключаются и

, т.к. этот оператор не имеет результирующего значения в

отличие от бинарных арифметических операторов.

- Кроме того, в стеке находится не значение (оно нам

не нужно), а ее адрес, т.к. в рез-те присвоения по нему заносит-

ся значение

2) Оператор GOTO А A BRL,

где метка А представлена адресом соответствующего ей эл-та

таблицы символов. Оператор BRL (Branch to label)

3) Условные переходы

BP, где первый операнд является значе-

нием арифметического выражения, второй указывает номер (место)

символа в цепочке польской записи. Если операнд1 положителен

(positive), то в качестве следующего берется символ, на который

указывает операнд2, иначе работа продолжается как обычно.

BP - переход по положительному значению, ВМ - по минусу, BZ

- по нулю, BPZ - по неотрицательному значению, и т.д.

4) Условная инструкция

IFTHENELSEBZBR

С1 - номер имвола, с которого начинается .

С2 - номер символа,следующего за .

Операторы BZ и BR не порождают результирующего значения.

Часть их работы состоит в исключении из стека двух верхних эле-

ментов (значения и ) для BZ и соответственно одного

для BR. Оператор безусловного перехода BR - использует-

ся метка для внутренних генерируемых переходов. В то время

как оператор BRL в качестве значения использует

адрес эл-та таблицы символов.

5) Описание массива. ARRAY A[Li:Ui,...,Ln:Un]

можно представить в виде:

LiUi...LnUn A ADEC, где ADEC - оператор, имеющий переменное

число операндов, зависящее от числа индексов. Операнд А - оче-

видно, адрес элемента таблицы символов для А -> При вычислении

ADEC, следовательно, из этого элемента таблицы извлекается ин-

формация о размерности массива А (т.е. и о числе операндов ADEC)

- с этой целью изменен порядок записи операндов.

6) Переменная с индексами A[,...,] преставляется

в виде ... A SUBS

Оператор SUBS используя элемент А таблицы символов и ин-

дексные выражения, вычисляет адрес элемента массива. Затем опе-

ранды исключаются из стека и на их место заносится новый опе-

ранд, определяемый адресом элемента массива и его типом.

Использование для индексирования специального оператора

SUBS - более удобный способ для польской записи.

Пример: BEGIN INTEGER K; ARRAY[1:I-j]; K:=0;

L:IF I>j THEN K:=K+A[I-j]*6 ELSE

BEGIN I:=I+1;I:=I+1;COTOL END

END

(1) BLOCK 1 IJ - A ADEC K0 := Польская запись

(11) IJ - 29 BMZ

(16) K KIJ - A SUBS 6*+:= 41 BR Для каждого символа отво-

(29) II1 + := II1 + := L BRL дится одна строка (место)

(41) BLCEND

Как видно, описание INTEGER K (не требующее генерации ко-

манд) отсутствует во внутреннем представлении. Оно нужно для

формирования элемента таблицы символов для К.

Введены два оператора без операндов BLOCK (начало блока) и

BLCKEND (конец блока).

N содерж. N содерж. таблица

слова слова символ слова слова символ символов

┌────┬────┬────┬───────┬────┬────┬────┬────────┬───┬─────┐

│ 1 │ 11 │ │ BLOCK │ 36 │ 6 │ │ SUBS │ 1 │ I │

├────┼────┼────┼───────┼────┼────┼────┼────────┼───┼─────┤

│ 2 │ 1 │ 1 │ 1 │ 37 │ 1 │ 6 │ 6 │ 2 │ Y │

├────┼────┼────┼───────┼────┼────┼────┼────────┼───┼─────┤

│ 4 │ 2 │ 1 │ I │ 39 │ 15 │ │ * │ 3 │ A │

├────┼────┼────┼───────┼────┼────┼────┼────────┼───┼─────┤

│ 6 │ 2 │ 2 │ Y │ 40 │ 14 │ │ + │ 4 │ K │

├────┼────┼────┼───────┼────┼────┼────┼────────┼───┼─────┤

│ 8 │ 16 │ │ - │ 41 │ 7 │ │ := │ 5 │ L25 │

├────┼────┼────┼───────┼────┼────┼────┼────────┼───┴─────┘

│ 9 │ 2 │ 3 │ A │ 42 │ 1 │ 64 │ 64 │

├────┼────┼────┼───────┼────┼────┼────┼────────┤

│ 11 │ 13 │ │ ADEC │ 44 │ 9 │ │ BR │

├────┼────┼────┼───────┼────┼────┼────┼────────┤

│ 12 │ 2 │ 4 │ K │ 45 │ 2 │ 1 │ I │

├────┼────┼────┼───────┼────┼────┼────┼────────┤

│ 14 │ 1 │ 0 │ 0 │ 47 │ 2 │ 1 │ I │

├────┼────┼────┼───────┼────┼────┼────┼────────┤

│ 16 │ 7 │ │ := │ 49 │ 1 │ 1 │ 1 │

├────┼────┼────┼───────┼────┼────┼────┼────────┤

│ 17 │ 2 │ 1 │ I │ 51 │ 14 │ │ + │

├────┼────┼────┼───────┼────┼────┼────┼────────┤

│ 19 │ 2 │ 2 │ Y │ 52 │ 7 │ │ := │

├────┼────┼────┼───────┼────┼────┼────┼────────┤

│ 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. А * В + С * D => *, A, B, T1 ┐ тетрады располагаются в

*, C, D, T2 ├ том порядке, в котором

+, T1, T2, T3 ┘ они должны вычисляться

Для унарных операторов (-А) остается пустым

(-,А, ,Т) 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) 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

вещи: операторы и операнды. Различие состоит в том, как эти опе-

раторы и операнды соединяются.

Промежуточная программа должна отражать синтаксическую

структуру исходной программы. Операндами являются простые имена

(переменные, константы, процедуры и т.д.). Компиляторы, осущес-

твляющие значительную работу по оптимизации кода, создают де-

тальное представление промежуточной программы, точно описывающее

порядок выполнения исходной программы. В других компиляторах

представлением промежуточной программы служит простое представле-

ние синтаксического дерева, такое как польская запись.

Польская запись

Для представления арифметических и логических выражений ис-

Характеристики

Список файлов реферата