Проектирование трансляторов
синтаксическому дереву. Для передачи же информации вниз по
дереву применяется так называемый верхний стек. Значение в
него помещается всякий раз, когда во время генерации кода
происходит вход в такую конструкцию, как присваивание или
описание идентификатора. При выходе из этой конструкции зна-
чение из стека удаляется. Следовательно, генератор кода может
заключить, например, что компилируемое выражение находится
справа от знака присваивания; эта информация способствует оп-
тимизации.
Еще одной структурой данных, которая требуется во время
генерации кода, является таблица блоков.
╔══════════╦═══════════╦═══════════════════╦═════════════════╗
║ Блок ║ Уровень ║ Размер стека ║ Размер рабочего ║
║ ║ блока ║ идентификаторов ║ ║
╠══════════╬═══════════╬═══════════════════╬═════════════════╣
║ 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
Действия А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. Поместить результат (при необходимости) в рамку стека
вызывающего блока.