В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 25
Текст из файла (страница 25)
Элемент правой части синтаксического правила, заключенный в скобки [ ],может отсутствовать. Элемент правой части синтаксического правила, заключенный в скобки ( ), означает возможность повторения один или более раз.Элемент правой части синтаксического правила, заключенный в скобки [()],означает возможность повторения ноль или более раз. В скобках [ ] или[()] может указываться разделитель конструкций.Ниже дан синтаксис языка описания атрибутных грамматик. Приведентолько синтаксис конструкций, собственно описывающих атрибутные вычисления. Синтаксис обычных выражений и операторов не приводится —он основывается на Си.Атрибутная грамматика::=’ALPHABET’( ОписаниеНетерминала ) ( Правило )ОписаниеНетерминала::=ИмяНетерминала’::’ [( ОписаниеАтрибутов / ’;’)]’.’ОписаниеАтрибутов::=Тип ( ИмяАтрибута / ’,’)Правило::=’RULE’ Синтаксис ’SEMANTICS’ Семантика’.’Синтаксис::=ИмяНетерминала ’::=’ ПраваяЧастьПраваяЧасть::=[( ЭлементПравойЧасти )]ЭлементПравойЧасти::=ИмяНетерминала| Терминал| ’(’ Нетерминал [ ’/’ Терминал ] ’)’| ’[’ Нетерминал ’]’| ’[(’ Нетерминал [ ’/’ Терминал ] ’)]’Семантика::=[(ЛокальноеОбъявление / ’;’)][( СемантическоеДействие / ’;’)]СемантическоеДействие::=Присваивание| [ Метка ] ОператорПрисваивание::=Переменная ’:=’ ВыражениеПеременная::=ЛокальнаяПеременная|АтрибутАтрибут::=ЛокальныйАтрибут|ГлобальныйАтрибутЛокальныйАтрибут::=ИмяАтрибута ’<’ Номер ’>’ГлобальныйАтрибут::=ИмяАтрибута ’<’ Нетерминал ’>’Метка::=Целое ’:’| Целое ’Е’ ’:’| Целое ’А’ ’:’5.3.
Атрибутные грамматики125Описание атрибутной грамматики состоит из раздела описания атрибутови раздела правил. Раздел описания атрибутов определяет состав атрибутовдля каждого символа грамматики и тип каждого атрибута. Правила состоятиз синтаксической и семантической частей.
В синтаксической части используется расширенная БНФ. Семантическая часть правила состоит из локальныхобъявлений и семантических действий. В качестве семантических действийдопускаются как атрибутные присваивания, так и составные операторы.Метка в семантической части правила привязывает выполнение оператора к обходу дерева разбора сверху-вниз слева-направо.
Конструкцияi : оператор означает, что оператор должен быть выполнен сразу послеобхода i-й компоненты правой части. Конструкция i E : оператор означает,что оператор должен быть выполнен, только если порождение i-й компонентыправой части пусто. Конструкция i A : оператор означает, что оператордолжен быть выполнен после разбора каждого повторения i-й компонентыправой части (имеется в виду конструкция повторения).Каждое правило может иметь локальные определения (типов и переменных). В формулах используются как атрибуты символов данного правила(локальные атрибуты), и в этом случае соответствующие символы указываются номерами в правиле (0 для символа левой части, 1 для первого символаправой части, 2 для второго символа правой части, и т.
д.), так и атрибутысимволов предков левой части правила (глобальные атрибуты). В этом случаесоответствующий символ указывается именем нетерминала. Таким образом,на дереве образуются области видимости атрибутов: атрибут символа имеетобласть видимости, состоящую из правила, в которое символ входит в правуючасть, плюс всё поддерево, корнем которого является символ, за исключениемподдеревьев — потомков того же символа в этом поддереве.Значение терминального символа доступно через атрибут VAL соответствующего типа.Пример 5.9. Атрибутная грамматика из примера 5.5 записывается следующимобразом:ALPHABET Num:: float V.
Intint P.Frac:: float V;int P.digit :: int VAL.RULENum ::= Int ’.’ FracSEMANTICSV<0>=V<1>+V<3>; P<3>=1.RULE:: float V;126Глава 5. Элементы теории переводаInt ::= eSEMANTICSV<0>=0; P<0>=0.RULEInt ::= digit IntSEMANTICSV<0>=VAL<1>*10**P<2>+V<2>; P<0>=P<2>+1.RULEFrac ::= eSEMANTICSV<0>=0.RULEFrac ::= digit FracSEMANTICSV<0>=VAL<1>*10**(-P<0>)+V<2>; P<2>=P<0>+1.Глава 6ПРОВЕРКА КОНТЕКСТНЫХ УСЛОВИЙ6.1. Описание областей видимости и блочной структурыЗадачей контекстного анализа является установление свойств объектови их использования. Наиболее часто решаемой задачей является определениесуществования объекта и соответствия его использования контексту, чтоосуществляется с помощью анализа типа объекта. Под контекстом здесьпонимается вся совокупность свойств текущей точки программы, напримермножество доступных объектов, тип выражения и т.
д.Таким образом, необходимо хранить объекты и их типы, уметь находитьэти объекты и определять их типы, определять характеристики контекста.Совокупность доступных в данной точке объектов будем называть средой.Обычно среда программы состоит из частично упорядоченного набора компонентE = {DS1 , DS2 , . . . , DSn }Каждая компонента — это множество объявлений, представляющих собойпары (имя, тип):DSi = {(имяj , типj ) | 1 6 j 6 ki }где под типом будем подразумевать полное описание свойств объекта (объектом, в частности, может быть само описание типа).Рис. 6.1128Глава 6. Проверка контекстных условийКомпоненты образуют дерево, соответствующее этому частичному порядку.
Частичный порядок между компонентами обычно определяется статической вложенностью компонент в программе. Эта вложенность можетсоответствовать блокам, процедурам или классам программы (рис. 6.1). Компоненты среды могут быть именованы. Поиск в среде обычно ведется с учетомупорядоченности компонент. Среда может включать в себя как компоненты,полученные при трансляции «текущего» текста программы, так и «внешние»(например, раздельно компилированные) компоненты.Для обозначения участков программы, в которых доступны те или иныеописания, используются понятия области действия и области видимости.Областью действия описания является процедура (блок), содержащая описание, со всеми входящими в нее (подчиненными по дереву) процедурами(блоками). Областью видимости описания называется часть области действия, из которой исключены те подобласти, в которых по тем или инымпричинам описание недоступно, например, оно перекрыто другим описанием.В разных языках понятия области действия и области видимости уточняютсяпо-разному.Обычными операциями при работе со средой являются:– включить объект в компоненту среды;– найти объект в среде и получить доступ к его описанию;– образовать в среде новую компоненту, определенным образом связаннуюс остальными;– удалить компоненту из среды.6.2.
Занесение в среду и поиск объектовРассмотрим схему реализации простой блочной структуры, аналогичнойпроцедурам в Паскале или блокам в Си. Каждый блок может иметь свойнабор описаний. Программа состоит из основного именованного блока, в котором имеются описания и операторы. Описания состоят из описаний типови объявлений переменных. В качестве типа может использоваться целочисленный тип и тип массива. Два типа T1 и T2 считаются эквивалентными,если имеется описание T1=T2 (или T2=T1). Операторами служат операторыприсваивания вида Переменная1=Переменная2 и блоки. Переменная — этолибо просто идентификатор, либо выборка из массива. Оператор присваивания считается правильным, если типы переменных левой и правой частиэквивалентны.
Примером правильной программы может служитьprogram Example;type T1=array 100 of array 200 of integer;T2=T1;6.2. Занесение в среду и поиск объектов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 пробегает все значения множества.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
