Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Классы атрибутных грамматик и их реализация
|
|
В общем виде реализация вычислителей для атрибутных грамматик вызывает значительные трудности. Это связано с тем, что множество значений атрибутов, связанных с данным деревом, приходится вычислять в соответствии с зависимостями атрибутов, которые образуют ориентированный ациклический граф. На практике стараются осуществлять процесс вычисления атрибутов, привязывая его к тому или иному способу обхода дерева. Рассматривают многовизитные, многопроходные и другие атрибутные вычислители. Это, как правило, ведет к ограничению допустимых зависимостей между атрибутами, поддерживаемых вычислителем.
Простейшими подклассами атрибутных грамматик, вычисления всех атрибутов для которых может быть осуществлено одновременно с синтаксическим анализом, являются S -атрибутные и L -атрибутные грамматики. Определение. Атрибутная грамматика называется S - атрибутной, если она содержит только синтезируемые атрибуты.
Нетрудно видеть, что для S -атрибутной грамматики на любом дереве разбора все атрибуты могут быть вычислены за один обход дерева снизу вверх. Таким образом, вычисление атрибутов можно делать параллельно с восходящим синтаксическим анализом, например, LR(1)- анализом.
Пример 5.8. Рассмотрим S -атрибутную грамматику для перевода арифметических выражений в ПОЛИЗ. Здесь атрибут v имеет строковый тип, k - обозначает операцию конкатенации. Правила вывода и семантические правила определяются следующим образом
Определение. Атрибутная грамматика называется L - атрибутной, если любой наследуемый атрибут любого символа Xj из правой части каждого правила X0 -> X1X2... Xn грамматики зависит только от
1. атрибутов символов X1, X2,..., Xj-1, находящихся в правиле слева от Xj, и
2. наследуемых атрибутов символа X0.
Заметим, что каждая S -атрибутная грамматика является L -атрибутной. Все атрибуты на любом дереве для L - атрибутной грамматики могут быть вычислены за один обход дерева сверху-вниз слева-направо. Таким образом, вычисление атрибутов можно осуществлять параллельно с нисходящим синтаксическим анализом, например, LL(1)- анализом или рекурсивным спуском.
В случае рекурсивного спуска в каждой функции, соответствующей нетерминалу, надо определить формальные параметры, передаваемые по значению, для наследуемых атрибутов, и формальные параметры, передаваемые по ссылке, для синтезируемых атрибутов. В качестве примера рассмотрим реализацию атрибутной грамматики из примера 5.5 (нетрудно видеть, что грамматика является L -атрибутной).
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; }|
|