Сильно ациклическая грамматика: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Сильно ациклическая грамматика''' (''Strongly non-circular grammar'') - атрибутная грамма...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Сильно ациклическая грамматика''' (''Strongly non-circular grammar'') - | '''Сильно ациклическая грамматика''' (''[[Strongly non-circular grammar]]'') - | ||
атрибутная грамматика, для которой существует такое семейство | [[атрибутная грамматика]], для которой существует такое семейство | ||
частичных порядков <math>\{ R(X):X\in N\}</math>, что справедливы | частичных порядков <math>\{ R(X):X\in N\}</math>, что справедливы | ||
следующие два условия: | следующие два условия: | ||
| Строка 9: | Строка 9: | ||
<math>R(X_1)\cup\ldots\cup R(X_{n<p>})\cup D(p),</math> | <math>R(X_1)\cup\ldots\cup R(X_{n<p>})\cup D(p),</math> | ||
где <math>D(p)</math> --- ''граф локальной зависимости''; | где <math>D(p)</math> --- ''[[граф локальной зависимости]]''; | ||
2) (''замкнутость'') для любой продукции <math>p\in P</math> --- ограничение | 2) (''замкнутость'') для любой продукции <math>p\in P</math> --- ограничение | ||
| Строка 23: | Строка 23: | ||
принадлежащей к классу | принадлежащей к классу | ||
'''С.а.г.''', является то, что реальные | '''С.а.г.''', является то, что реальные | ||
зависимости между наследуемыми и синтезируемыми атрибутами, | зависимости между [[наследуемый атрибут|наследуемыми]] и [[синтезируемый атрибут|синтезируемыми атрибутами]], | ||
индуцированные <math>R(t)</math> в дереве <math>t</math> с корнем <math>X</math>, покрываются | индуцированные <math>R(t)</math> в [[дерево|дереве]] <math>t</math> с [[корень|корнем]] <math>X</math>, покрываются | ||
<math>R(X)</math>. Поэтому | <math>R(X)</math>. Поэтому | ||
атрибутная грамматика эквивалентна множеству | атрибутная грамматика эквивалентна множеству | ||
| Строка 38: | Строка 38: | ||
сравнимость на практике. | сравнимость на практике. | ||
Другие названия --- ''Абсолютно ациклическая грамматика, <math>ANC</math>-грамматика, <math>SNC</math>-грамматика''. | Другие названия --- ''[[Абсолютно ациклическая грамматика]], [[ANC-Грамматика|<math>ANC</math>-грамматика]], [[SNC-Грамматика|<math>SNC</math>-грамматика]]''. | ||
См. также '' <math>l</math>-Упорядоченные грамматики, Чисто синтезированные грамматики.'' | ==См. также == | ||
'' [[l-Упорядоченные грамматики|<math>l</math>-Упорядоченные грамматики]], [[Чисто синтезированные грамматики]].'' | |||
==Литература== | ==Литература== | ||
[Евстигнеев-Касьянов/98] | [Евстигнеев-Касьянов/98] | ||
Версия от 19:11, 29 января 2010
Сильно ациклическая грамматика (Strongly non-circular grammar) - атрибутная грамматика, для которой существует такое семейство частичных порядков [math]\displaystyle{ \{ R(X):X\in N\} }[/math], что справедливы следующие два условия:
1) (ацикличность) для любой продукции [math]\displaystyle{ p\in P }[/math] является ациклическим
[math]\displaystyle{ R(X_1)\cup\ldots\cup R(X_{n\lt p\gt })\cup D(p), }[/math]
где [math]\displaystyle{ D(p) }[/math] --- граф локальной зависимости;
2) (замкнутость) для любой продукции [math]\displaystyle{ p\in P }[/math] --- ограничение отношения [math]\displaystyle{ [R(X_1)\cup\ldots\cup R(X_{n\lt p\gt })\cup D(p)]^+ }[/math] на [math]\displaystyle{ A(X_0) }[/math] является подмножеством [math]\displaystyle{ R(X_0) }[/math], т.е.
[math]\displaystyle{ [R(X_1)\cup\ldots\cup R(X_{n\lt p\gt })\cup D(p)]_{X_0}^+\subseteq R(X_0). }[/math]
Существует полиномиальный алгоритм для вычисления семейства минимальных [math]\displaystyle{ R(X) }[/math] для С.а.г. Наиболее интересной характеристикой грамматики, принадлежащей к классу С.а.г., является то, что реальные зависимости между наследуемыми и синтезируемыми атрибутами, индуцированные [math]\displaystyle{ R(t) }[/math] в дереве [math]\displaystyle{ t }[/math] с корнем [math]\displaystyle{ X }[/math], покрываются [math]\displaystyle{ R(X) }[/math]. Поэтому атрибутная грамматика эквивалентна множеству функций, рекурсивно определенных над структурой дерева [math]\displaystyle{ t }[/math].
Одно из преимуществ вычислителя С.а.г. --- то, что он нисходящий. Однако он может вычислять лишние наследуемые атрибуты, и его временная сложность является экспоненциальной от размера [math]\displaystyle{ W(t) }[/math], если не поддерживается информация о вычисленных переменных (та же ситуация, что и для [math]\displaystyle{ S }[/math]-грамматик). Некоторые экспериментальные исследования С.а.г. и [math]\displaystyle{ l }[/math]-упорядоченных грамматик показали их сравнимость на практике.
Другие названия --- Абсолютно ациклическая грамматика, [math]\displaystyle{ ANC }[/math]-грамматика, [math]\displaystyle{ SNC }[/math]-грамматика.
См. также
[math]\displaystyle{ l }[/math]-Упорядоченные грамматики, Чисто синтезированные грамматики.
Литература
[Евстигнеев-Касьянов/98]