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

'''Чисто синтезированные грамматики''' (''[[Pure synthesized grammar]]'') — ''[[атрибутная грамматика]]'', в которой <math>I=\emptyset</math>. Аналогично атрибутная грамматика называется ''чисто наследуемой'' (или <math>I</math>-''грамматикой''), если <math>S=\emptyset</math>.

Определения указанных классов грамматик имеют симметричный вид, однако только '''чисто синтезированные грамматики''' играют важную роль как с теоретической, так и с практической точки зрения. Класс '''чисто синтезированных грамматик''' по мощности не уступает ''[[машина Тьюринга|машинам Тьюринга]]''. '''Чисто синтезированная грамматика''' не требует динамических построений, поскольку  ей присущ определенный порядок вычисления атрибутов. Реально может быть построена некоторая оптимальная по времени система, которая объединяет синтаксический и семантический анализы, например близкий к оптимальному восходящий вычислитель, линейный по размеру ''[[граф зависимости атрибутов|графа зависимости атрибутов]]'', или оптимальный нисходящий вычислитель, который может комбинироваться с методом разбора различных стратегий.

Другое название — [[S-Грамматика|<math>S</math>-''Грамматика'']].

* ''[[Сильно ациклическая грамматика]],''

* ''[[l-Упорядоченные грамматики|<math>l</math>-Упорядоченные грамматики]].''

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