Теория и реализация языков программирования
       

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


Рассмотрим схему реализации простой блочной структуры, аналогичной процедурам в Паскале или блокам в Си. Каждый блок может иметь свой набор описаний. Программа состоит из основного именованного блока, в котором имеются описания и операторы. Описания состоят из описаний типов и объявлений переменных. В качестве типа может использоваться целочисленный тип и тип массива. Два типа 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. Обозначение <Нетерминал> в позиции типа - это указатель на вершину типа Нетерминал. Обозначение <Нетерминал> в выражении - это взятие значения указателя


Рис. 6.2. 

на ближайшую вершину вверх по дереву разбора, помеченную соответствующим нетерминалом.

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

Атрибутная реализация выглядит следующим образом.

Листинг 6.1.

(html, txt)

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

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

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


Содержание раздела