Чисто синтезированные грамматики

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

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

Другое название — [math]\displaystyle{ S }[/math]-Грамматика.

См. также

• Сильно ациклическая грамматика,
• [math]\displaystyle{ l }[/math]-Упорядоченные грамматики.

Литература

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