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

Перейти к навигации Перейти к поиску
нет описания правки
(Создана новая страница размером '''Сильно ациклическая грамматика''' (''Strongly non-circular grammar'') - атрибутная грамма...)
 
Нет описания правки
Строка 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]

Навигация