Теория языков программирования методов трансляции (стр. 43 )

Этот процесс можно распространить на более сложные выражения, например, на грамматики с правилами.

Для данных правил после чтения идентификатора или константы, знака операции и второго операнда необходимо выполнить следующие действия.

A1. После чтения идентификатора или константы (т. е. листа синтаксического дерева) поместить в нижний стек соответствующие характеристики.

A2. После чтения оператора поместить символ операции в стек знаков операций.

A3. После чтения правого операнда (который может быть выражением) извлечь из стеков знак операции и два его операнда, генерировать соответствующий код, т. к. знак операции идентифицирован, и поместить в нижний стек статические характеристики результата. Тип результата становится известным во время идентификации знака операции (например, сложение двух целых чисел дает целое число).

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

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

Рассмотрим дерево для (рис. 9.2).

 

Рис. 9.2. Синтаксическое дерево для арифметического выражения

Если значения a и b имеют тип целого, а x, y-тип вещественного значения, компилятор может заключить, воспользовавшись информацией нижнего стека, что «+» вершины дерева представляет собой сложение целого и вещественного. Мы можем переписать выражение, расставив действия A1, A2 и A3 в том порядке, в каком они будут возникать при трансляции выражения.

a<A1>´<A2>b<A1><A3>+<A2>x<A1>´<A2>y<A1><A3><A3>.

Каждый вызов A3 соответствует тому месту, где появился знак операции в постфиксной форме. Стек знаков операций служит для формирования постфиксной нотации. Поэтому последовательность действий при трансляции данного выражения должна быть следующей.

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

A2. Поместить знак «´» в стек знаков.

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

A3. Извлечь статические характеристики a и b из нижнего стека и знак «´» из стека знаков операций, генерировать код для умножения двух целых чисел, поместить статические характеристики результата в нижний стек; тип результата - целый.

A2. Поместить знак «+» в стек знаков.

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

A2. Поместить знак «´» в стек знаков операций.

A1. Поместить статическую характеристику y в нижний стек.

A3. Извлечь статические характеристики x и y из нижнего стека и знак «´» из стека знаков операций, генерировать код умножения двух вещественных чисел, поместить статические характеристики результата в нижний стек; тип результата - вещественный.

A3. Извлечь два верхних элемента из нижнего стека и знак «+» из стека знаков операций, генерировать код сложения целого и вещественного значений, поместить статические характеристики результата в нижний стек; тип результата – вещественный.

Действия A1, A2, A3 легко расширить, что позволит использовать большое число уровней приоритета для знаков операций и унарные знаки операций.

Нижний стек обеспечивает передачу информации вверх по синтаксическому дереву. Для передачи вниз по дереву используется верхний стек. Значение в него помещается всякий раз, когда во время генерации кода происходит вход в такую конструкцию, как присвоение или описание идентификатора. При выходе из этой конструкции значение из стека удаляется.

Еще одной структурой данных, которая требуется во время генерации кода, является таблица блоков (табл. 9.1.)

Таблица 9.1 – Таблица блоков

Блок	Уровень блока	Размер стека идентификаторов	Размер рабочего стека
1	1	14	16
2	2	12	11
3	2	21	13
4	3	4	9
5	2	6	12

В этой таблице есть запись для каждого блока программы, и эту запись можно рассматривать как структуру, имеющую поля, которые соответствуют номеру уровня блока, размеру статического стека идентификаторов, размеру статического рабочего стека и т. д. Такую таблицу можно заполнять во время прохода, генерирующего код, и с ее помощью во время следующего прохода вычислять смещения адресов рабочего стека по отношению к текущей рамке стека.

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

-  нижний стек;

-  верхний стек;

-  стек значений операций;

-  таблица блоков;

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

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

10.3.1.  Присвоение

destination := source

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

р := x + y (значение x + y присвоить p)

Допустим, что статические характеристики источника и получателя находятся в вершине нижнего стека. Последовательность действий: из нижнего стека удаляются два верхних элемента, затем выполняются следующие операции.

Проверяется непротиворечивость типов получателя и источника. Так как получатель представляет собой адрес, источник должен давать что-нибудь приемлемое для присвоения этому адресу. В зависимости от реализуемого языка типы получателя и источника можно определенным образом менять до выполнения операции присвоения. (Если источник — целое число, то его можно сначала преобразовать в вещественное, а затем присвоить адресу, имеющему тип вещественного числа.)

Там, где необходимо, проверяются правила области действия (для некоторых языков источник не может иметь меньшую область действия, чем получатель).

begin pointer real xx

begin real x

xx := x

end

присвоение недопустимо, и это может быть обнаружено во время компиляции, если в таблице символов или в нижнем стеке имеется информация об области действия.

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

ASSIGN type, S, D,

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

Если язык ориентирован на выражения (то есть само присвоение имеет значение), статические характеристики этого значения помещаются в нижний стек.

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

if B then C else D

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

CONDITIONAL ® if B<A1> then C<A2> else D<A3>

Действия А1, А2, А3 (next — значение номера следующей метки, присваиваемое компилятором) означают:

А1. Проверить тип В, применяя любые необходимые преобразования типа для получения логического значения. Выдать код для перехода к L<next>, если В есть «ложь»:

JUMPF L<next>, <address of B>

Поместить в стек значение next (обычно для этого используется стек знаков операций). Увеличить next на 1. (Угловые скобки используются для обозначения значений величин, заключенных в них).

А2. Генерировать код для перехода через ветвь else (то есть переход к концу условной зависимости):

GO TO L<next>.

Удалить из стека номер метки (помещенный в стек действием А1), назвать ее i, генерировать код для размещения метки:

SET LABEL L<i>.

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

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

SET LABEL L<j>.

Если условная зависимость сама является выражением, компилятор должен знать, где хранить его значение, независимо от того, какая часть является then или else.

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

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

Допустим, что типы всех идентификаторов выяснены в предыдущем проходе и помещены в таблицу символов. Адреса распределяются во время прохода, генерирующего код. Перечислим действия, выполняемые во время компиляции.

В таблице символов производится поиск записи, соответствующей идентификатору х.

Текущее значение указателя стека идентификаторов дает адрес, который нужно выделить под х. Этот адрес

(idstack, current block number, instack pointer)

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

Если х имеет динамическую часть (например, массив), то генерируется код для размещения динамической памяти во время прогона.

10.3.4.  Циклы

Рассмотрим простейший пример цикла:

for i to 10 do something.

Для генерации кода требуется четыре действия, которые размещаются следующим образом: