этого выражения:
а<A1>*<A2>b<A1><A3>+<A2>x<A1>*<A2>y<A1><A3><A3>
Действие А3 соответствует применению знака операции. Из
изложенного выше вытекает, что каждый вызов А3 соответствует
тому месту, где появился бы знак операции в постфиксной фор-
ме. Стек знаков опреаций, по существу, служит для формирова-
ния постфиксной нотации. Поэтому последовательность действий
при трансляции данного выражения должна быть следующей:
А1. Поместить статические характеристики а в нижний
стек.
А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
При генерации кода для такой условной зависимости во
время компиляции выполняются три действия. Грамматика с вклю-