Реферат: Проектирование трансляторов
дереву применяется так называемый верхний стек. Значение в
него помещается всякий раз, когда во время генерации кода
происходит вход в такую конструкцию, как присваивание или
описание идентификатора. При выходе из этой конструкции зна-
чение из стека удаляется. Следовательно, генератор кода может
заключить, например, что компилируемое выражение находится
справа от знака присваивания; эта информация способствует оп-
тимизации.
Еще одной структурой данных, которая требуется во время
генерации кода, является таблица блоков.
╔══════════╦═══════════╦═══════════════════╦═════════════════╗
║ Блок ║ Уровень ║ Размер стека ║ Размер рабочего ║
║ ║ блока ║ идентификаторов ║ ║
╠══════════╬═══════════╬═══════════════════╬═════════════════╣
║ 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
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40
