4194
правки
L-Упорядоченные грамматики: различия между версиями
Перейти к навигации
Перейти к поиску
L-Упорядоченные грамматики (посмотреть исходный код)
Версия от 11:36, 18 февраля 2010
, 18 февраля 2010нет описания правки
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] | ||