Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
Онлайн-курс по SQL для новичков.
Теория, практика, поддержка, сертификат.
2004 г
Назад Оглавление Вперёд

6. Проверка контекстных условий

6.1 Описание областей видимости и блочной структуры

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

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

Каждая компонента - это множество объявлений, представляющих собой пары (имя, тип):

где под типом будем подразумевать полное описание свойств объекта (объектом, в частности, может быть само описание типа).


Рис. 6.1:

Компоненты образуют дерево, соответствующее этому частичному порядку. Частичный порядок между компонентами обычно определяется статической вложенностью компонент в программе. Эта вложенность может соответствовать блокам, процедурам или классам программы (рис. 6.1). Компоненты среды могут быть именованы. Поиск в среде обычно ведется с учетом упорядоченности компонент. Среда может включать в себя как компоненты, полученные при трансляции «текущего» текста программы, так и «внешние» (например, раздельно компилированные) компоненты.

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

Обычными операциями при работе со средой являются:

- включить объект в компоненту среды;

- найти объект в среде и получить доступ к его описанию;

- образовать в среде новую компоненту, определенным образом связанную с остальными;

- удалить компоненту из среды.

Среда состоит из отдельных объектов, реализуемых как записи (в дальнейшем описании мы будем использовать имя TElement для имени типа этой записи). Состав полей записи, вообще говоря, зависит от описываемого объекта (тип, переменная и т.д.), но есть поля, входящие в запись для любого объекта:

TObject Object - категория объекта (тип, переменная, процедура и т.д.);

TMode Mode - вид объекта: целый, массив, запись и т.д.;

TName Name - имя объекта;

TType Type - указатель на описание типа.

6.2 Занесение в среду и поиск объектов

Рассмотрим схему реализации простой блочной структуры, аналогичной процедурам в Паскале или блокам в Си. Каждый блок может иметь свой набор описаний. Программа состоит из основного именованного блока, в котором имеются описания и операторы. Описания состоят из описаний типов и объявлений переменных. В качестве типа может использоваться целочисленный тип и тип массива. Два типа T1 и T2 считаются эквивалентными, если имеется описание T1=T2 (или T2=T1). Операторами служат операторы присваивания вида Переменная1=Переменная2 и блоки. Переменная - это либо просто идентификатор, либо выборка из массива. Оператор присваивания считается правильным, если типы переменных левой и правой части эквивалентны. Примером правильной программы может служить
program Example  
begin  
  type  T1=array 100 of array 200 of integer;  
        T2=T1;  
  var   V1:T1;  
        V2:T2;  
  begin  
    V1=V2;  
    V2[1]=V1[2];  
    begin  
      type  T3=array 300 of T1;  
      var   V3:T3;  
      V3[50]=V1;  
    end  
  end  
end.

Рассматриваемое подмножество языка может быть порождено следующей грамматикой (запись в расширенной БНФ):
Prog ::= 'program' Ident Block '.'  
Block ::= 'begin' [( Declaration )] [ (Statement) ] 'end'  
Declaration ::= 'type' ( Type_Decl )  
Type_Decl ::= Ident '=' Type_Defin  
Type_Defin ::= 'ARRAY' Index 'OF' Type_Defin  
Type_Defin ::= Type_Use  
Type_Use ::= Ident  
Declaration ::= 'var' ( Var_Decl )  
Var_Decl ::= Ident_List ':' Type_Use ';'  
Ident_List ::= ( Ident / ',' )  
Statement ::= Block ';'  
Statement ::= Variable '=' Variable ';'  
Variable ::= Ident Access  
Access ::= '[' Expression ']' Access  
Access ::=

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

  • SETOF T - простое неупорядоченное множество объектов типа T;
  • KEY K SETOF T - ключевое неупорядоченное множество объектов типа T с ключом типа K;
  • LISTOF T - простое упорядоченное множество объектов типа T;
  • KEY K LISTOF T - ключевое упорядоченное множество объектов типа T с ключом типа K;

Над объектами типа множества определены следующие операции:

  • Init(S) - создать и проинициализировать переменную S;
  • Include(V,S) - включить объект V в множество S; если множество упорядоченное, то включение осуществляется в качестве последнего элемента;
  • Find(K,S) - выдать указатель на объект с ключом K во множестве S и NIL, если объект с таким ключом не найден.

Имеется специальный оператор цикла, пробегающий элементы множества:
 for (V in S) Оператор;

Переменная V пробегает все значения множества. Если множество упорядочено, то элементы пробегаются в этом порядке, если нет - в произвольном порядке.

Среда представляет собой ключевое множество с ключом - именем объекта. Идентификаторы имеют тип TName. Обозначение <Нетерминал> в позиции типа - это указатель на вершину типа Нетерминал. Обозначение <Нетерминал> в выражении - это взятие значения указателя на ближайшую вершину вверх по дереву разбора, помеченную соответствующим нетерминалом.

Для реализации среды каждый нетерминал Block имеет атрибут Env. Для обеспечения возможности просматривать компоненты среды в соответствии с вложенностью блоков каждый нетерминал Block имеет атрибут Pred - указатель на охватывающий блок. Кроме того, среда блока корня дерева (нетерминал Prog) содержит все предопределенные описания (рис. 6.2). Это заполнение реализуется процедурой PreDefine. Атрибут Pred блока корневой компоненты имеет значение NULL.


Рис. 6.2:

Атрибутная реализация выглядит следующим образом.
// Описание атрибутов  
ALPHABET  
 
Prog:: KEY TName SETOF TElement Env.  
// Корневая компонента, содержащая предопределенные описания.  
 
Block:: KEY TName SETOF TElement Env;  
          Pred.  
 
