В.А. Серебряков - Теория и реализация языков программирования (1134641), страница 26
Текст из файла (страница 26)
Занесение в среду и поиск объектовvar129V1:T1;V2:T2;beginV1=V2;V2[1]=V1[2];type T3=array 300 of T1;varV3:T3;beginV3[50]=V1;endendРассматриваемое подмножество языка может быть порождено следующейграмматикой (запись в расширенной БНФ):Prog ::= ’program’ Ident ’;’ Block ’END’Block ::= [ ( Declaration ) ] ’begin’ [ (Statement) ] ’end’Declaration ::= ’type’ ( Type_Decl )Declaration ::= ’var’ ( Var_Decl )Type_Decl ::= ( Ident ’=’ Type_Defin ’;’)Type_Defin ::= ’ARRAY’ Integer ’OF’ Type_DefinType_Defin ::= Type_UseVar_Decl ::= ( Ident_List ’:’ Type_Use ’;’)Type_Use ::= IdentIdent_List ::= ( Ident / ’,’ )Statement ::= Block ’;’Statement ::= Variable ’=’ Expression’;’Variable ::= Ident AccessAccess ::= ’[’ Expression ’]’ AccessAccess ::=Expression ::= (Term/’+’)Term ::= (Factor/’*’)Factor ::= VariableFactor ::= ’(’ Expression ’)’Factor ::= IntegerНаш транслятор будет переводить приведенную выше программу в следующую программу на Java:class Example{ public static void main(String args[]){ int XXXX_0,XXXX_1,XXXX_2,XXXX_3,XXXX_4,XXXX_6;int V1_1[][]=new int[100][200];int V2_1[][]=new int[100][200];5 В.А.
Серебряков130Глава 6. Проверка контекстных условийfor (XXXX_0=0;XXXX_0<100;XXXX_0++)for (XXXX_1=0;XXXX_1<200;XXXX_1++)V1_1[XXXX_0][XXXX_1]=V2_1[XXXX_0][XXXX_1];for (XXXX_1=0;XXXX_1<200;XXXX_1++)V2_1[1][XXXX_1]=V1_1[2][XXXX_1];int V3_2[][][]=new int[300][100][200];for (XXXX_0=0;XXXX_0<100;XXXX_0++)for (XXXX_1=0;XXXX_1<200;XXXX_1++)V3_2[50][XXXX_0][XXXX_1]=V1_1[XXXX_0][XXXX_1];}}Среда состоит из отдельных объектов, реализуемых как записи (в дальнейшем описании мы будем использовать имя TElement для имени типаэтой записи). Состав полей записи, вообще говоря, зависит от описываемогообъекта (тип, переменная и т.
п.). В трансляторе, приведенном ниже, элементсреды реализуется классом TElement:сlass TElement {int object;//String objectName;//TElement typeRef = null; //ArrayList IndexList = null;int level;}Переменная или типТолько для отладкиСсылка на описатель базового типа// Список индексов// Block levelДля реализации синтезируемых атрибутов будем использовать ссылку на этоттип:class TElementRef {TElement TER;}Для реализации некоторых атрибутов (в частности среды, списка идентификаторов и т. п.) в качестве типов данных мы будем использовать различныемножества.
Множество может быть упорядоченным или неупорядоченным,ключевым или простым. Элементом ключевого множества может быть запись,одним из полей которой является ключ. В Java эти множества реализуютсятипами данных LinkedList, ArrayList, HashMap.HashSet — простое неупорядоченное множество объектов;HashMap — ключевое неупорядоченное множество объектов ;LinkedList — упорядоченное множество объектов ;6.2. Занесение в среду и поиск объектов131ArrayList — список (упорядоченное множество объектов), к элементамкоторого имеется доступ по индексу.Над объектами типа множества определены следующие операции:T S = new T() — создать переменную S типа T;S.add(Value) — включить объект Value во множество S ; если множе-ство упорядоченное, то включение осуществляется в качестве последнего элемента;S.put(Name,Value) — включить объект Value в ключевое множествоS;(T)S.get(Key) — выдать указатель на объект типа T с ключом Key вомножестве S и NULL, если объект с таким ключом не найден.Цикл по элементам множества реализуется с помощью итератора:Iterator itr = S.iterator();while (itr.hasNext()) {T V = (T) itr.next();}Переменная V пробегает все значения множества.
Если множество упорядочено, то элементы пробегаются в этом порядке, если нет — в произвольномпорядке.Среда представляет собой ключевое множество с ключом — именемобъекта. Для реализации среды каждый нетерминал 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
