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

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

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.