Определение атрибутных грамматик

Атрибутной грамматикой называется четверка AG = (G, A_S, A_I, R), где

1. G = (N, T, P, S) - приведенная КС-грамматика;

2. A_S - конечное множество синтезируемых атрибутов;

3. A_I - конечное множество наследуемых атрибутов, ;

4. R - конечное множество семантических правил.

Атрибутная грамматика AG сопоставляет каждому символу X из множество A_S(X) синтезируемых атрибутов и множество A_I (X) наследуемых атрибутов. Множество всех синтезируемых атрибутов всех символов из обозначаетсяA_S, наследуемых - A_I. Атрибуты разных символов являются различными атрибутами. Будем обозначать атрибут a символа X какa(X). Значения атрибутов могут быть произвольных типов, например, представлять собой числа, строки, адреса памяти и т.д.

Пусть правило p из P имеет вид X₀ -> X₁X₂... X_n. Атрибутная грамматика AG сопоставляет каждому правилу p из Pконечное множество R(p) семантических правил вида

a(X_i) = f(b(X_j), c(X_k),..., d(X_m))

где 0 < = j, k,..., m < = n, причем 1 < = i < = n, если (то есть a(X_i) - наследуемый атрибут), иi = 0, если (то есть a(X_i) - синтезируемый атрибут).

Таким образом, семантическое правило определяет значение атрибута a символа X_i на основе значений атрибутов b, c,..., d символов X_j, X_k,..., X_m соответственно.

В частном случае длина n правой части правила может быть равна нулю, тогда будем говорить, что атрибут a символа X_i" получает в качестве значения константу".

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

Пример 5.5. Рассмотрим атрибутную грамматику, позволяющую вычислить значение вещественного числа, представленного в десятичной записи. Здесь N = {Num, Int, Frac}, T = {digit,.}, S = Num, а правила вывода и семантические правила определяются следующим образом (верхние индексы используются для ссылки на разные вхождения одного и того же нетерминала):

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

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

Рис. 5.2.

Пусть теперь X - метка некоторого узла дерева и пусть a - атрибут символа X. Если a - синтезируемый атрибут, то X = X₀для некоторого ; если же a - наследуемый атрибут, то X = X_j для некоторых и 1 < = j < = n. В обоих случаях дерево " в районе" этого узла имеет вид, приведенный на рис. 5.2. По определению, атрибут a имеет в этом узле значениеv, если в соответствующем семантическом правиле

a(X_i) = f(b(X_j), c(X_k),..., d(X_m))

все атрибуты b, c,..., d уже определены и имеют в узлах с метками X_j, X_k,..., X_m значения v_j, v_k,..., v_mсоответственно, а v = f(v₁, v₂,..., v_m). Процесс вычисления атрибутов на дереве продолжается до тех пор, пока нельзя будет вычислить больше ни одного атрибута. Вычисленные в результате атрибуты корня дерева представляют собой " значение", соответствующее данному дереву вывода.

Заметим, что значение синтезируемого атрибута символа в узле синтаксического дерева вычисляется по атрибутам символов в потомках этого узла; значение наследуемого атрибута вычисляется по атрибутам " родителя" и " соседей".

Атрибуты, сопоставленные вхождениям символов в дерево разбора, будем называть вхождениями атрибутов в дерево разбора, а дерево с сопоставленными каждой вершине атрибутами - атрибутированным деревом разбора.

Пример 5.6. Атрибутированное дерево для грамматики из предыдущего примера и цепочки w = 12: 34 показано на рис. 5.3.

Рис. 5.3.

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

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

Пусть T - дерево разбора. Сопоставим этому дереву ориентированный граф D(T), узлами которого являются пары (n; a), гдеn - узел дерева T, a - атрибут символа, служащего меткой узла n. Граф содержит дугу из (n₁, a₁) в (n₂, a₂) тогда и только тогда, когда семантическое правило, вычисляющее атрибут a₂, непосредственно использует значение атрибута a₁. Таким образом, узлами графа D(T) являются атрибуты, которые нужно вычислить, а дуги определяют зависимости, подразумевающие, какие атрибуты вычисляются раньше, а какие позже.

Пример 5.7. Граф зависимостей атрибутов для дерева разбора из предыдущего примера показан на рис. 5.4.

Рис. 5.4.

Можно показать, что семантические правила являются корректными тогда и только тогда, когда для любого дерева вывода Tсоответствующий граф D(T) не содержит циклов (то есть является ориентированным ациклическим графом).