L-Упорядоченные грамматики: различия между версиями

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

::::::<math>p=X_0\longrightarrow X_1\ldots X_{n<p>}\ ,</math>  

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

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

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

* ''[[Сильно ациклическая грамматика]],''

* ''[[Чисто синтезированные грамматики]].''

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