Сильно ациклическая грамматика

Сильно ациклическая грамматика (Strongly non-circular grammar) — атрибутная грамматика, для которой существует такое семейство частичных порядков [math]\displaystyle{ \{ R(X):X\in N\}, }[/math] что справедливы следующие два условия:

1) (ацикличность) для любой продукции [math]\displaystyle{ p\in P }[/math] является ациклическим

[math]\displaystyle{ R(X_1)\cup\ldots\cup R(X_{n\lt p\gt })\cup D(p), }[/math]

где [math]\displaystyle{ \,D(p) }[/math] — граф локальной зависимости;

2) (замкнутость) для любой продукции [math]\displaystyle{ p\in P }[/math] — ограничение отношения [math]\displaystyle{ [R(X_1)\cup\ldots\cup R(X_{n\lt p\gt })\cup D(p)]^+ }[/math] на [math]\displaystyle{ \,A(X_0) }[/math] является подмножеством [math]\displaystyle{ \,R(X_0), }[/math] т.е.

[math]\displaystyle{ [R(X_1)\cup\ldots\cup R(X_{n\lt p\gt })\cup D(p)]_{X_0}^+\subseteq R(X_0). }[/math]

Существует полиномиальный алгоритм для вычисления семейства минимальных [math]\displaystyle{ \,R(X) }[/math] для сильно ациклической грамматики. Наиболее интересной характеристикой грамматики, принадлежащей к классу сильно ациклической грамматики, является то, что реальные зависимости между наследуемыми и синтезируемыми атрибутами, индуцированные [math]\displaystyle{ \,R(t) }[/math] в дереве [math]\displaystyle{ \,t }[/math] с корнем [math]\displaystyle{ \,X }[/math], покрываются [math]\displaystyle{ \,R(X) }[/math]. Поэтому атрибутная грамматика эквивалентна множеству функций, рекурсивно определенных над структурой дерева [math]\displaystyle{ \,t }[/math].

Одно из преимуществ вычислителя сильно ациклической грамматики — то, что он нисходящий. Однако он может вычислять лишние наследуемые атрибуты, и его временная сложность является экспоненциальной от размера [math]\displaystyle{ \,W(t) }[/math], если не поддерживается информация о вычисленных переменных (та же ситуация, что и для [math]\displaystyle{ \,S }[/math]-грамматик). Некоторые экспериментальные исследования сильно ациклической грамматики и [math]\displaystyle{ \,l }[/math]-упорядоченных грамматик показали их сравнимость на практике.

Другие названия — Абсолютно ациклическая грамматика, [math]\displaystyle{ ANC }[/math]-грамматика, [math]\displaystyle{ SNC }[/math]-грамматика.

См. также

• [math]\displaystyle{ l }[/math]-Упорядоченные грамматики,
• Чисто синтезированные грамматики.

Литература

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