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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''<math>l</math>-Упорядоченные грамматики''' (''<math>l</math>-Ordered grammar'') - ''атрибутная гра...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''<math>l</math>-Упорядоченные грамматики''' (''<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.