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

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

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

[math]\displaystyle{ a_0\lt i_0\gt =f^{p}_{a_0\lt i_0\gt } (a_1\lt i_1\gt ,\ldots , a_{k}\lt i_{k}\gt ), }[/math]

где либо [math]\displaystyle{ i_0=0 }[/math] и [math]\displaystyle{ a_0\in S(X_0) }[/math], либо [math]\displaystyle{ 1\leq i_0\leq n\lt p\gt }[/math] и [math]\displaystyle{ a_0\in I(X_{i_0}) }[/math].

Если [math]\displaystyle{ M(p) }[/math] содержит семантическое правило, определяющее вычисление [math]\displaystyle{ a_0\lt i_0\gt }[/math] по [math]\displaystyle{ a_1\lt i_1\gt ,\ldots , a_k\lt i_k\gt }[/math], то говорят, что [math]\displaystyle{ a_0\lt i_0\gt }[/math] локально зависит от [math]\displaystyle{ a_1\lt i_1\gt }[/math],[math]\displaystyle{ \ldots }[/math], [math]\displaystyle{ a_k\lt i_k\gt }[/math]. В частном случае [math]\displaystyle{ k }[/math] может быть равно нулю, и тогда говорят, что атрибут [math]\displaystyle{ a_0\lt i_0\gt }[/math] получает в качестве значения константу.

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

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

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

См. также

• Атрибутное дерево,
• Атрибутное вычисление,
• Задача трансляции.

Литература

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