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

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

[math]\displaystyle{ p=X_0\longrightarrow X_1\ldots X_{n\lt p\gt }\ , }[/math]

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

[math]\displaystyle{ T(p)=T(X_0)\cup T(X_1)\cup\ldots\cup T(X_{n\lt p\gt })\cup D(p). }[/math]

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

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

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

Литература

[Евстигнеев-Касьянов/98]