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.

Текущая версия от 11:40, 23 сентября 2011

[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]-упорядоченную грамматику, причем с теми же семантическими определениями, но имеющую экспоненциальный размер.

См. также

Литература

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