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



             

Определение атрибутных грамматик - часть 2


\begin{align*} &Num \rightarrow Int . Frac &v&(Num) = v(Int) + v(Frac) \\ & &p&(Frac) = 1\\ &Int \rightarrow e &v&(Int) = 0 \\ & &p&(Int) = 0 \\ &Int^1 \rightarrow digit \; Int^2 &v&(Int^1) = v(digit) * 10^{p(Int^{2})} + v(Int^2)\\ & &p&(Int^1) = p(Int^2) + 1 \\ &Frac \rightarrow e &v&(Frac) = 0 \\ &Frac^1 \rightarrow digitFrac^2 &v&(Frac^1)= v(digit) * 10^{-p(Frac^1)}+ v(Frac^2)\\ & &p&(Frac^2)= p(Frac^1) + 1 \\ \end{align*}

Для этой грамматики

\begin{align*} &A_S(Num) = \{v\}, &&AI (Num) = \oslash,\\ &A_S(Int) = \{v, p\}, &&A_I (Int) =\oslash,\\ &A_S(Frac) = \{v\}, &&A_I (Frac) = \{p\}. \end{align*}

Пусть дана атрибутная грамматика AG и цепочка, принадлежащая языку, определяемому соответствующей G = (N, T, P, S). Сопоставим этой цепочке "значение "следующим образом. Построим дерево разбора T этой цепочки в грамматике G. Каждый внутренний узел этого дерева помечается нетерминалом X0, соответствующим применению p-го правила грамматики; таким образом, у этого узла будет n непосредственных потомков (рис. 5.2).


Рис. 5.2. 

Пусть теперь X - метка некоторого узла дерева и пусть a - атрибут символа X. Если a - синтезируемый атрибут, то X = X0 для некоторого

p \in P
; если же a - наследуемый атрибут, то X = Xj для некоторых
p \in P
и 1
j
n. В обоих случаях дерево "в районе" этого узла имеет вид, приведенный на рис. 5.2. По определению, атрибут 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.6. Атрибутированное дерево для грамматики из предыдущего примера и цепочки w = 12:34 показано на рис. 5.3.


Рис. 5.3. 

Будем говорить, что семантические правила заданы корректно, если они позволяют вычислить все атрибуты произвольного узла в любом дереве вывода.




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