Атрибутная грамматика

Материал из WikiGrapp
Перейти к:навигация, поиск

Атрибутная грамматика (Attribute grammar) — состоит из КС-грамматики G, называемой ее основой (или базой), отображений S и I, ставящих в соответствие каждому символу X непересекающиеся множества S(X) и I(X) его синтезируемых и наследуемых атрибутов, а также из множеств M(p) так называемых семантических правил (правил вычисления значений атрибутов) для каждого правила p\in P.


Пусть p:X_0\longrightarrow X_1X_2\ldots X_{n<p>} — некоторое правило грамматики G. Говорят, что имеется вхождение атрибута a при j-м символе X_j правила p (обозначается a<j>), если a\in A(X_j)=I(X_j)\cup S(X_j). Для a<j> иногда используются также обозначения X_j.a и a^{X_j}. Множество M(p) состоит из семантических правил, определяющих вычисление элементов из S(X_0) и I(X_j) для j\in [1,n<p>] в терминах элементов A(X_i), 0\leq i\leq
n<p>, и имеющих вид


a_0<i_0>=f^{p}_{a_0<i_0>} (a_1<i_1>,\ldots , a_{k}<i_{k}>),


где либо i_0=0 и a_0\in S(X_0), либо 1\leq
i_0\leq n<p> и a_0\in I(X_{i_0}).

Если M(p) содержит семантическое правило, определяющее вычисление a_0<i_0> по a_1<i_1>,\ldots , a_k<i_k>, то говорят, что a_0<i_0> локально зависит от a_1<i_1>,\ldots, a_k<i_k>. В частном случае k может быть равно нулю, и тогда говорят, что атрибут a_0<i_0> получает в качестве значения константу.

Пусть W(p) обозначает множество вхождений атрибутов в правило p, т.е. W(p)=\{ a<i>:a\in A(X_i), 0\leq i\leq n<p>\}. Таким образом, семантические правила из M(p) индуцируют на W(p) отношение локальной зависимости D(p) такое, что b<j>D(p)a<i> тогда и только тогда, когда b<j> появляется в определении a<i>.

Граф локальной зависимости в продукции p — это граф отношения D(p) на множестве W(p).

Атрибутная грамматика является грамматикой в нормальной форме (или нормализованной), если ее семантические правила определяют вычисления атрибутов из W(p) по атрибутам из I(X_0) и S(X_j) для 1\leq j\leq n<p>, т.е. они используют только атрибуты, определенные вне продукции p. Всякая атрибутная грамматика может быть преобразована в нормальную форму посредством простого преобразования семантических определений, если D(p) является ациклическим.

См. также

Литература

  • Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998.