В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395), страница 17
Текст из файла (страница 17)
Обозначение <Нетерминал> в выражении – это взятие значения указателя на ближайшую вершину вверх по дереву разбора, помеченную соответствующим нетерминалом.Для реализации среды каждый нетерминал Block имеет атрибут Env.Для обеспечения возможности просматривать компоненты среды в соответствии с вложенностью блоков каждый нетерминал Block имеет атрибут Pred – указатель на охватывающий блок. Кроме того, среда блока6.2.
ЗАНЕСЕНИЕ В СРЕДУ И ПОИСК ОБЪЕКТОВ103(QY(QY(QY(QY(QY(QY(QYРис. 6.2:корня дерева (нетерминал Prog) содержит все предопределенные описания (рис. 6.2). Это заполнение реализуется процедурой PreDefine. Атрибут Pred блока корневой компоненты имеет значение NULL.Атрибутная реализация выглядит следующим образом.// Описание атрибутовALPHABETProg:: KEY TName SETOF TElement Env.// Корневая компонента, содержащая предопределенные описания.Block:: KEY TName SETOF TElement Env;<Block> 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.// Описание синтаксисических и семантических правилRULEProg ::= ’program’ Ident Block ’.’SEMANTICS0:{Init(Env<3>);PreDefine(Env<3>);104ГЛАВА 6.
ПРОВЕРКА КОНТЕКСТНЫХ УСЛОВИЙPred<3>=NULL}.RULEBlock ::= ’begin’ [( Declaration )] [ (Statement) ] ’end’SEMANTICS0: if (<Block>!=NULL){Init(Env<0>);Pred<0>=<Block>}.RULEDeclaration ::= ’type’ ( Type_Decl ).RULEType_Decl ::= Ident ’=’ Type_DefinSEMANTICSTElement V;if (Find(Val<1>,Env<Block>)!=NULL)Error("Identifier declared twice");// Идентификатор уже объявлен в блоке// В любом случае заносится новое описаниеV.Name=Val<1>;V.Object=TypeObject;V.Type=ElementType<3>;Include(V,Env<Block>).RULEType_Defin ::= ’ARRAY’ Index ’OF’ Type_DefinSEMANTICSElementType<0>=ArrayType(ElementType<4>,Val<2>).RULEType_Defin ::= Type_UseSEMANTICSElementType<0>=ElementType<1>.RULEType_Use ::= IdentSEMANTICSTElement * PV;PV=FindObject(Val<1>,<Block>,TypeObject,<Prog>);ElementType<0>=PV->Type.// В этом правиле анализируется использующая позиция// идентификатора типа.6.2.
ЗАНЕСЕНИЕ В СРЕДУ И ПОИСК ОБЪЕКТОВRULEDeclaration ::= ’var’ ( Var_Decl ).RULEVar_Decl ::= Ident_List ’:’ Type_Use ’;’SEMANTICSTElement V;TName N;for (N in Ident_Set<1>){// Цикл по (неупорядоченному) списку идентификаторовif (Find(N,Env<Block>)!=NULL)Error("Identifier declared twice");// Идентификатор уже объявлен в блоке// В любом случае заносится новое описаниеV.Name=N;V.Object=VarObject;V.Type=ElementType<3>;Include(V,Env<Block>)}.// N - рабочая переменная для элементов списка. Для каждого// идентификатора из множества идентификаторов Ident_Set<1>// сформировать объект-переменную в текущей компоненте среды// с соответствующими характеристиками.RULEIdent_List ::= ( Ident /’,’ )SEMANTICS0:Init(Ident_Set<0>);1A:Include(Val<1>,Ident_Set<0>).RULEStatement ::= Block ’;’.RULEStatement ::= Variable ’=’ Variable ’;’SEMANTICSif (ElementType<1>!=NULL) && (ElementType<3>!=NULL)&& (ElementType<1>!=ElementType<3>)Error("Incompatible Expression Types").RULEVariable ::= Ident AccessSEMANTICSTElement * PV;PV=FindObject(Val<1>,<Block>,VarObject,<Prog>);if (PV==NULL){105106ГЛАВА 6.
ПРОВЕРКА КОНТЕКСТНЫХ УСЛОВИЙError("Identifier used is not declared");ElementType<2>=NULL}elseElementType<2>=PV->Type.RULEAccess ::= ’[’ Expression ’]’ AccessSEMANTICSElementType<4>=ArrayElementType(ElementType<0>, ElementType<2>).RULEAccess ::=SEMANTICSElementType<Variable>=ElementType<0>.Поиск в среде осуществляется следующей функцией:TElement * FindObject(TName Ident, <Block> BlockPointer,TObject Object, <Prog> 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;}6.2.
ЗАНЕСЕНИЕ В СРЕДУ И ПОИСК ОБЪЕКТОВ107Переменная BlockPointer – указатель на ближайший охватывающийблок. Переходя от блока к блоку, ищем объект в его среде. Если не нашли, то переходим к охватывающему блоку. Если дошли до корневойкомпоненты, пытаемся найти объект среди предопределенных объектов. Если объект нашли, надо убедиться, что он имеет нужную категорию.Функция ArrayElementType(TType EntryType, TType ExprType) осуществляет проверку допустимости применения операции взятия индекса к переменной и возвращает тип элемента массива.Функция ArrayType(TType EntryType, int Val) возвращает описание типа –массива с типом элемента EntryType и диапазоном индекса Val.108ГЛАВА 6.
ПРОВЕРКА КОНТЕКСТНЫХ УСЛОВИЙГлава 7Организация таблицсимволовВ процессе работы компилятор хранит информацию об объектах программы в специальных таблицах символов. Как правило, информацияо каждом объекте состоит из двух основных элементов: имени объектаи описания объекта. Информация об объектах программы должна бытьорганизована таким образом, чтобы поиск ее был по возможности быстрее, а требуемая память по возможности меньше.Кроме того, со стороны языка программирования могут быть дополнительные требования к организации информации. Имена могут иметьопределенную область видимости.
Например, поле записи должно бытьуникально в пределах структуры (или уровня структуры), но может совпадать с именем объекта вне записи (или другого уровня записи). В тоже время имя поля может открываться оператором присоединения, итогда может возникнуть конфликт имен (или неоднозначность в трактовке имени). Если язык имеет блочную структуру, то необходимо обеспечить такой способ хранения информации, чтобы, во-первых, поддерживать блочный механизм видимости, а во-вторых – эффективно освобождать память при выходе из блока.
В некоторых языках (например,Аде) одновременно (в одном блоке) могут быть видимы несколько объектов с одним именем, в других такая ситуация недопустима.Мы рассмотрим некоторые основные способы организации таблиц символов в компиляторе: таблицы идентификаторов, таблицы расстановки, двоичные деревья и реализацию блочной структуры.7.1Таблицы идентификаторовКак уже было сказано, информацию об объекте обычно можно разделить на две части: имя (идентификатор) и описание. Если длина идентификатора ограничена (или имя идентифицируется по ограниченному109ГЛАВА 7.
ОРГАНИЗАЦИЯ ТАБЛИЦ СИМВОЛОВ110числу первых символов идентификатора), то таблица символов можетбыть организована в виде простого массива строк фиксированной длины, как это изображено на рис. 7.1. Некоторые входы могут быть заняты, некоторые – свободны.VDULBfyh[t_dlZRUWHDGHibkZgb_h[t_dlZРис. 7.1:HibkZgb_h[t_dlZVRUW(26D(26UHDG(26L(26Рис. 7.2:Ясно, что, во-первых, размер массива должен быть не меньше числа идентификаторов, которые могут реально появиться в программе (впротивном случае возникает переполнение таблицы); во-вторых, как правило, потенциальное число различных идентификаторов существенно7.2.
ТАБЛИЦЫ РАССТАНОВКИ111больше размера таблицы.Заметим, что в большинстве языков программирования символьноепредставление идентификатора может иметь произвольную длину. Кроме того, различные объекты в одной или в разных областях видимостимогут иметь одинаковые имена, и нет большого смысла занимать память для повторного хранения идентификатора. Таким образом, удобноимя объекта и его описание хранить по отдельности.В этом случае идентификаторы хранятся в отдельной таблице – таблице идентификаторов.
В таблице символов же хранится указательна соответствующий вход в таблицу идентификаторов. Таблицу идентификаторов можно организовать, например, в виде сплошного массива. Идентификатор в массиве заканчивается каким-либо специальнымсимволом EOS (рис. 7.2). Второй возможный вариант – в качестве первого символа идентификатора в массив заносится его длина.7.2Таблицы расстановкиОдним из эффективных способов организации таблицы символов является таблица расстановки (или хеш-таблица). Поиск в такой таблицеможет быть организован методом повторной расстановки. Суть его заключается в следующем.Таблица символов представляет собой массив фиксированного размера N .
Идентификаторы могут храниться как в самой таблице символов, так и в отдельной таблице идентификаторов.Определим некоторую функцию h1 (первичную функцию расстановки), определенную на множестве идентификаторов и принимающую значения от 0 до N − 1 (т.е. 0 6 h1 (id) 6 N − 1, где id – символьное представление идентификатора).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
