В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1134643), страница 17
Текст из файла (страница 17)
АТРИБУТНЫЕ ГРАММАТИКИ95ции разработки трансляторов, основанных на формализме атрибутныхграмматик. Опыт их использования показал, что “чистый” атрибутныйформализм может быть успешно применен для описания семантики языка, но его использование вызывает трудности при создании транслятора. Эти трудности связаны как с самим формализмом, так и с некоторыми технологическими проблемами. К трудностям первого рода можно отнести несоответствие чисто функциональной природы атрибутноговычислителя и связанной с ней неупорядоченностью процесса вычисления атрибутов (что в значительной степени является преимуществомэтого формализма) и упорядоченностью элементов программы.
Это несоответствие ведет к тому, что приходится идти на искусственные приемы для их сочетания. Технологические трудности связаны с эффективностью трансляторов, полученных с помощью атрибутных систем. Какправило, качество таких трансляторов довольно низко из-за большихрасходов памяти, неэффективности искусственных приемов, о которыхбыло сказано выше.Учитывая это, мы будем вести дальнейшее изложение на языке, сочетающем особенности атрибутного формализма и обычного языка программирования, в котором предполагается наличие операторов, а значит, и возможность управления порядком исполнения операторов.
Этотпорядок может быть привязан к обходу атрибутированного дерева разбора сверху вниз слева направо. Что касается грамматики входного языка, то мы не будем предполагать принадлежность ее определенному классу (например, LL(1) или LR(1)). Будем считать, что дерево разбора входной программы уже построено как результат синтаксического анализа и атрибутные вычисления осуществляются в результате обхода этогодерева. Таким образом, входная грамматика атрибутного вычислителяможет быть даже неоднозначной, что не влияет на процесс атрибутныхвычислений.При записи синтаксиса мы будем использовать расширенную БНФ.Элемент правой части синтаксического правила, заключенный в скобки[ ], может отсутствовать.
Элемент правой части синтаксического правила, заключенный в скобки ( ), означает возможность повторения одинили более раз. Элемент правой части синтаксического правила, заключенный в скобки [()], означает возможность повторения ноль или болеераз. В скобках [ ] или [()] может указываться разделитель конструкций.Ниже дан синтаксис языка описания атрибутных грамматик. Приведен только синтаксис конструкций, собственно описывающих атрибутные вычисления.
Синтаксис обычных выражений и операторов неприводится – он основывается на Си.Атрибутная грамматика ::= ’ALPHABET’( ОписаниеНетерминала ) ( Правило )ОписаниеНетерминала ::= ИмяНетерминала’::’ [( ОписаниеАтрибутов / ’;’)] ’.’ОписаниеАтрибутов ::= Тип ( ИмяАтрибута / ’,’)96ГЛАВА 5. ЭЛЕМЕНТЫ ТЕОРИИ ПЕРЕВОДАПравило ::= ’RULE’ Синтаксис ’SEMANTICS’ Семантика ’.’Синтаксис ::= ИмяНетерминала ’::=’ ПраваяЧастьПраваяЧасть ::= [( ЭлементПравойЧасти )]ЭлементПравойЧасти ::= ИмяНетерминала| Терминал| ’(’ Нетерминал [ ’/’ Терминал ] ’)’| ’[’ Нетерминал ’]’| ’[(’ Нетерминал [ ’/’ Терминал ] ’)]’Семантика ::= [(ЛокальноеОбъявление / ’;’)][( СемантическоеДействие / ’;’)]СемантическоеДействие ::= Присваивание| [ Метка ] ОператорПрисваивание ::= Переменная ’:=’ ВыражениеПеременная ::= ЛокальнаяПеременная| АтрибутАтрибут ::= ЛокальныйАтрибут| ГлобальныйАтрибутЛокальныйАтрибут ::= ИмяАтрибута ’<’ Номер ’>’ГлобальныйАтрибут ::= ИмяАтрибута ’<’ Нетерминал ’>’Метка ::= Целое ’:’| Целое ’Е’ ’:’| Целое ’А’ ’:’Оператор ::= Условный| ОператорПроцедуры| ЦиклПоМножеству| ПростойЦикл| ЦиклСУсловиемОкончанияОписание атрибутной грамматики состоит из раздела описания атрибутов и раздела правил.
Раздел описания атрибутов определяет составатрибутов для каждого символа грамматики и тип каждого атрибута.Правила состоят из синтаксической и семантической части. В синтаксической части используется расширенная БНФ. Семантическая частьправила состоит из локальных объявлений и семантических действий.В качестве семантических действий допускаются как атрибутные присваивания, так и составные операторы.Метка в семантической части правила привязывает выполнение оператора к обходу дерева разбора сверху-вниз слева направо. Конструкция i : оператор означает, что оператор должен быть выполнен сразу после обхода i-й компоненты правой части. Конструкция i E : оператор означает, что оператор должен быть выполнен, только если порождение i-йкомпоненты правой части пусто.
Конструкция i A : оператор означает,что оператор должен быть выполнен после разбора каждого повторенияi-й компоненты правой части (имеется в виду конструкция повторения).Каждое правило может иметь локальные определения (типов и пе-5.3. АТРИБУТНЫЕ ГРАММАТИКИ97ременных). В формулах используются как атрибуты символов данногоправила (локальные атрибуты) и в этом случае соответствующие символы указываются номерами в правиле (0 – для символа левой части, 1 –для первого символа правой части, 2 – для второго символа правой части и т.д.), так и атрибуты символов предков левой части правила (глобальные атрибуты).
В этом случае соответствующий символ указывается именем нетерминала. Таким образом, на дереве образуются областивидимости атрибутов: атрибут символа имеет область видимости, состоящую из правила, в которое символ входит в правую часть, плюс всеподдерево, корнем которого является символ, за исключением поддеревьев – потомков того же символа в этом поддереве.Значение терминального символа доступно через атрибут VAL соответствующего типа.Пример 5.9.
Атрибутная грамматика из примера 5.5 записывается следующим образом:ALPHABETNum :: float V.Int :: float V;int P.Frac :: float V;int P.digit :: int VAL.RULENum ::= Int ’.’ FracSEMANTICSV<0>=V<1>+V<3>; P<3>=1.RULEInt ::= 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.98ГЛАВА 5. ЭЛЕМЕНТЫ ТЕОРИИ ПЕРЕВОДАГлава 6Проверка контекстныхусловий6.1Описание областей видимости и блочной структурыЗадачей контекстного анализа является установление свойств объектови их использования.
Наиболее часто решаемой задачей является определение существования объекта и соответствия его использования контексту, что осуществляется с помощью анализа типа объекта. Под контекстом здесь понимается вся совокупность свойств текущей точки программы, например множество доступных объектов, тип выражения ит.д.Таким образом, необходимо хранить объекты и их типы, уметь находить эти объекты и определять их типы, определять характеристикиконтекста.
Совокупность доступных в данной точке объектов будем называть средой. Обычно среда программы состоит из частично упорядоченного набора компонентE = {DS1 , DS2 , ... , DSn }Каждая компонента – это множество объявлений, представляющихсобой пары (имя, тип):DSi = {(имяj , типj ) | 1 6 j 6 ki }где под типом будем подразумевать полное описание свойств объекта(объектом, в частности, может быть само описание типа).Компоненты образуют дерево, соответствующее этому частичному порядку.
Частичный порядок между компонентами обычно определяетсястатической вложенностью компонент в программе. Эта вложенностьможет соответствовать блокам, процедурам или классам программы (рис. 6.1).99100ГЛАВА 6. ПРОВЕРКА КОНТЕКСТНЫХ УСЛОВИЙDhjg_\Zydhfihg_glZijh]jZffZijhp_^mjZ[ehdijhp_^mjZ[ehdijhp_^mjZ[ehdРис. 6.1:Компоненты среды могут быть именованы. Поиск в среде обычно ведется с учетом упорядоченности компонент. Среда может включать всебя как компоненты, полученные при трансляции “текущего” текстапрограммы, так и “внешние” (например, раздельно компилированные)компоненты.Для обозначения участков программы, в которых доступны те илииные описания, используются понятия области действия и областивидимости. Областью действия описания является процедура (блок),содержащая описание, со всеми входящими в нее (подчиненными по дереву) процедурами (блоками).
Областью видимости описания называется часть области действия, из которой исключены те подобласти, в которых по тем или иным причинам описание недоступно, например, оноперекрыто другим описанием. В разных языках понятия области действия и области видимости уточняются по-разному.Обычными операциями при работе со средой являются:– включить объект в компоненту среды;– найти объект в среде и получить доступ к его описанию;– образовать в среде новую компоненту, определенным образом связанную с остальными;– удалить компоненту из среды.Среда состоит из отдельных объектов, реализуемых как записи (вдальнейшем описании мы будем использовать имя TElement для именитипа этой записи).
Состав полей записи, вообще говоря, зависит от описываемого объекта (тип, переменная и т.д.), но есть поля, входящие взапись для любого объекта:TObject Object – категория объекта (тип, переменная, процедура и т.д.);TMode Mode – вид объекта: целый, массив, запись и т.д.;TName Name – имя объекта;TType Type – указатель на описание типа.6.2. ЗАНЕСЕНИЕ В СРЕДУ И ПОИСК ОБЪЕКТОВ6.2101Занесение в среду и поиск объектовРассмотрим схему реализации простой блочной структуры, аналогичной процедурам в Паскале или блокам в Си. Каждый блок может иметьсвой набор описаний. Программа состоит из основного именованного блока, в котором имеются описания и операторы. Описания состоят из описаний типов и объявлений переменных.
В качестве типа может использоваться целочисленный тип и тип массива. Два типа T1 и T2 считаются эквивалентными, если имеется описание T1=T2 (или T2=T1). Операторами служат операторы присваивания вида Переменная1=Переменная2 иблоки. Переменная – это либо просто идентификатор, либо выборка измассива. Оператор присваивания считается правильным, если типы переменных левой и правой части эквивалентны. Примером правильнойпрограммы может служитьprogram Examplebegintype T1=array 100 of array 200 of integer;T2=T1;var V1:T1;V2:T2;beginV1=V2;V2[1]=V1[2];begintype T3=array 300 of T1;var V3:T3;V3[50]=V1;endendend.Рассматриваемое подмножество языка может быть порождено следующей грамматикой (запись в расширенной БНФ):Prog ::= ’program’ Ident Block ’.’Block ::= ’begin’ [( Declaration )] [ (Statement) ] ’end’Declaration ::= ’type’ ( Type_Decl )Type_Decl ::= Ident ’=’ Type_DefinType_Defin ::= ’ARRAY’ Index ’OF’ Type_DefinType_Defin ::= Type_UseType_Use ::= IdentDeclaration ::= ’var’ ( Var_Decl )Var_Decl ::= Ident_List ’:’ Type_Use ’;’Ident_List ::= ( Ident / ’,’ )Statement ::= Block ’;’Statement ::= Variable ’=’ Variable ’;’ГЛАВА 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
