Лекции по конструированию компиляторов. В.А. Серебряков (1134687), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

Entry<3>=Include(Val<2>,Env<Block>);
Entry<3>->Object=LocalModuleObject;
Kind<4>=false;
3: for (M in Imp_Set<3>) Inc_Imp(M,Env<4>);
if (Mode<3>==NotQual)
for (V in Entry<3>->Exp_Set) Export(V,Env<Block>).

Помещение модуля; ищем объект с данным именем в текущей компоненте. Если такой уже есть, - ошибка. Заносим в текущую компоненту среды объект-модуль. Множество Imp_Set - это множество импортируемых модулем объектов. Элементы этого множества - пары, первая компонента которых - имя импортируемого модуля, вторая - список импортируемых из него объектов. Если вторая компонента Nil, то импорт неквалифицированный. Если импортируемый объект M - модуль и если M импортируется неквалифицированно (IMPORT M), то процедура Inc_Imp включает M в среду текущего модуля; если импорт квалифицированный (FROM M IMPORT ...), то M имеет список импорта и процедура Inc_Imp включает в текущую компоненту те экспортируемые из M объекты, которые перечислены в списке квалифицированного импорта; если при этом импортируемый объект - в свою очередь модуль, то из M рекурсивно импортируется все его экспортные объекты.

Атрибут Mode вычисляется в правиле для экспорта и определяет, осуществляется ли квалифицированный экспорт (EXPORT QUALIFIED ...) или нет (EXPORT ...). Процедура Export в случае неквалифицированного экспорта EXPORT A1,A2,... все объекты экспортного списка модуля заносит в компоненту среды, охватывающую модуль; если Ai - модуль, его экспорт обрабатывается рекурсивно; если экспорт квалифицированный, то в охватывающую модуль компоненту попадает только сам модуль со списком экспорта.

RULE
Block ::= [( Declaration )] [ Block_St_Seq ] 'end' Ident
SEMANTICS
0:Init(Env<0>);
Pred<0>=&<Block>.

Атрибут Pred - указатель на охватывающий блок.

RULE
Mod_Head ::= [ Priority ] ';' [ ( Import ) ] [ Export ]
SEMANTICS
4E: Mode<4>=NotQual;
Entry<0>->Mode=Mode<4>;
Mode<0>=Mode<4>;
0:Init(Imp_Set<0>).

Инициализируется список импорта. Тип экспорта заносится в описание модуля.

RULE
Import ::= [ From ] 'import' ( Ident /',' ) ';'
SEMANTICS
Import_Pair Tmp;
0:Init(Imp_Set<0>);
1E: Qual<1>=false;
3A:if (Qual<1>) Include(Val<3>,Imp_Set<0>);
else {Tmp.Name_Set=NULL;
Tmp.Imp_Name=Name<3>;
Include(Tmp,Imp_Set<Mod_Head>);
}
if (Qual<1>)
{Tmp.Name_Set=Imp_Set<0>;
Tmp.Imp_Name=Name<1>;
Include(Tmp,Imp_Set<Mod_Head>);
}.

Если импорт квалифицированный, то Name<1> - имя модуля, из которого делается импорт. В этом случае Imp_Set<0> - множество импортируемых из него объектов. Идентификатор включается в список импорта из модуля, иначе идентификатор - имя модуля и он включается в список импортируемых модулей. Если импорт квалифицированный, включить в список импорта модуля весь список импортируемых объектов.

RULE
From ::= 'from' Ident
SEMANTICS
Qual<0>=true;
Name<0>=Val<2>.

RULE
Export ::= 'export' [ Qual ] ( Ident /',' )
SEMANTICS
0: Init(Entry<Mod_Head>->Exp_Set);
2Е: Mode<2>=NotQual;
Mode<0>=Mode<2>;
3A: Include(Val<3>,Entry<Mod_Head>->Exp_Set).

Включить идентификатор в экспортный список модуля; множество экспортируемых модулем объектов заносится в поле Exp_Set : Key Name Set Of Element в таблице объектов, поскольку при использовании квалифицированного импорта или обращении M.V, где M - имя модуля, а V - имя экспортируемого объекта, необходимо иметь доступ к списку квалифицированного экспорта.

