L-Упорядоченные грамматики

$l$-Упорядоченные грамматики ($l$-Ordered grammar) — атрибутная грамматика, если существует семейство общих порядков $\,\{ T(X)\}$ для $X\in N$ такое, что для любого $p\in P$, где

$p=X_0\longrightarrow X_1\ldots X_{n<p>}\ ,$

является ациклическим

$T(p)=T(X_0)\cup T(X_1)\cup\ldots\cup T(X_{n<p>})\cup D(p).$

Если грамматика $\,l$-упорядоченная, то для каждого дерева $\,t$ порядок $\,T(t)$, полученный объединением порядков $\,T(p)$, является порядком вычисления. Можно реализовать вычислитель в виде последовательности, включающей вызовы для посещения поддеревьев вершин в правых частях и вызовы для просмотра контекста. Такие последовательности называются визитными последовательностями и ассоциируются с каждой продукцией. Указанный вычислитель является эффективным восходящим, неоптимальным по времени, но линейным по размеру графа зависимости атрибутов, без повторных вычислений и затрат на разработку плана.

Любая ациклическая атрибутная грамматика может быть преобразована в эквивалентную $\,l$-упорядоченную грамматику, причем с теми же семантическими определениями, но имеющую экспоненциальный размер.

См. также

• Сильно ациклическая грамматика,
• Чисто синтезированные грамматики.

Литература

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