Сильно ациклическая грамматика: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Сильно ациклическая грамматика''' (''[[Strongly non-circular grammar]]'') -
'''Сильно ациклическая грамматика''' (''[[Strongly non-circular grammar]]'')
[[атрибутная грамматика]], для которой существует такое семейство
[[атрибутная грамматика]], для которой существует такое семейство
частичных порядков <math>\{ R(X):X\in N\}</math>, что справедливы
частичных порядков <math>\{ R(X):X\in N\},</math> что справедливы
следующие два условия:
следующие два условия:


1) (''ацикличность'') для любой продукции <math>p\in P</math> является
1) (''ацикличность'') для любой продукции <math>p\in P</math> является ациклическим
ациклическим


<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> ограничение
отношения <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>A(X_0)</math> является подмножеством <math>R(X_0)</math>, т.е.
<math>\,A(X_0)</math> является подмножеством <math>\,R(X_0),</math> т.е.


<math>[R(X_1)\cup\ldots\cup R(X_{n<p>})\cup D(p)]_{X_0}^+\subseteq R(X_0).</math>
::<math>[R(X_1)\cup\ldots\cup R(X_{n<p>})\cup D(p)]_{X_0}^+\subseteq R(X_0).</math>


Существует полиномиальный алгоритм для вычисления семейства
Существует полиномиальный алгоритм для вычисления семейства
минимальных <math>R(X)</math> для
минимальных <math>\,R(X)</math> для
'''С.а.г.'''
'''сильно ациклической грамматики'''.
Наиболее интересной характеристикой грамматики,
Наиболее интересной характеристикой грамматики,
принадлежащей к классу
принадлежащей к классу
'''С.а.г.''', является то, что реальные
'''сильно ациклической грамматики''', является то, что реальные
зависимости между  [[наследуемый атрибут|наследуемыми]] и [[синтезируемый атрибут|синтезируемыми атрибутами]],
зависимости между  [[наследуемый атрибут|наследуемыми]] и [[синтезируемый атрибут|синтезируемыми атрибутами]],
индуцированные <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>. Поэтому
атрибутная грамматика эквивалентна множеству
атрибутная грамматика эквивалентна множеству
функций, рекурсивно определенных над структурой дерева <math>t</math>.
функций, рекурсивно определенных над структурой дерева <math>\,t</math>.


Одно из преимуществ вычислителя '''С.а.г.''' --- то, что он
Одно из преимуществ вычислителя '''сильно ациклической грамматики''' то, что он
нисходящий. Однако он может вычислять лишние наследуемые
нисходящий. Однако он может вычислять лишние наследуемые
атрибуты, и его временная сложность является
атрибуты, и его временная сложность является
экспоненциальной от размера <math>W(t)</math>, если не поддерживается
экспоненциальной от размера <math>\,W(t)</math>, если не поддерживается
информация о вычисленных переменных (та же ситуация, что и
информация о вычисленных переменных (та же ситуация, что и
для <math>S</math>-грамматик). Некоторые экспериментальные исследования
для <math>\,S</math>-грамматик). Некоторые экспериментальные исследования
'''С.а.г.''' и <math>l</math>-упорядоченных грамматик показали их
'''сильно ациклической грамматики''' и <math>\,l</math>-упорядоченных грамматик показали их
сравнимость на практике.
сравнимость на практике.


Другие названия --- ''[[Абсолютно ациклическая грамматика]], [[ANC-Грамматика|<math>ANC</math>-грамматика]], [[SNC-Грамматика|<math>SNC</math>-грамматика]]''.
Другие названия ''[[Абсолютно ациклическая грамматика]], [[ANC-Грамматика|<math>ANC</math>-грамматика]], [[SNC-Грамматика|<math>SNC</math>-грамматика]]''.


==См. также ==
==См. также ==
'' [[l-Упорядоченные грамматики|<math>l</math>-Упорядоченные грамматики]], [[Чисто синтезированные грамматики]].''
* ''[[l-Упорядоченные грамматики|<math>l</math>-Упорядоченные грамматики]],''
* ''[[Чисто синтезированные грамматики]].''
==Литература==
==Литература==
[Евстигнеев-Касьянов/98]
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998.

Текущая версия от 12:39, 2 сентября 2011

Сильно ациклическая грамматика (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]-грамматика.

См. также

Литература

  • Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998.