RULE
Qual ::= 'qualified'
SEMANTICS
Qual<0>=Qualified.

RULE
Declaration ::= 'var' ( Var_Decl ).

RULE
Var_Decl ::= Ident_List ':' Type_Des ';'
SEMANTICS
Element V;
for (V in Ident_Set<1>)
{if (Find(V,Env<Block>)!=NULL)
Error("Identifire declared twice");
V.Object=VarObject;
V.Type=Exit<3>;
Include(V,Env<Block>)
}.

V - рабочая переменная для элементов списка. Для каждого идентификатора из множества Ident_Set<1> сформировать объект-переменную в текущей компоненте среды с соответствующими характеристиками.

RULE
Ident_List ::= ( Ident /',' )
SEMANTICS
0:Init(Ident_Set<0>);
1A:Include(Val<1>,Ident_Set<0>).

RULE
Type_Des ::= Ident
SEMANTICS
Block * P;
P=&<Block>;
do{
Exit<0>=Find(Val<1>,P->Env);
if (P->Kind) P=P->Pred;
}
while (Exit<0>==NULL)&&(P->Kind);
if (Exit<0>==NULL)
Exit<0>=Find(Val<1>,Env<Prog>);
if (Exit<0>==NULL) Error("Type Description not found");
else if (Exit<0>->Object!=TypeObject)
{Error("Not type object");
Exit<0>:=Nil;
}.

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

Зависимости атрибутов на дереве разбора приведены на рис. 5.5.

Block Env


Dec_List


Declaration


Block
Env

Imp_Set Mod_Head Exp_Set


Imp_List

Export

Import Import
Imp_Set

From Ident Ident


Ident


Ident Ident Ident Ident

Рис. 5.5

Глава 6. Организация таблиц символов компилятора

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

6.1. Таблицы идентификаторов и таблицы символов

Как уже было сказано, информацию об объекте обычно можно разделить на две части: имя (идентификатор) и описание. Удобно эти характеристики объекта хранить по отдельности. Это обусловлено двумя причинами: 1) символьное представление идентификатора может иметь неопределенную длину и быть довольно длинным; 2) как уже было сказано, различные объекты в одной области видимости и/или в разных могут иметь одинаковые имена и незачем занимать память для повторного хранения идентификатора. Таблицу для хранения идентификаторов называют таблицей идентификаторов, а таблицу для хранения свойств объектов - таблицей символов. В таком случае одним из свойств объекта становится его имя и в таблице символов хранится указатель на соответствующий вход в таблицу идентификаторов.

6.2. Таблицы идентификаторов

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

s o r t

a

r e a d

i
.................

Рис. 6.1

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

Пусть число элементов массива равно N. Определим некоторую функцию h (первичную функцию расстановки), определенную на множестве идентификаторов и принимающую значения 0<=h(id)<=N-1, id - идентификатор. Если элемент таблицы h(id) свободен, то это означает, что идентификатора в таблице нет. Если же занят, то это еще не означает, что идентификатор id в таблицу занесен, поскольку (вообще говоря) много идентификаторов могут иметь одно и то же значение функции расстановки. Для того чтобы определить, нашли ли мы нужный идентификатор, сравниваем id с элементом таблицы h(id). Если они равны - идентификатор нашли, если нет - надо продолжать поиск дальше. Для этого вычисляют вторичную функцию расстановки h2(h). Вновь возможны четыре варианта: либо элемент таблицы свободен, либо нашли идентификатор, либо таблица вся просмотрена и идентификатора нет, либо надо продолжать поиск. Для продолжения поиска применяют вновь функцию h3(h2), и т.д. Как правило, hi=h2 для i>=2. Аргументом функции h2 является целое в диапазоне [0,N-1] и она может быть быть устроена по-разному. Приведем три варианта.

1) h2(i)=(i+1) mod N

Берется следующий (циклически) элемент массива. Этот вариант плох тем, что занятые элементы "группируются", образуют последовательные занятые участки и в пределах этого участка поиск становится по-существу линейным.

2) h2(i)=(i+k) mod N, где k и N взаимно просты.

По-существу это предыдущий вариант, но элементы накапливаются не в последовательных элементах, а "разносятся".

Характеристики

Список файлов лекций