идентификаторов. Он может быть также литералом или константой. Номер блока позволяет найти номер уровня блока в таблице блоков (см. разд. 10.2), что обеспечивает доступ к конкретной рамке стека через дисплей. В случае литерала или константы номер блока не используется. Смещение (для адреса стека) показывает смещение значения конкретной рамки по отношению к началу стека идентификаторов или рабочего стека. Если тип-адреса представляет собой литерал, то смещение выражается самим значением, а если тип-адреса - константа, то смещение нужно найти в таблице констант по заданному им адресу. В том случае когда в каждой рамке стека рабочий стек помещается сразу же над стеком идентификаторов, смещения адресов рабочего стека по отношению к началу рамки модно рассчитывать, как только станет известным размер стека идентификаторов для конкретной рамки (т.е. во время прохода, следующего за проходом, при котором происходит распределение памяти).

Адреса во время прогона для идентификаторов определяются в процессе распределения памяти и хранятся в таблице символов вместе с информацией о типе и т. п.

Кроме рассмотренных, существуют и другие команды промежуточного кода (ICI по Бранкору):

SETLABEL L1

для установки метки и

ASSIGN type, addl, add2

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

10.2. СТРУКТУРЫ ДАННЫХ ДЛЯ ГЕНЕРАЦИИ КОДА

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

1) адресом времени прогона;

2) типом;

3) областью действия,

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

При трансляции A + B первыми помещаются в нижний стек статический свойства

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

B. Знак операции берется из стека знаков операций, а его два операнда - из нижнего стека. Типы операндов используются для идентификации знака операции, после чего

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

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

EXP TERM \

EXP + TERM

EXP - TERM

TERM FACT \

TERMXFACT \

TERM / FACT FACT constant identifier

(EXP)

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

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

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

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

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

EXP TERM

EXP + <A2> TERM<A3> EXP - <A2> TERM<A3>

TERM FACT

TERMX<A2>FACT<A3>\ TERM / <A2>FACT<A3>

FACT constant <A1> identifier <A1>

(EXP)

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

a X b + x X y

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

a<Ar>X<A2>b<A1><A3>+<A2>x<A1>X<A2>y<A1><A3><A3>

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

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

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

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

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

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

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

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

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

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

Действия А1, А2, А3 и вышеприведенную грамматику легко расширить, что позволит использовать

а) большее число уровней приоритета для знаков операций;

б) унарные знаки операций.

Другие случаи употребления нижнего стека рассматриваются в следующем разделе.

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

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

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