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

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

Сильно ациклическая грамматика (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-упорядоченных грамматик показали их сравнимость на практике.

Другие названия — Абсолютно ациклическая грамматика, ANC-грамматика, SNC-грамматика.

См. также

Литература

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