Аноним

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

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


<math>p=X_0\longrightarrow
::::::<math>p=X_0\longrightarrow X_1\ldots X_{n<p>}\ ,</math>  
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>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>\,l</math>-упорядоченная, то для каждого [[дерево|дерева]] <math>\,t</math> порядок <math>\,T(t)</math>, полученный объединением порядков <math>\,T(p)</math>, является порядком вычисления. Можно реализовать вычислитель в виде последовательности, включающей вызовы для посещения [[поддерево|поддеревьев]] [[вершина|вершин]] в правых частях и вызовы для просмотра контекста. Такие последовательности называются ''визитными последовательностями'' и ассоциируются с каждой продукцией. Указанный вычислитель является эффективным восходящим, неоптимальным по времени, но линейным по размеру ''[[граф зависимости атрибутов|графа зависимости атрибутов]]'', без повторных вычислений и затрат на разработку плана.
порядок <math>T(t)</math>, полученный объединением порядков <math>T(p)</math>,
является порядком вычисления. Можно реализовать вычислитель
в виде последовательности, включающей вызовы для посещения
[[поддерево|поддеревьев]] [[вершина|вершин]] в правых частях и вызовы для просмотра
контекста. Такие последовательности называются  
''визитными последовательностями'' и ассоциируются с каждой
продукцией. Указанный вычислитель является эффективным
восходящим, неоптимальным по времени, но линейным по размеру
''[[граф зависимости атрибутов|графа зависимости атрибутов]]'', без повторных вычислений
и затрат на разработку плана.


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


==См. также ==
==См. также ==
''[[Сильно ациклическая грамматика]], [[Чисто синтезированные грамматики]]''.
* ''[[Сильно ациклическая грамматика]],''
* ''[[Чисто синтезированные грамматики]].''
==Литература==
==Литература==
[Евстигнеев-Касьянов/98]
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998.