Таблица 10.1

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

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

10.3. ГЕНЕРАЦИЯ КОДА ДЛЯ НЕКОТОРЫХ ТИПИЧНЫХ

КОНСТРУКТОВ

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

1. Присваивания

В соответствии с терминологией Алгола 68 имеет вид

destination := source

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

р := X + у

значение <x + у» присваивается р.

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

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

2. Там, где это необходимо, проверяются правила области действия. В Алголе 68 источник не может иметь меньшую область действия, чем получатель. Например, в

begin refrealxx: begin real x: xx := x end

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

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

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

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

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

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

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

if B then C else D fi

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

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

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

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

JUMPFL<next>, <address of B >

Поместить в стек значения next (обычно для этого служит стек знаков операций). Увеличить next на 1. (Угловые скобки (< , >), в которые заключаются «next» и «address of B», используются для обозначения значений этих величин, и их не следует путать со скобками, в которые заключаются действия порождающих правилах грамматики.)

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

GOTO L< next >

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

SETLABEL L<i>

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

SETLABEL L<j>

Если условная зависимость сама является выражением (а не оператором), компилятор должен знать, где хранить его значение, независимо от того, какая часть вычисляется - then или else. Это можно сделать, специфицируя адрес, который указывает на данное значение, или пересылая значение, заданное частью then либо частью else, по указанному адресу.

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

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

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

Рассмотрим описание

somemode x

Перечислим действия, выполняемые во время компиляции:

1) В таблице символов производиться поиск записи, соответствующей x.

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

(idstack, current block number, idstackpointer)

включается в таблицу символов, а указатель стека идентификаторов увеличивается на статический размер значения, соответствующего x. (В Алголе 68, если вид x начинается с ref, объем памяти должен выделяться для значения, на которое ссылается x, а не для самого x; это обозначается с помощью адреса другого типа.)

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

4. Циклы

Рассмотрим следующий простой цикл:

for i to 10 do something od

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

for i<A1>to10<A2>do<A3>something<A4>od

Эти действия таковы: А1. Выделить память для управляющей переменной i. Поместить сначала в эту память 1

MOVE «1», address (controlledvariable)

А2. Генерировать код для записи в память значения верхнего предела рабочего стека

MOVE address (ulimit), (wostack, current block number, wostackpointer)

(wostack pointer - указатель рабочего стека). Увеличить указатель рабочего стека и уменьшить указатель нижнего стека, где хранились статические характеристики верхнего предела

А3. Поместить метку

SETLABEL L<next>