Ident_List:: SETOF TName Ident_Set.  
// Ident_Set - список идентификаторов  
 
Type_Defin, Type_Use, Access, Expression:: TType ElementType.  
// ElementType - указатель на описание типа  
 
Declaration, Var_Decl, Type_Decl::.  
 
Ident:: TName Val.  
 
Index:: int Val.  
 
// Описание синтаксисических и семантических правил  
RULE  
Prog ::= 'program' Ident Block '.'  
SEMANTICS  
0:{Init(Env<3>);  
   PreDefine(Env<3>);  
   Pred<3>=NULL  
  }.  
 
RULE  
Block ::= 'begin' [( Declaration )] [ (Statement) ] 'end'  
SEMANTICS  
0: if (!=NULL){  
     Init(Env<0>);  
     Pred<0>=  
   }.  
 
RULE  
Declaration ::= 'type' ( Type_Decl ).  
 
RULE  
Type_Decl ::= Ident '=' Type_Defin  
SEMANTICS  
TElement V;  
if (Find(Val<1>,Env)!=NULL)  
    Error("Identifier declared twice");  
// Идентификатор уже объявлен в блоке  
// В любом случае заносится новое описание  
V.Name=Val<1>;  
V.Object=TypeObject;  
V.Type=ElementType<3>;  
Include(V,Env).  
 
RULE  
Type_Defin ::= 'ARRAY' Index 'OF' Type_Defin  
SEMANTICS  
ElementType<0>=ArrayType(ElementType<4>,Val<2>).  
 
RULE  
Type_Defin ::= Type_Use  
SEMANTICS  
ElementType<0>=ElementType<1>.  
 
RULE  
Type_Use ::= Ident  
SEMANTICS  
TElement * PV;  
PV=FindObject(Val<1>,,TypeObject,);  
If (PV!=NULL)  
ElementType<0>=PV->Type.  
// В этом правиле анализируется использующая позиция  
// идентификатора типа.  
 
RULE  
Declaration ::= 'var' ( Var_Decl ).  
 
RULE  
Var_Decl ::= Ident_List ':' Type_Use ';'  
SEMANTICS  
TElement V;  
TName N;  
for (N in Ident_Set<1>){  
// Цикл по (неупорядоченному) списку идентификаторов  
  if (Find(N,Env)!=NULL)  
     Error("Identifier declared twice");  
// Идентификатор уже объявлен в блоке  
// В любом случае заносится новое описание  
  V.Name=N;  
  V.Object=VarObject;  
  V.Type=ElementType<3>;  
  Include(V,Env)  
}.  
// N - рабочая переменная для элементов списка. Для каждого  
// идентификатора из множества идентификаторов Ident_Set<1>  
// сформировать объект-переменную в текущей компоненте среды  
// с соответствующими характеристиками.  
 
RULE  
Ident_List ::= ( Ident /',' )  
SEMANTICS  
0:Init(Ident_Set<0>);  
1A:Include(Val<1>,Ident_Set<0>).  
 
RULE  
Statement ::= Block ';'.  
 
RULE  
Statement ::= Variable '=' Variable ';'  
SEMANTICS  
if (ElementType<1>!=NULL) && (ElementType<3>!=NULL)  
         && (ElementType<1>!=ElementType<3>)  
   Error("Incompatible Expression Types").  
 
RULE  
Variable ::= Ident Access  
SEMANTICS  
TElement * PV;  
PV=FindObject(Val<1>,,VarObject,);  
if (PV==NULL){  
   Error("Identifier used is not declared");  
   ElementType<2>=NULL ;  
}  
else  
   ElementType<2>=PV->Type.  
 
RULE  
Access ::= '[' Expression ']' Access  
SEMANTICS  
ElementType<4>=ArrayElementType(ElementType<0>, ElementType<2>).  
 
RULE  
Access ::=  
SEMANTICS  
ElementType=ElementType<0>.

Поиск в среде осуществляется следующей функцией:
TElement * FindObject(TName Ident,  BlockPointer,  
                      TObject Object,  Prog)  
{ TElement * ElementPointer;  
// Получить указатель на ближайший охватывающий блок  
do{  
  ElementPointer=Find(Ident, BlockPointer->Env);  
  BlockPointer=BlockPointer->Pred;  
  }  
while (ElementPointer==NULL)&&(BlockPointer!=NULL);  
// Искать до момента, когда либо найдем нужный идентификатор,  
// либо дойдем до корневой компоненты  
if (ElementPointer==NULL)&&(BlockPointer==NULL)  
// Дошли до корневой компоненты и еще не нашли идентификатора  
// Найти объект среди предопределенных  
   ElementPointer=Find(Ident, Prog->Env);  
if (ElementPointer!=NULL)  
// Нашли объект с данным идентификатором  
// либо в очередном блоке, либо среди предопределенных  
if (ElementPointer->Object!=Object){  
// Проверить, имеет ли найденный объект  
// нужную категорию  
   Error("Object of specified category is not found");  
   ElementPointer=NULL;  
}  
else  
// Объект не найден  
   Error("Object is not found");  
return ElementPointer;  
}

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

Функция ArrayElementType(TType EntryType, TType ExprType) осуществляет проверку допустимости применения операции взятия индекса к переменной и возвращает тип элемента массива.

Функция ArrayType(TType EntryType, int Val) возвращает описание типа - массива с типом элемента EntryType и диапазоном индекса Val.


Назад Оглавление Вперёд

Новости мира IT:

Архив новостей

Последние комментарии:

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 985 1945361
Пресс-релизы — pr@citforum.ru
Обратная связь
Информация для авторов
Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2015 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...