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

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

1) (ацикличность) для любой продукции $p\in P$ является ациклическим

R(X_1)\cup\ldots\cup R(X_{n<p>})\cup D(p),

где $\,D(p)$ — граф локальной зависимости;

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

[R(X_1)\cup\ldots\cup R(X_{n<p>})\cup D(p)]_{X_0}^+\subseteq R(X_0).

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

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