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