В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395), страница 15
Текст из файла (страница 15)
По определению, атрибут a имеет в этом узлезначение v, если в соответствующем семантическом правилеa(Xi ) = f (b(Xj ), c(Xk ), ... , d(Xm ))все атрибуты b, c, . . . , d уже определены и имеют в узлах с метками Xj ,Xk , . . . , Xm значения vj , vk , . . . , vm соответственно, а v = f (v1 , v2 , ... , vm ).5.3. АТРИБУТНЫЕ ГРАММАТИКИ91Процесс вычисления атрибутов на дереве продолжается до тех пор, пока нельзя будет вычислить больше ни одного атрибута. Вычисленные врезультате атрибуты корня дерева представляют собой “значение”, соответствующее данному дереву вывода.Заметим, что значение синтезируемого атрибута символа в узле синтаксического дерева вычисляется по атрибутам символов в потомкахэтого узла; значение наследуемого атрибута вычисляется по атрибутам“родителя’ и “соседей”.Атрибуты, сопоставленные вхождениям символов в дерево разбора,будем называть вхождениями атрибутов в дерево разбора, а дерево с сопоставленными каждой вершине атрибутами – атрибутированным деревом разбора.Пример 5.6.
Атрибутированное дерево для грамматики из предыдущего примера и цепочки w = 12.34 показано на рис. 5.3.1XP,QWGLJLWY Y S ,QWGLJLWY Y )UDFGLJLWY S ,QWY Y S Y S )UDFGLJLWY Y S )UDFY S HHРис. 5.3:Будем говорить, что семантические правила заданы корректно, если они позволяют вычислить все атрибуты произвольного узла в любомдереве вывода.Между вхождениями атрибутов в дерево разбора существуют зависимости, определяемые семантическими правилами, соответствующимипримененным синтаксическим правилам. Эти зависимости могут бытьпредставлены в виде ориентированного графа следующим образом.Пусть T – дерево разбора.
Сопоставим этому дереву ориентированный граф D(T ), узлами которого являются пары (n, a), где n – узел дерева T , a – атрибут символа, служащего меткой узла n. Граф содержитдугу из (n1 , a1 ) в (n2 , a2 ) тогда и только тогда, когда семантическое правило, вычисляющее атрибут a2 , непосредственно использует значениеГЛАВА 5. ЭЛЕМЕНТЫ ТЕОРИИ ПЕРЕВОДА92атрибута a1 . Таким образом, узлами графа D(T ) являются атрибуты, которые нужно вычислить, а дуги определяют зависимости, подразумевающие, какие атрибуты вычисляются раньше, а какие позже.Пример 5.7. Граф зависимостей атрибутов для дерева разбора из предыдущего примера показан на рис.
5.4.Y1XP S1XPY,QW S,QWYGLJLWY,QW S,QWY,QW S,QWYGLJLW Y,QW S,QWYGLJLW Y,QW S,QWYGLJLW Y,QW S,QWРис. 5.4:Можно показать, что семантические правила являются корректными тогда и только тогда, когда для любого дерева вывода T соответствующий граф D(T ) не содержит циклов (т.е. является ориентированнымациклическим графом).5.3.2Классы атрибутных грамматик и их реализацияВ общем виде реализация вычислителей для атрибутных грамматик вызывает значительные трудности.
Это связано с тем, что множество значений атрибутов, связанных с данным деревом, приходится вычислятьв соответствии с зависимостями атрибутов, которые образуют ориентированный ациклический граф. На практике стараются осуществлять процесс вычисления атрибутов, привязывая его к тому или иному способуобхода дерева.
Рассматривают многовизитные, многопроходные и другие атрибутные вычислители. Это, как правило, ведет к ограничениюдопустимых зависимостей между атрибутами, поддерживаемых вычислителем.Простейшими подклассами атрибутных грамматик, вычисления всехатрибутов для которых может быть осуществлено одновременно с синтаксическим анализом, являются S-атрибутные и L-атрибутные грамматики.5.3.
АТРИБУТНЫЕ ГРАММАТИКИ93Определение. Атрибутная грамматика называется S-атрибутной, если она содержит только синтезируемые атрибуты.Нетрудно видеть, что для S-атрибутной грамматики на любом дереве разбора все атрибуты могут быть вычислены за один обход дереваснизу вверх. Таким образом, вычисление атрибутов можно делать параллельно с восходящим синтаксическим анализом, например, LR(1)анализом.Пример 5.8. Рассмотрим S-атрибутную грамматику для перевода арифметических выражений в ПОЛИЗ.
Здесь атрибут v имеет строковый тип, k – обозначает операцию конкатенации. Правила вывода и семантические правила определяются следующим образомE1 → E2 + Tv(E 1 ) = v(E 2 ) k v(T ) k 0 +0E→Tv(E) = v(T )T →T ∗Fv(T 1 ) = v(T 2 ) k v(F ) k 0 ∗0T →Fv(T ) = v(F )F → idv(F ) = v(id)F → (E)v(F ) = v(E)Определение. Атрибутная грамматика называется L-атрибутной, если любой наследуемый атрибут любого символа Xj из правой частикаждого правила X0 → X1 X2 ... Xn грамматики зависит только от(1) атрибутов символов X1 , X2 , .
. . , Xj−1 , находящихся в правиле слева от Xj , и(2) наследуемых атрибутов символа X0 .Заметим, что каждая S-атрибутная грамматика является L-атрибутной.Все атрибуты на любом дереве для L-атрибутной грамматики могут бытьвычислены за один обход дерева сверху-вниз слева-направо. Таким образом, вычисление атрибутов можно осуществлять параллельно с нисходящим синтаксическим анализом, например, LL(1)-анализом или рекурсивным спуском.В случае рекурсивного спуска в каждой функции, соответствующейнетерминалу, надо определить формальные параметры, передаваемыепо значению, для наследуемых атрибутов, и формальные параметры,передаваемые по ссылке, для синтезируемых атрибутов.
В качестве примера рассмотрим реализацию атрибутной грамматики из примера 5.5(нетрудно видеть, что грамматика является L-атрибутной).94ГЛАВА 5. ЭЛЕМЕНТЫ ТЕОРИИ ПЕРЕВОДАvoid int_part(float * V0, int * P0){if (Map[InSym]==Digit){ int I=InSym;float V2;int P2;InSym=getInSym();int_part(&V2,&P2);*V0=I*exp(P2*ln(10))+V2;*P0=P2+1;else {*V0=0;*P0=0;}}void fract_part(float * V0, int P0){if (Map[InSym]==Digit){ int I=InSym;float V2;int P2=P0+1;InSym=getInSym();fract_part(&V2,P2);*V0=I*exp(-P0*ln(10))+V2;else {*V0=0;}}void number(){ float V1,V3,V0;int P;int_part(&V1,&P);if (InSym!=’.’) error();fract_part(&V3,1);V0=V1+V3;}5.3.3Язык описания атрибутных грамматикФормализм атрибутных грамматик оказался очень удобным средствомдля описания семантики языков программирования. Вместе с тем выяснилось, что реализация вычислителей для атрибутных грамматик общего вида сталкивается с большими трудностями.
В связи с этим былосделано множество попыток рассматривать те или иные классы атрибутных грамматик, обладающих “хорошими” свойствами. К числу таких свойств относятся прежде всего простота алгоритма проверки атрибутной грамматики на зацикленность и простота алгоритма вычисления атрибутов для атрибутных грамматик данного класса.Атрибутные грамматики использовались для описания семантики языков программирования и было создано несколько систем автоматиза-5.3. АТРИБУТНЫЕ ГРАММАТИКИ95ции разработки трансляторов, основанных на формализме атрибутныхграмматик.
Опыт их использования показал, что “чистый” атрибутныйформализм может быть успешно применен для описания семантики языка, но его использование вызывает трудности при создании транслятора. Эти трудности связаны как с самим формализмом, так и с некоторыми технологическими проблемами. К трудностям первого рода можно отнести несоответствие чисто функциональной природы атрибутноговычислителя и связанной с ней неупорядоченностью процесса вычисления атрибутов (что в значительной степени является преимуществомэтого формализма) и упорядоченностью элементов программы. Это несоответствие ведет к тому, что приходится идти на искусственные приемы для их сочетания.
Технологические трудности связаны с эффективностью трансляторов, полученных с помощью атрибутных систем. Какправило, качество таких трансляторов довольно низко из-за большихрасходов памяти, неэффективности искусственных приемов, о которыхбыло сказано выше.Учитывая это, мы будем вести дальнейшее изложение на языке, сочетающем особенности атрибутного формализма и обычного языка программирования, в котором предполагается наличие операторов, а значит, и возможность управления порядком исполнения операторов.
Этотпорядок может быть привязан к обходу атрибутированного дерева разбора сверху вниз слева направо. Что касается грамматики входного языка, то мы не будем предполагать принадлежность ее определенному классу (например, LL(1) или LR(1)). Будем считать, что дерево разбора входной программы уже построено как результат синтаксического анализа и атрибутные вычисления осуществляются в результате обхода этогодерева. Таким образом, входная грамматика атрибутного вычислителяможет быть даже неоднозначной, что не влияет на процесс атрибутныхвычислений.При записи синтаксиса мы будем использовать расширенную БНФ.Элемент правой части синтаксического правила, заключенный в скобки[ ], может отсутствовать. Элемент правой части синтаксического правила, заключенный в скобки ( ), означает возможность повторения одинили более раз.
Элемент правой части синтаксического правила, заключенный в скобки [()], означает возможность повторения ноль или болеераз. В скобках [ ] или [()] может указываться разделитель конструкций.Ниже дан синтаксис языка описания атрибутных грамматик. Приведен только синтаксис конструкций, собственно описывающих атрибутные вычисления.
Синтаксис обычных выражений и операторов неприводится – он основывается на Си.Атрибутная грамматика ::= ’ALPHABET’( ОписаниеНетерминала ) ( Правило )ОписаниеНетерминала ::= ИмяНетерминала’::’ [( ОписаниеАтрибутов / ’;’)] ’.’ОписаниеАтрибутов ::= Тип ( ИмяАтрибута / ’,’)96ГЛАВА 5. ЭЛЕМЕНТЫ ТЕОРИИ ПЕРЕВОДАПравило ::= ’RULE’ Синтаксис ’SEMANTICS’ Семантика ’.’Синтаксис ::= ИмяНетерминала ’::=’ ПраваяЧастьПраваяЧасть ::= [( ЭлементПравойЧасти )]ЭлементПравойЧасти ::= ИмяНетерминала| Терминал| ’(’ Нетерминал [ ’/’ Терминал ] ’)’| ’[’ Нетерминал ’]’| ’[(’ Нетерминал [ ’/’ Терминал ] ’)]’Семантика ::= [(ЛокальноеОбъявление / ’;’)][( СемантическоеДействие / ’;’)]СемантическоеДействие ::= Присваивание| [ Метка ] ОператорПрисваивание ::= Переменная ’:=’ ВыражениеПеременная ::= ЛокальнаяПеременная| АтрибутАтрибут ::= ЛокальныйАтрибут| ГлобальныйАтрибутЛокальныйАтрибут ::= ИмяАтрибута ’<’ Номер ’>’ГлобальныйАтрибут ::= ИмяАтрибута ’<’ Нетерминал ’>’Метка ::= Целое ’:’| Целое ’Е’ ’:’| Целое ’А’ ’:’Оператор ::= Условный| ОператорПроцедуры| ЦиклПоМножеству| ПростойЦикл| ЦиклСУсловиемОкончанияОписание атрибутной грамматики состоит из раздела описания атрибутов и раздела правил.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
