В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 26
Текст из файла (страница 26)
Если множество упорядочено, то элементы пробегаются в этом порядке, если нет — в произвольномпорядке.Среда представляет собой ключевое множество с ключом — именемобъекта. Для реализации среды каждый нетерминал Block имеет атрибутEnviron. Для обеспечения возможности просматривать компоненты средыв соответствии с вложенностью блоков поддерживается стек (список) средблоков EnvironStack (рис.
6.2). Кроме того, среда блока корня дерева (нетерминал Program) содержит все предопределенные описания.Рис. 6.2Ниже приведена атрибутная грамматика языка ToyLang, в которой определяются контекстные условия языка. Для каждого объявления переменнойи объявления типа создается запись типа TElement. В ней указывается имясозданного объекта, его вид (переменная или тип), список индексов и указатель на базовый тип.5*132Глава 6. Проверка контекстных условийALPHABETProg :: LinkedList EnvironStack.Ident :: String Val.Block :: HashMap Environ. Ident_List :: LinkedList IdentSet.Access :: TelementRef TypeRefRef; int IndexNo.Type_Defin,Type_Use, Variable, Expression, Term, Factor ::TelementRef TypeRefRef.Declaration, type_Decl,Var_Decl,Statement::.RuleProg ::= ’program’ Ident ’;’ Block ’END’.RuleBlock ::= [ ( Declaration ) ] ’begin’ [ (Statement) ] ’end’Semantics0:{Environ<0> = new HashMap(); //Новая компонента средыif (EnvironStack<Program>.isEmpty())//Блок программыEnviron.put(intName, intRef);//Предопределенный тип integerEnvironStack<Program>.addFirst(Environ);//Создать среду нового блока}{EnvironStack.removeFirst();//Удалить среду блока на выходе }.RuleDeclaration ::= ’type’ ( Type_Decl ).RuleDeclaration ::= ’var’ ( Var_Decl ).RuleType_Decl ::= Ident ’=’ Type_Defin ’;’Semantics1: {if (!((HashMap)EnvironStack<Program>.getFirst()).containsKey(Val<1>)) {//Если не было объявления с таким идентификаторомTypeRef<3> = new TElement(TYPEOBJECT);//Новый TYPEOBJECTTypeRef<3>.objectName = Val<1>;} else Error("Повторное объявление " + Val<1>); }3:{((HashMap)EnvironStack<Program>.getFirst()).put(Val<1>,typeRef<3>);// typeRef<3> наследуемый атрибут - ссылка на TYPEOBJECT6.2.
Занесение в среду и поиск объектов//Поместить в среду текущего блока}.RuleType_Defin ::= ’ARRAY’ Integer ’OF’ Type_DefinSemantics2:{if (TypeRef<0>.IndexList == null)//Первый элемент списка индексовTypeRef<0>.IndexList = new ArrayList();TypeRef<0>.IndexList.add(new Integer(Val<2>));//Добавить новый индекс к списку индексовTypeRef<4> = TypeRef<0>;}.RuleType_Defin ::= Type_UseSemantics0:{TypeRefRef<1>=newTElementRef();}//Синтезируемый атрибут{TypeRef<0> = TypeRefRef<1>.TER;}.RuleType_Use ::= IdentSemantics{HashMap Environ = null;Iterator itr = EnvironStack<Program>.iterator();while (itr.hasNext()) { //Пройти по списку сред транслируемых//блоков от внутреннего к внешнемуEnviron = (HashMap) itr.next();if (Environ.containsKey(Val<1>)) {PV = (TElement) Environ.get(Val<1>);if (PV.object != TYPEOBJECT) {Error(Val<1>+ " Не идентификатор типа");PV = null;break;}}}TypeRefRef<0>.TER = PV;if (PV == null) Error(Val<1>+ " Не объявлен");}.RuleVar_Decl ::= Ident_List ’:’ Type_Use ’;’Semantics1:{TypeRefRef<3> = new TElementRef();//Синтезируемый атрибутIdentSet<1> = new LinkedList();//Список идентификаторов }3:{TElement PV = TypeRefRef<3>.TER;Iterator itr = IdentSet<1>.iterator();133134Глава 6.
Проверка контекстных условийHashMap Env = (HashMap) EnvironStack.getFirst();while (itr.hasNext()) {//Для каждого идентификатора из спискаString Ident = (String) itr.next();if (!Env.containsKey(Ident)) {//Если идентификатор не объявленTElement newVar = new TElement(VAROBJECT);//Создать новый VAROBJECTnewVar.objectName = Ident;newVar.typeRef = PV;Env.put(Ident, newVar);} else Error("Повторное объявление" + Ident);}}RuleIdent_List ::= ( Ident / ’,’ )Semantics1A:{IdentSet<0>.addFirst(new String(Val<1>));}.RuleStatement ::= Block ’;’.RuleStatement ::= Variable ’=’ Expression’;’Semantics{TElementRef TypeRefRef<1 >= new TElementRef(); TElementRefTypeRefRef<3> = new TElementRef();if (TypeRefRef<1> .TER != TypeRefRef<3> .TER)Error("Типы значений различны"); }.RuleVariable ::= Ident AccessSemantics1:{ Iteratoritr=EnvironStack<Program>.iterator();while (itr.hasNext()) {//Пройти по блокам от внутреннего к внешнемуHashMap Environ = (HashMap) itr.next();if (Environ.containsKey(Val<1>)) {TElement PV = (TElement) Environ.get(Val<1>);if (PV.object == VAROBJECT)/* Получаем ссылку на TElement тип переменной */typeRefRef<0>.TER = PV.typeRef;else {Error(Val<1> + " Не идентификатор переменной");PV = null;break;}}}6.2.
Занесение в среду и поиск объектов135if (PV == null) Error(Val<1> + " Не объявлен");IndexNo<2> = 0; //Подсчет числа индексовTypeRefRef<2> = TypeRefRef<0>; }.RuleAccess ::= ’[’ Expression ’]’ AccessSemanticsTypeRefRef <4> = TypeRefRef <0>;{if (TypeRefRef <2> .TER != intRef)Error("Тип переменной в выражении должен быть integer");IndexNo<4> = IndexNo<0>+1; }.RuleAccess ::=Semantics{Telement eqType = typeRefRef<0>.TER;while ((eqType.IndexList == null)/* Список эквивалентных типов */& (eqType.typeRef != null))/* Пройти по списку эквивалентных типов но не далее intRef */eqType = eqType.typeRef;TypeRefRef<0>.TER = eqType;if (indexNo<0> != 0) {typeRefRef<0>.TER = eqType.typeRef;// Получаем тип элемента массиваif (indexNo<0> != eqType.IndexList.size())Error("Выход за пределы размерности массива");}}.RuleExpression ::= (Term / ’+’)Semantics0:{ TypeRefRef<1>=TypeRefRef<0>;boolean first = true;//Признак первый ли Term}1A:{if (!first)//Если Term не единственный, то все они должны иметь тип integerif ((TypeRef != intRef) | (TypeRefRef<1>.TER != TypeRef))// TypeRef - тип предыдущего Term// TypeRef<1>.TER - тип текущего TermError("Тип переменной в выражении должен быть integer");Telement TypeRef = typeRefRef<1>.TER;//Тип очередного Termfirst = false; }.RuleTerm ::= (Factor/’*’)Semantics0:{ typeRefRef<1> =typeRefRef<0>;boolean first = true;136Глава 6.
Проверка контекстных условий}1A:{if (!first)if ((TypeRef != intRef) | (typeRefRef<1>.TER != typeRef))Error("Тип переменной в выражении должен быть integer");Telement typeRef = typeRefRef<1>.TER;first = false; }.RuleFactor ::= VariableSemantics{TypeRefRef<0> =TypeRefRef<1>; }.RuleFactor ::= ’(’ Expression ’)’Semantics{TypeRefRef<0> = TypeRefRef<2>;if (TypeRefRef<2>.TER != intRef)Error("Тип переменной в выражении должен быть integer");}.RuleFactor ::= IntegerSemantics{TypeRefRef<0>.TER = intRef;}.Глава 7ОРГАНИЗАЦИЯ ТАБЛИЦ СИМВОЛОВВ процессе работы компилятор хранит информацию об объектах программы в специальных таблицах символов.
Как правило, информация о каждомобъекте состоит из двух основных элементов: имени объекта и описанияобъекта. Информация об объектах программы должна быть организованатаким образом, чтобы поиск ее был по возможности быстрее, а требуемаяпамять по возможности меньше.Кроме того, со стороны языка программирования могут быть дополнительные требования к организации информации. Имена могут иметь определенную область видимости. Например, поле записи должно быть уникальнов пределах структуры (или уровня структуры), но может совпадать с именемобъекта вне записи (или другого уровня записи).
В то же время имя поляможет открываться оператором присоединения, и тогда может возникнутьконфликт имен (или неоднозначность в трактовке имени). Если язык имеетблочную структуру, то необходимо обеспечить такой способ хранения информации, чтобы, во-первых, поддерживать блочный механизм видимости,а во-вторых, эффективно освобождать память при выходе из блока. Некоторые языки (например, Ада) допускают одновременную (в одном блоке)видимость нескольких объектов с одним именем, в других такая ситуациянедопустима.Мы рассмотрим некоторые основные способы организации таблиц символов в компиляторе: таблицы идентификаторов, таблицы расстановки, двоичные деревья и реализацию блочной структуры.7.1.
Таблицы идентификаторовКак уже было сказано, информацию об объекте обычно можно разделитьна две части: имя (идентификатор) и описание. Если длина идентификатораограничена (или имя идентифицируется по ограниченному числу первыхсимволов идентификатора), то таблица символов может быть организованав виде простого массива строк фиксированной длины, как это изображенона рис. 7.1. Некоторые входы могут быть заняты, некоторые — свободны.Ясно, что, во-первых, размер массива должен быть не меньше числа идентификаторов, которые могут реально появиться в программе (в противном138Глава 7.
Организация таблиц символовРис. 7.1Рис. 7.2случае возникает переполнение таблицы); во-вторых, как правило, потенциальное число различных идентификаторов существенно больше размератаблицы.Заметим, что в большинстве языков программирования символьное представление идентификатора может иметь произвольную длину. Кроме того,различные объекты в одной или в разных областях видимости могут иметьодинаковые имена, и нет большого смысла занимать память для повторногохранения идентификатора. Таким образом, удобно имя объекта и его описаниехранить по отдельности.В этом случае идентификаторы хранятся в отдельной таблице — таблицеидентификаторов.
В таблице символов же хранится указатель на соответствующий вход в таблицу идентификаторов. Таблицу идентификаторовможно организовать, например, в виде сплошного массива. Идентификаторв массиве заканчивается каким-либо специальным символом EOS (рис. 7.2).Второй возможный вариант — в качестве первого символа идентификаторав массив заносится его длина.7.2. Таблицы расстановки1397.2. Таблицы расстановкиОдним из эффективных способов организации таблицы символов являетсятаблица расстановки (или хеш-таблица). Поиск в такой таблице можетбыть организован методом повторной расстановки. Суть его заключаетсяв следующем.Таблица символов представляет собой массив фиксированного размера N .Идентификаторы могут храниться как в самой таблице символов, так и в отдельной таблице идентификаторов.Определим некоторую функцию h1 (первичную функцию расстановки),определенную на множестве идентификаторов и принимающую значения от0 до N − 1 (т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
