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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''<math>l</math>-Упорядоченные грамматики''' (''<math>l</math>-Ordered grammar'') - ''атрибутная гра...)
 
Нет описания правки
Строка 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>, где  
Строка 11: Строка 11:
<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]
[Евстигнеев-Касьянов/98]

Версия от 11:36, 18 февраля 2010

[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]