Проектирование трансляторов

информации вверх по

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

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

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

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

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

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

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

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

тимизации.

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

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


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

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

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

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

║ 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. Прочитать в таблице символов информацию, касающуюся

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

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

щих реализаций идентификаторов и т.д.

2. Поместить в стек (idstack pointer). Поместить в стек

(wostack pointer). Поместить в стек (block number). Все эти

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

вновь после того, как будет покинуть блок, в который только

что осуществлен вход:


idstack pointer := 0

wostack pointer := 0


3. Генерировать код для исправления DISPLAY


BLOCK ENTRY block number


4. Увеличить номер уровня блока на 1. Увеличить наиболь-

ший использованный до сих пор номер блока на 1 и присвоить

это значение номеру блока.

5. Прочитать информацию о виде и добавить ее в таблицу

видов ( если в языке имеются такие "сложные" виды, как в Ал-

голе 68 ).

При выходе из блока требуется:

1. Обновить таблицу блоков, задав размер стека идентифи-

каторов и т.п. для покинутого блока.

2. Исключить информацию в виде таблицы символов для по-

кинутого блока.

3. Генерировать код для изменения дисплея


BLOCK EXIT block number


4. Удалить из стека (block number). Удалить из стека

(wostack pointer). Удалить из стека (idstack pointer). Умень-

шить номер уровня на 1.

5. Поместить результат (при необходимости) в рамку стека

вызывающего блока.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

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

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: