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

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

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

стек.

А2. Поместить знак "*" в стек знаков операций.

А1. Поместить статические характеристики b в нижний

стек.

А3. Извлечь статические характеристики a и b из ниж-

него стека и знак "*" из стека знаков операций, генерировать

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

рактеристики результата в нижний стек; тип результата - целый.

А2. Поместить знак "+" в стек знаков операций.

А1. Поместить статические характеристики х в нижний

стек.

А2. Поместить знак "*" в стек знаков операций.

А1. Поместить статические характеристики у в нижний

стек.

А3. Извлечь статические характеристики х и у из ниж-

него стека и знак "*" из стека знаков операций, генерировать

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

рактеристики результата в нижний стек; тип результата - ве-

щественный.

А3. Извлечь два верхних элемента из нижнего стека и знак

"+" из стека знаков операций, генерировать код для сложения

целого и вещественного значений, поместить статические харак-

теристики результата в нижний стек; тип результата - вещест-

венный.

Действия А1, А2, А3 и вышеприведенную грамматику легко

расширить, что позволит использовать

а) большее число уровней приоритета для знаков операций;

б) унарные знаки операций.

Другие случаи употребления нижнего стека рассматриваются

в следующем разделе.

Нижний стек обеспечивает передачу информации вверх по

синтаксическому дереву. Для передачи же информации вниз по

дереву применяется так называемый верхний стек. Значение в

него помещается всякий раз, когда во время генерации кода

происходит вход в такую конструкцию, как присваивание или

описание идентификатора. При выходе из этой конструкции зна-

чение из стека удаляется. Следовательно, генератор кода может

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

справа от знака присваивания; эта информация способствует оп-

тимизации.

Еще одной структурой данных, которая требуется во время

генерации кода, является таблица блоков.

╔══════════╦═══════════╦═══════════════════╦═════════════════╗

║ Блок ║ Уровень ║ Размер стека ║ Размер рабочего ║

║ ║ блока ║ идентификаторов ║ ║

╠══════════╬═══════════╬═══════════════════╬═════════════════╣

║ 1 ║ 1 ║ 14 ║ 16 ║

║ 2 ║ 2 ║ 12 ║ 11 ║

║ 3 ║ 2 ║ 21 ║ 13 ║

║ 4 ║ 3 ║ 4 ║ 9 ║

║ 5 ║ 2 ║ 6 ║ 12 ║

╚══════════╩═══════════╩═══════════════════╩═════════════════╝

В этой таблице есть запись для каждого блока программы,

и эту запись можно рассматривать как структуру, имеющуюю по-

ля, которые соответствуют номеру уровня блока, размеру стати-

ческого стека идентификаторов, размеру статического рабочего

стека и т.д. Такую таблицу можно заполнять во время прохода,

генерирующего код, и с ее помощью в следующем проходе вычис-

лять смещения адресов рабочего стека по отношению к текущей

рамке стека.

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

дующие основные структуры данных: нижний стек, верхний стек,

стек знаков операций, таблица блоков и, кроме того, таблица

видов и таблица символов из предыдущих проходов.

Генерация команд

По существу, на этом этапе происходит перевод внутреннего

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

язык.

Возможны три формы об'ектного кода: абсолютные команды, по-

мещенные в фиксированные ячейки; программа на автокоде; програма

на языке машины, предтавленная образами карт и записанная во

вторичную память.

Рассмотрим выражение (A + B) + (X + Y)

Очевидный способ его вычисления в терминах машинного языка

таков:

1. загрузить А в сумматор;

2. прибавить B к сумматору;

3. записать результат A+B во временную рабочую ячейку;

4. загрузить X в сумматор; 5. прибавить Y к сумматору;

6. прибавить временный результат A+B к X+Y в сумматоре.

Каждому из трех сложений предшествует своя последователь-

ность команд загрузки и записи.

Чтобы построить код генератор хранит некоторую информацию о

том, что будет происходить в период исполнения генерируемого им

кода.

При разработке генератора кода первый шаг заключается в

том, что чтобы определить, как будет организована память машины

в перид исполнения скомпилированной прграммы. Предлагаемое расп-

ределение памяти показано на рисунке

----------------------

! Программа !

----------------------

! Константы !

----------------------

! Подпрограммный !

! стек !

----------------------

! Промежуточные !

! результаты !

----------------------

! Хранимые результаты!

----------------------

! Переменные !

----------------------

Область ПРОГРАММА содержит команды об'ектной программы.

ПОДПРОГРАММНЫЙ СТЕК используется для хранения адресов возврата

подпрограмм. Область ХРАНИМЫЕ РЕЗУЛЬТАТЫ используется для хране-

ния результатов атома ХРАНЕНИЕ в FOR-операторах. В областях

КОНСТАНТЫ и ПЕРЕМЕННЫЕ хранятся соответственно значения констант

и переменных.

Область ВРЕМЕННЫЕ РЕЗУЛЬТАТЫ используется для хранения про-

межуточных результатов.

Генератор кода использует табличные эдементы для хранения

информации о параметрах атомов. Каждый табдичный элемент имеет

поле ВИД, указывающее вид об'екта, описываемого этим элементом,

а также одно или два других поля. Поле ВИД содержит одно из сле-

дующих пяти значений: КОНСТАНТА, ПЕРЕМЕННАЯ, ПРОМЕЖУТОЧНЫЙ РЕ-

ЗУЛЬТАТ, ХРАНИМЫЙ РЕЗУЛЬТАТ или МЕТКА.

