L-Упорядоченные грамматики

Материал из WikiGrapp
Версия от 15:16, 9 февраля 2010; Glk (обсуждение | вклад) (Создана новая страница размером '''<math>l</math>-Упорядоченные грамматики''' (''<math>l</math>-Ordered grammar'') - ''атрибутная гра...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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