Реферат: Проектирование трансляторов
пользуется для V4. При t=7 вновь возникает такая же проблема.
Значение V4 не требуется до момента t=11, тогда как V3 ис-
пользуется при t=8 и V2 - при t=9. Поэтому регистр R1 отводится
для V5. При t=10 переменная V1 используется снова. Теперь приме-
няется сформулированное выше условие (2), так как значение V2
больше не потребуется. Поэтому регистр R2 отводится для V1. Ана-
логично при t=11 регистр К2 отводится для V4, так как больше не
потребуется значение V1.
Распределение регистров R1 и R3 для V5 и V3 сохраняется до
конца последовательности команд. Описанное распределение быстрых
регистров показано диаграммой на рис. 20.9.
V5 ├─────────────────┤
V4 ├────── ─ ─ ─ ─ ─ ──┤
V3 ├───────────────┼──────────────────┤
V2 ├─────┼─────┼────────┤
V1 ├──────────── ─ ─ ─ ─ ─ ─ ──┤
1 2 3 4 5 6 7 8 9 10 11 12 13
Рис. 20.9 Диаграмма использования переменных Vi в последова-
тельности команд, поясняющая работу алгоритма Биледи
4. ТАБЛИЦА СИМВОЛОВ
4.1 Описатели
Для каждого вхождения идентификатора в исх. программе осу-
ществляется поиск соотв. элемента в таблице символов (ТС), инфор-
мация, полученная при данном вхождении, сопоставляется с ранее
полученной информацией, выполняется необходимый контроль и регис-
трация новой информации. Таким образом, ТС является очень важной
частью компилятора и, в некотором смысле, узловой точкой всей
трансляции. Ее структура должна допускать эффективный поиск и
внесение информации. В то же время, каждый элемент должен зани-
мать как можно меньше места, для того, чтобы хватало места на
большие программы с большим числом идентификаторов. Вообще гово-
ря, желательно, чтобы возможно меньшее число программ транслято-
ра непосредственно работало с ТС. Это позволит достаточно легко
вносить необходимые изменения. Особенно важно тщательно согласо-
вать формат описателя до того, как начнется программирование
транслятора.
ОПИСАТЕЛЕМ называется часть элемента ТС, в которой описы-
вается идентификатор. Существует другой термин для обозначения
этого же понятия, введенный Фельдманом - "семантическое слово" (У
Ахо и Ульмана это назывется "дескриптором").
Количество информации, которое нужно хранить в описателе,
зависит от того, чем является фактически идентификатор - простой
переменной, массивом, функцией и т.д. Поэтому в некоторых реали-
зацих описатели имеют переменную длину. Это допустимо не при лю-
бой организации ТС. Иногда в целях экономии памяти выбирают эле-
мент ТС малого размера, а для идентификаторов, требующих больше
места, отводят по несколько соседних элементов.
Другая возможность открывается, емли в нужных случаях отво-
дить часть описателя под указатель, ссылающийся на дополни-
тельную таблицу. Это несколько осложняет программирование, пос-
кольку тип описателя может менять свой смысл в зависимости от ти-
па элемента.
4.2 Возможные параметры описания переменных и процедур
в таблице символов
Для переменных и процедур в описателе может потребоваться
следующая информация:
ПЕРЕМЕННАЯ:
Тип (вещ., целый, строка, комплексный, метка и т.д.);
Точность, масштаб, длина;
Вид (простая переменная, массив, структура и т.д.);
Адрес во время выполнения программы;
Если массив, то - число измерений. Если есть граничные пары
(ограниченные множества в Паскале), то их значения;
Если структура или компонента структуры, то связь данной
компоненты с другими компонентами;
Формальный параметр или нет; если да, то тип соответствия
параметров;
Описана ли переменная как extern или как идентификатор объе-
динения (union) ?
Обрабатывалось ли уже ее описание ?
Существует ли инструкция, присваивающая ей значение ?
ПРОЦЕДУРА:
Является ли она внешней по отношению к программе ?
Является ли она функцией ?
Каков ее тип ?
Обрабатывалось ли уже ее описание ?
Является ли она рекурсивной ?
Каковы ее формальные параметры ? Их описатели должны быть
связаны с именем функции для того, чтобы можно было проверить их
соответствие фактическим параметрам.
4.3 Таблица символов компилятора /360 WATFOR
/360 WATFOR - однопроходной компилятор с языка ФОРТРАН IV
для машин IBM/360.
ТС состоит из пяти разных списков:
- списка меток;
- списка арифметических констант;
- списка имен общих блоков, подпрограмм, переменных;
- списка блоков;
- списка подпрограмм.
(Таким образом, некоторые элементы оказываются в двух списках.)
Элементы всех списков помещаются в одной и той же таблице;
первые 2 байта каждого элемента используются для ссылки на сле-
дующий элемент в этом же списке. Следовательно, поиск отдельного
элемента сводится к линейному просмотру по ссылкам.
Элементы различных типов имеют разлмчную длину в пределах от
8 до 20 байтов.
Например, элемент для переменной имеют длину 16 байтов и со-
держит следующую информацию (первые 2 байта опущены):
3-4 5-10 11-12 13-14 15-16
┌────┬───────┬───────────┬──────┬───────────┐
│ B2 │идент-р│размерность│COMMON│EQUIVALENCE│
└────┴───────┴───────────┴──────┴───────────┘
В полях "COMMON" и "EQUIVALENCE" помещаются указатели на
элементы других переменных, связанных с данной при помощи ин-
струкций COMMON и EQUIVALENCE.
В поле "размерность" содержится 0, если переменная не яв-
ляется массивом; в противном случае оно указывает на отдельный
элемент, содержащий всю информацию о размерности: величины
d1,...,dn и длину d1*...*dn.
Два байта, обозначенные B2, содержат всю остальную информа-
цию (см. рис. 20.10). Первоначально все поля содержат нули, и в
них заносится информация по мере обработки программы.
Единица в каждом однобитовом поле на рис. 20.10 говорит о
наличии соответствующего факта.
│ 0-1 │ 2-4 │ 5-6 │ 7 │ 8 │ 9 │
├───────────┼────────┼──────────┼────────┼───────┼─────────┤
│10 - прос- │число │ тип │ длина │ тип │исполь- │
│ тая │индексов│00 - лог. │задается│сформи-│зование │
│ перем.│в случае│01 - цел. │програм-│рован │сформиро-│
│11 - массив│массива │10 - вещ. │мистом │ │вано │
│ │ │11 - ком- │ │ │ │
│ │ │ плекс. │ │ │ │
│ 10 │ 11 │ 12 │ 13 │ 14 │ 15 │
├─────────┼────────┼─────────┼────────┼────────┼───────────┤
│формаль- │текущий │присваи- │имеет │встреча-│встреча- │
│ный пара-│параметр│вается │нач. │ется в │ется в │
│метр │цикла │значение │значение│COMMON │EQUIVALENCE│
│програм- │ │по ASSIGN│ │ │ │
│мы │ │ │ │ │ │
Рис. 20.10 Схема подполей поля B2
4.4 Представление структур в таблице символов
Мы можем представлять структуру, отводя по одному элементу
для каждой компоненты. Кроме обычных полей, каждый элемент имеет
три дополнительных поля: FATHER, SON и BROTHER.
Поле FATHER указывает на ОТЦА, SON - на первого СЫНА компо-
ненты, а поле BROTHER - на ее следующего БРАТА в последова-
тельности братьев группы.
Если данный элемент не имеет отца, сына или следующего бра-
та, то соответствующее поле будет содержать 0.
Ниже на рис. 20.11 приведены иерархические схемы строения
двух структур с указанием перед идентификатором каждой из
(под)компонент уровня ее вложенности.
1 A 1 L
2 B 2 M
3 C 4 C
3 D 4 D
2 E 2 B
2 F 5 C
5 D
Рис. 20.11 Схема построения двух структур
Элементы ТС для этих двух структур приведены ниже на Табли-
це 20.1. Этой информации может хватить с избытком (а может ока-
заться и недостаточно) для эффективной работы со структурами.
Поскольку могут существовать элементы, имена которых совпа-
дают, вводится еще один указатель SAME, связывающий такие элемен-
ты между собой. Первый из этих элементов содержит в этом поле 0.
Таблица 20.1 Схема заполнения элементов ТС для двух струк-
тур на рис. 20.11
┌────┬───┬─────┬──────┬────┬───────┐
│ │ID │ SAME│FATHER│ SON│BROTHER│
├────┼───┼─────┼──────┼────┼───────┤
│ A1 │ A │ 0 │ 0 │ B1 │ 0 │
│ B1 │ B │ 0 │ A1 │ C1 │ E1 │
│ C1 │ C │ 0 │ B1 │ 0 │ D1 │
│ D1 │ D │ 0 │ B1 │ 0 │ 0 │
│ E1 │ E │ 0 │ A1 │ 0 │ F1 │
│ F1 │ F │ 0 │ A1 │ 0 │ 0 │
│ L1 │ L │ 0 │ 0 │ M1 │ 0 │
│ M1 │ M │ 0 │ L1 │ C2 │ B2 │
│ C2 │ C │ C1 │ M1 │ 0 │ D2 │
│ D2 │ D │ D1 │ M1 │ 0 │ 0 │
│ B2 │ B │ B1 │ L1 │ C3 │ 0 │
│ C3 │ C │ C2 │ B2 │ 0 │ D3 │
│ D3 │ D │ D2 │ B2 │ 0 │ 0 │
└────┴───┴─────┴──────┴────┴───────┘
_
