Теория и реализация языков программирования



             

Классы атрибутных грамматик и их реализация


В общем виде реализация вычислителей для атрибутных грамматик вызывает значительные трудности. Это связано с тем, что множество значений атрибутов, связанных с данным деревом, приходится вычислять в соответствии с зависимостями атрибутов, которые образуют ориентированный ациклический граф. На практике стараются осуществлять процесс вычисления атрибутов, привязывая его к тому или иному способу обхода дерева. Рассматривают многовизитные, многопроходные и другие атрибутные вычислители. Это, как правило, ведет к ограничению допустимых зависимостей между атрибутами, поддерживаемых вычислителем.

Простейшими подклассами атрибутных грамматик, вычисления всех атрибутов для которых может быть осуществлено одновременно с синтаксическим анализом, являются S-атрибутные и L-атрибутные грамматики. Определение. Атрибутная грамматика называется S- атрибутной, если она содержит только синтезируемые атрибуты.

Нетрудно видеть, что для S-атрибутной грамматики на любом дереве разбора все атрибуты могут быть вычислены за один обход дерева снизу вверх. Таким образом, вычисление атрибутов можно делать параллельно с восходящим синтаксическим анализом, например, LR(1)- анализом.

Пример 5.8. Рассмотрим S-атрибутную грамматику для перевода арифметических выражений в ПОЛИЗ. Здесь атрибут v имеет строковый тип, k - обозначает операцию конкатенации. Правила вывода и семантические правила определяются следующим образом

\begin{align*} &E^1 \rightarrow E^2 + T &&v(E^1) = v(E^2) \parallel v(T) \parallel \; '+' \\ &E \rightarrow T &&v(E) = v(T)\\ &T \rightarrow T * F &&v(T^1) = v(T^2) \parallel v(F) \parallel \; '*'\\ &T \rightarrow F &&v(T) = v(F) \\ &F \rightarrow id &&v(F) = v(id) \\ & F \rightarrow (E) &&v(F) = v(E) \end{align*}

Определение. Атрибутная грамматика называется 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; }




Содержание  Назад  Вперед