|
Лекции по конструированию компиляторов - Часть 8
Автор: В.А.Серебряков Глава 6. Контекстные условия языков программирования 6.1. Описание областей видимости и блочной структуры Задачей контекстного анализа является установление правильности использования объектов. Наиболее часто решаемой задачей является определение существования объекта и соответствия его использования контексту, что осуществляется с помощью анализа типа объекта. Таким образом необходимо хранить объекты, их типы, уметь находить эти объекты и определять их типы, определять характеристики контекста. Совокупность доступных в даной точке объектов будем называть "средой". Обычно среда программы состоит из частично упорядоченного набора компонент
E={DS1,...DSn}.
Каждая компонента - это множество объявлений, представляющих собой пары <имя,тип>:
DSi={<имя,тип>},
где под типом будем подразумевать полное описание свойств объекта (объектом, в частности, может быть само описание типа). Между компонентами DSi и DSj имеет место отношение "DSi включает DSj" тогда и только тогда, когда любой объект из DSi может быть доступен из DSj (конкретный способ доступа определяется правилами видимости языка), но не наоборот. Компоненты образуют дерево. Это дерево соответствует блокам или процедурам (рис. 6.1
+-------------+
| Корневая |
| компонента |
| (программа) |
+-------------+
+---------+ | +--------+
| | |
+-----------++-----------++-----------+
| процедура || процедура || процедура |
| (блок) || (блок) || (блок) |
+-----------++-----------++-----------+
/|\ /|\ /|\
Рис. 6.1
Обычными операциями при работе со средой являются:
- включить объект в компоненту среды;
- найти объект в среде и получить доступ к его описанию;
- образовать в среде новую компоненту, определенным образом
связанную с остальными;
- удалить компоненту из среды.
Компоненты среды могут быть именованы. Поиск в среде обычно ведется с учетом упорядоченности компонент. Среда может включать в себя как компоненты, полученные при трансляции "текущего" текста программы, так и "внешние" компоненты. Для обозначения участков программы, в которых доступны те или иные описания, используются понятия "область действия" и "область видимости". Областью действия описания является процедура (блок), содержащая описание, со всеми входящими в нее (подчиненными по дереву) процедурами (блоками). Областью видимости описания называется часть области действия, из которой исключены те подобласти, в которых по тем или иным причинам описание недоступно. В разных языках понятия области действия и области видимости уточняются по-разному. В дальнейшем изложение ведется на примере языка Модула -2. 6.2. Структура среды Модулы-2 Имеются четыре рода языковых конструкций, которые могут содержать описания: 1) программный модуль или модуль реализации; 2) модуль определения; 3) процедура; 4) локальный модуль. "Корневую" компоненту среды в Модуле-2 образует программный модуль или модуль реализации. Объекты этой компоненты могут быть описаны в самом модуле или могут быть импортированы из других модулей определений. Такой импорт может быть квалифицированным (from M import X,Y, ...;) или не квалифицированным (import M;).
Экспортирующий Компонента Импортирующий
локальный модуль среды локальный модуль
+------------+ +------------+ +------------+
| MODULE M1; | | +----+ | | MODULE X1; |
| EXPORT A1;-+--------+-->| A1 |---+--+ | IMPORT A1; |
| ......... | | +----+ | | | |
+------------+ | | +--+------> A1 |
| | +------------+
+--------------+ | |
| MODULE M2; | | | +------------+
| EXPORT | | +----+ | | MODULE X2; |
| QUALIFIED A2-+------+-->| M2 | | | FROM M2 |
| ............ | | +----+ | | IMPORT A2; |
+--------------+ | v | +---+---->A2 |
| +----+ | | +------------+
| | A2 |---+-+
| +----+ |
+-----------------+ | |
| MODULE M3; | | +-----+ |
| EXPORT M31;-----+---+-->| M31 | | +-------------+
| +-------------+| | +-----+ | | MODULE X3; |
| | MODULE M31; || | +-----+ | | IMPORT A31; |
| | EXPORT A31;-++---+-->| A31 |--+-----+--> A31 |
| | .......... || | +-----+ | | +-------------+
| +-------------+| | | |
| ................| | | | +-------------+
+-----------------+ | | | | MODULE X |
| | | | IMPORT M31; |
| | +--+---> A31 |
v v +-------------+
+-------------------+ v v
| MODULE M4; | | +-----+ |
| EXPORT M41;-------+-+-->| M41 | | +-------------+
| +---------------+| | +-----+ | | MODULE X4; |
| | MODULE M41; || | v | | FROM M41 |
| | EXPORT || | +-----+ | | IMPORT A41; |
| | QUALIFIED A41;|+-+-->| A41 |--+-----+----> A41 |
| | .......... || | +-----+ | | +-------------+
| +---------------+| | | | +--------------+
| ..................| | | | | MODULE X |
+-------------------+ | | | | IMPORT M41; |
| | +--+-->A41 |
| | +--------------+
+-----------------+ | +----+ |
| MODULE M5; | | | M5 | | +-------------+
| EXPORT | | +----+ | | MODULE X5; |
| QUALIFIED M51;--+---+-+ v | | FROM M5 |
| +-------------+| | | +-----+ | | IMPORT M51; |
| | MODULE M51; || | +->| M51 |-+------+-> M51.A51 |
| | EXPORT A51;-++---+-+ +-----+ | +-------------+
| | .......... || | | v |
| +-------------+| | | +-----+ |
| ................| | +->| A51 | |
+-----------------+ | +-----+ |
+-------------------+ | +----+ |
| MODULE M6; | | | M6 | | +-------------+
| EXPORT | | +----+ | | MODULE X6; |
| QULIFIED M61;-----+-+-+ v | | FROM M6 |
| +---------------+| | | +-----+ | | IMPORT M61; |
| | MODULE M61; || | +->| M61 |-+------+--> M61.A61 |
| | EXPORT || | +-----+ | +-------------+
| | QUALIFIED A61;|+-+-+ v |
| | ............ || | | +-----+ |
| +---------------+| | +->| A61 | |
| ..................| | +-----+ |
+-------------------+ +------------+
Рис. 6.2
В первом случае импортированные объекты становятся элементами среды данного модуля, во втором - сам импортированный модуль становится элементом среды, а его объекты могут быть доступны через указание имени модуля (M.X). Область действия объектов, описанных в локальном модуле, может состоять из самого этого локального модуля или из охватывающего его блока, если объект экспортируется из локального модуля. Схему импорта в локальный модуль можно пояснить рис. 6.2. Существует предопределенная компонента, объекты которой доступны во всех других компонентах (если они там не переопределены). Эта компонента включает в себя типы данных такие как, integer, real, boolean, char, word, address, proc, константы true, false, nil, процедуры adr, tsize, cap, small, chr, inc, dec, float, halt, hihg, odd, ord, trunc, val, excl, incl, max, min, size, abs. Элементом описания может быть процедура или локальный модуль, имеющие свой список описаний. Процедура образует новую компоненту среды, а локальный модуль - нет (рис. 6.3). Объекты локального модуля являются объектами охватывающей компоненты, но с ограниченными областями видимости. Внутри локального модуля доступны те и только те объекты этой компоненты, которые явно импортированы в локальный модуль. И наоборот: объекты локального модуля могут быть экспортированы в охватывающую компоненту. В то же время объекты процедуры образуют новую компоненту, поскольку объекты этой компоненты могут быть доступны в процедуре. Конфликт имен при этом не противоречит определению компоненты: объект охватывающей компоненты может быть виден (если внутри данной процедуры не описан объект с тем же именем).
Модуль (программный или реализации)
+------------+
| Среда |<----- Свой модуль определений
|------------|<----- Импорт из других
| Объявления | модулей определений
+------------+
|^ |
Импорт || | Видимость
+--------+| +-----------+
| +-------+ |
v |Экспорт v
+------------------+ +-----------+
| Локальный модуль | | Процедура |
|------------------| |-----------|
| ................ | | ......... |
| | | |
+------------------+ +-----------+
Рис. 6.3
Среда состоит из отдельных объектов, реализуемых как записи. Состав полей записи вообще говоря зависит от объекта (тип, переменная и т.д.), но есть поля, входящие в запись для любого объекта:
Object - категория объекта: тип, переменная, процедура и т.д.; Mode - вид объекта: целый, массив, запись и т.д.; Name - имя объекта; Type - указатель на описание типа. 6.3. Занесение в среду и поиск объектов Поскольку блоки образуют иерархию на дереве разбора программы, при поиске объекта мы можем с помощью атрибута типа "указатель на блок" переходить от блока к охватывающему блоку. Если теперь у каждого блока есть атрибут, указывающий, является ли блок процедурой или модулем, то легко реализовать сочетание блочной структуры со средствами управления видимостью. Кроме того, корень дерева имеет атрибут, соответствующий предопределенной компоненте, так что через этот глобальный атрибут доступны все предопределенные описания (рис. 6.4). Env ^ ^ / \ Env Env ^^ ^^ / \ / \ Env Env Env Env Рис. 6.4 В качестве типов данных атрибутов мы будем использовать множество. Множество может быть упорядоченным или неупорядоченным, ключевым или простым. Элементом ключевого множества может быть запись, одним из полей которой является ключ:
SET OF T - простое неупорядоченное множество объектов типа T; KEY K SET OF T - ключевое неупорядоченное множество объектов типа T с ключом K; LIST OF T - простое упорядоченное множество объектов типа T; KEY K LIST OF T - ключевое упорядоченное множество объектов типа T с ключом K; Над объектами типа множества определены следующие операции: Init(S) - создать и проинициализировать переменную S; Include(V,S) - включить объект V в множество S; если множество упорядоченное, то включение осуществляется в качестве последнего элемента; Find(K,S) - выдать указатель на объект с ключом K во множестве S и NIL, если объект с таким ключом не найден. Имеется специальный оператор цикла, пробегающий элементы множества: for V in S do Оператор; Переменная V локализована в теле оператора и пробегает все значения множества. Если множество упорядочено, то элементы пробегаются в этом порядке, если нет - в произвольном порядке. Среда представляет собой ключевое множество с ключом - именем объекта. Каждый локальный модуль имеет атрибут - множество импортируемых объектов и атрибут - множество экспортируемых объектов. Экспортируемые модулем объекты в соответствии с правилами экспорта включаются в компоненту среды, в которую входит сам модуль. Ниже приведен фрагмент описания контекстных условий языка Модула-2 (в фигурные скобки заключены комментарии).
ALPHABET Prog:: Env : key Name set of Element. Предопределенная компонента. Идентификаторы имеют тип Name.
Block :: Env : key Name set of Element;
Kind : boolean;
Pred : pointer to Block.
Арибут Kind равен true для процедур и false для модулей. Env - множество объявлений блока. Pred - указатель на охватывающий блок.
Mod_Head :: Entry : pointer to Element;
Imp_Set : set of Import_Pair;
Mode:boolean.
Imp_Set - множество импортируемых модулем объектов; тип
Import_Pair - запись из двух полей: Imp_Name:Name - имя
импортируемого объекта, и Name_Set:Set of Name - список
импортируемых из модуля объектов, если импорт
квалифицированный, и Nil, если неквалифицированный; Entry -
указатель на вход для модуля; Mode - признак
квалифицированного экспорта.
Import :: Imp_Set : set of Name.
Imp_Set - список квалифицированного импорта.
Export :: Mode:boolean.
Mode - признак квалифицированного экспорта.
From :: Qual : boolean; Name : NameType.
Qual :: Qual : boolean.
Ident_List :: Ident_Set : set of Name.
Type_Des :: Exit : pointer to Element.
Qual - признак квалифицированного импорта; Name - имя модуля,
из которого делается импорт; Ident_Set - список
идентификаторов; Exit - указатель на описание типа.
RULE
Declaration ::= 'procedure' Ident [ Formal_Param ] ';'
Block ';'
SEMANTICS
var Entry:pointer to Element;
Kind<5>:=true;
2:if Find(Val<2>,Env)<>Nil
then Error("Identifire declared twice");
end;
Entry:=Include(Val<2>,Env);
Entry@.Object:=ProcObject.
Помещение процедуры; ищем объект с данным именем в текущей компоненте; Entry - указатель на вход для процедуры. Если объект с таким именем уже есть, - ошибка.
RULE
Declaration ::= 'module' Ident Mod_Head Block ';'
SEMANTICS
var M:Import_Pair;
V:Element;
if Find(Val<2>,Env)<>Nil
then Error("Identifire declared twice")
end;
Entry<3>:=Include(Val<2>,Env);
Entry<3>@.Object:=LocalModuleObject;
Kind<4>:=false;
3: for M in Imp_Set<3> do Inc_Imp(M,Env<4>);
end;
if (Mode<3>=NotQual) then
for V in Entry<3>@.Exp_Set do Export(V,Env);
end end.
Помещение модуля; ищем объект с данным именем в текущей компоненте. Если такой уже есть, - ошибка. Заносим в текущую компоненту среды объект-модуль. Множество 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>:=@.
Атрибут 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
var Tmp:Import_Pair;
0:Init(Imp_Set<0>);
1E: Qual<1>:=false;
3A:if Qual<1> then Include(Val<3>,Imp_Set<0>)
else Tmp.Name_Set:=Nil;
Tmp.Imp_Name:=Name<3>;
Include(Tmp,Imp_Set)
end;
if Qual<1> then
Tmp.Name_Set:=Imp_Set<0>;
Tmp.Imp_Name:=Name<1>;
Include(Tmp,Imp_Set)
end.
Если импорт квалифицированный, то 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@.Exp_Set);
2Е: Mode<2>:=NotQual;
Mode<0>:=Mode<2>;
3A: Include(Val<3>,Entry@.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
var V:Name;
for V in Ident_Set<1> do
if (Find(V,Env)<>Nil)
then Error("Identifire declared twice")
end;
Include(V,Env);
V@.Object:=VarObject;
V@.Type:=Exit<3>;
end.
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
var P:pointer to Block;
P:=Block@;
repeat
Exit<0>:=Find(Val<1>,P@.Env);
if P@.Kind then P:=P@.Pred
end;
until (Exit<0><>NIL)or(not P@.Kind);
if (Exit<0>=NIL)
then Exit<0>:=Find(Val<1>,Env)
end;
if (Exit<0>=Nil) then Error("тип не найден")
else if (Exit<0>@.Object<>TypeObject) then
Error("Not type object"); Exit<0>:=Nil;
end end.
Рабочая переменная P - указатель на ближайший охватывающий блок. Переходя от блока от блоку, ищем объект в его среде. Если не нашли, то, если блок - процедура, перейти к охватывающей. Если дошли до границы модуля, попытаться найти объект в предопределенной компоненте. Если объект нашли, надо убедиться, что он - тип. Зависимости атрибутов на дереве разбора приведены на рис. 6.5.
+--------------------+
| |
| Block | Env<--------+
| | |
| | |
| Dec_List |
| | |
| | |
| Declaration |
| | \ |
| | \ |
| | Block |
| +---------+---------->Env |
v | | |
+-----> Imp_Set | Mod_Head | Exp_Set<-+
| | \ |
| | \ |
| Imp_List \ |
| | \ |
| +--------------+ Export |
| | | | |
| Import Import |--------+ |
| /| Imp_Set | | | |
| / | ^ | | | |
| From | | | Ident Ident |
| | | | | | | |
| | | | | v v |
|<--Ident | | | ---------------+
| +-------+ | +--------+
| | | | | |
| Ident Ident | Ident Ident
| | | | | |
| v v | | |
| -----------+ v v
+------------------------------
Рис. 6.5
|
Автор проекта: USU Software
Вы можете выкупить этот проект.