Мы предполагаем, что генератор кода содержит процедуру, на-

зываемую ГЕН, которая строит двоичное представление генерируемой

команды. ГЕН вызывается с двумя параметрами: кодом операции и

указателем на табличный элемент, соответствующий полю адреса ге-

нерируемой команды. Процедура ГЕН выполняет следующие действия:

1. Формируется двоичный код, соответствующий первому

параметру процедуры ГЕН.

2. Формируется двоичный код, соответствующий второму

параметру процедуры ГЕН.

3. Двоичный код, образующий сгенерированную команду,

помещается в ячейку, соответствующую текущему зна-

чению СЧЕТКОМ.

4. СЧЕТКОМ увеличивается и сравнивается с ГРАНКОМ.

Здесь СЧЕТКОМ и ГРАНКОМ - переменные периода компиляции.

Генерация кода для некоторых типичных конструктов

Покажем, как генерируеися код для некоторых конструктов,

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

I. Присваивания

В соответствии с терминологией Алгола 68 присвамвание

имеет вид

destination := source

Смысл его состоит в том, что значение, соответствующее

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

( или именем ), заданным получателем. Например, в

p := x + y

значение "х+у" присваивается р.

Допустим, что статические характеристики источника и по-

лучателя уже находятся в вершине нижнего стека. Опишем дейс-

твия, выполняемые во время компиляции для осуществления прис-

ваивания. Прежде всего из нижнего стека удаляются два верхних

элемента, после чего происходит следующее:

1. Проверяется непртиворечивость типов получателя и ис-

точника. Так как получатель представляет собой адрес, источ-

ник должен давать что-нибудь приемлемое для присваивания это-

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

получателя и источника можно определенным образом изменять до

выполнения присваивания. Например, если тип источника - целое

число, то его можно сначала преобразовать в вещественное, а

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

2. Там, где это необходимо, проверяются правила области

действия. В Алголе 68 источник не может иметь меньшую область

действия, чем получатель. Например, в

begin ref real xx;

begin real x;

xx := x

end

присваивание недопустимо, и это может быть обнаружено во вре-

мя компиляции, если в таблице символов или в нижнем стеке

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

компиляции нельзя обнаружить все нарушения правил области

действия, и в некоторых случаях для проверки этой области

приходится создавть код во время прогона.

3. Генерируется код для присваивания, имеющий форму

ASSIGN type,S,D

где S - адрес источника, а D - адрес получателя.

4. Если язык ориентирован на выражения ( то есть само

присвоение имеет значение ), статические характеристики этого

значения помещаются в нижний стек.

II. Условные зависимости

Почти все языки содержат условное выражение или опера-

тор, аналогичный следующему:

if B then C else D fi

При генерации кода для такой условной зависимости во

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

ченными действиями:

CONDITIONAL -> if B then C else D fi

Действия А1, А2 и А3 означают (next - значение номера

следующей метки, присваиваемое компилятором):

А1. Проверить тип В, применяя любые необходимые преобра-

зования (приведения) типа для получения логического значения.

Выдать код для перехода к L, если В есть "ложь":

JUMPF L,

Поместить в стек значение next ( обычно для этого служит

стек знаков операций ). Увеличить next на 1. (Угловые скобки

(), в которые заключаются "next" и "address of B", исполь-

зуются для обозначения значений этих величин, и их не следует

путать со скобками, в которые заключаются действия в порожда-

ющих правилах грамматики.)

А2. Генерировать код для перехода через ветвь else (

т.е. перехода к концу условной зависимости )

GOTO L

Удалить из стека номер метки ( помещенный в стек дейс-

твием А1 ), назвать i, генерировать код для размещения метки

SETLEBEL L

Поместить в стек значение next. Увеличить next на 1.

А3. Удалить из стека номер метки (j). Генерировать код

для размещения метки

SETLABEL L

Если условная зависимость сама является выражением ( а

не оператором ), компилятор должен знать, где хранить его

значение, независимо от того, какая часть вычисляется - then

или else. Это можно сделать, специфицируя адрес, который ука-

зывает на данное значение, или пересылая значение, заданное

частью then либо частью else, по указанному адресу.

Аналогично можно обращаться с вложенными условными выра-

жениями или операторами.

III. Описания идентификаторов

Допустим, что типы всех идентификаторов полностью выяс-

нены в предыдущем проходе и помещены в таблицу символов. Ад-

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

Рассмотрим описание

somemode x

еречислим действия, выполняемые во время компиляции:

1. В таблице символов производится поиск записи, соот-

ветствующей x.

2. Текущее значение указателя стека идентификаторов дает

адрес, который нужно выделить для x. Этот адрес

(idstack, current block number, idstack pointer)

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

торов увеличивается на статический размер значения, соответс-

твующего х. (В Алголе 68, если вид х начинается с ref, обьем

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

х, а не для самого х; это обозначается с помощью адреса дру-

гого типа. )

3. Если х имеет динамическую часть, например в случае

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

мяти во время прогона.

IV. Вход и выход из блока

При входе в блок ( последовательное предложение с описа-

ниями в Алгол 68 ) предположим, что во время предыдущего про-

хода получена определенная информация. Она состоит из таблиц

видов и символов, дающих типы или виды всех идентификаторов и

т.п. Тогда при входе в блок нужно выполнить следующие основ-

ные действия:

1. Прочитать в таблице символов информацию, касающуюся

блока, и связать ее с информацией включающих блоков таким об-

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

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