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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Чисто синтезированные грамматики''' (''Pure synthesized grammar'') - ''атрибутная грамма...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Чисто синтезированные грамматики''' (''Pure synthesized grammar'') -
'''Чисто синтезированные грамматики''' (''[[Pure synthesized grammar]]'') ''[[атрибутная грамматика]]'', в которой <math>I=\emptyset</math>. Аналогично атрибутная грамматика называется ''чисто наследуемой'' (или <math>I</math>-''грамматикой''), если <math>S=\emptyset</math>.
''атрибутная грамматика'', в которой <math>I=\emptyset</math>. Аналогично атрибутная грамматика
называется ''чисто наследуемой'' (или <math>I</math>-''грамматикой''),
если <math>S=\emptyset</math>.


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


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


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

Текущая версия от 16:20, 11 октября 2011

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

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

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

См. также

Литература

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