Чисто синтезированные грамматики: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Чисто синтезированные грамматики''' (''Pure synthesized grammar'') - ''атрибутная грамма...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Чисто синтезированные грамматики''' (''Pure synthesized grammar'') - | '''Чисто синтезированные грамматики''' (''[[Pure synthesized grammar]]'') - | ||
''атрибутная грамматика'', в которой <math>I=\emptyset</math>. Аналогично атрибутная грамматика | ''[[атрибутная грамматика]]'', в которой <math>I=\emptyset</math>. Аналогично атрибутная грамматика | ||
называется ''чисто наследуемой'' (или <math>I</math>-''грамматикой''), | называется ''чисто наследуемой'' (или <math>I</math>-''грамматикой''), | ||
если <math>S=\emptyset</math>. | если <math>S=\emptyset</math>. | ||
Определения указанных классов грамматик имеют симметричный | Определения указанных классов грамматик имеют симметричный | ||
вид, однако только ''' | вид, однако только '''чисто синтезированные грамматики''' играют важную роль как с | ||
теоретической, так и с практической точки зрения. | теоретической, так и с практической точки зрения. | ||
Класс ''' | Класс '''чисто синтезированных грамматик''' по мощности не уступает ''[[машина Тьюринга|машинам Тьюринга]]''. | ||
''' | '''Чисто синтезированная грамматика''' не требует динамических построений, поскольку ей присущ | ||
определенный порядок вычисления атрибутов. | определенный порядок вычисления атрибутов. | ||
Реально может быть построена некоторая оптимальная по | Реально может быть построена некоторая оптимальная по | ||
времени система, которая объединяет синтаксический и | времени система, которая объединяет синтаксический и | ||
семантический анализы, например близкий к оптимальному | семантический анализы, например близкий к оптимальному | ||
восходящий вычислитель, линейный по размеру ''графа зависимости атрибутов'', или оптимальный нисходящий вычислитель, который может комбинироваться с методом разбора | восходящий вычислитель, линейный по размеру ''[[граф зависимости атрибутов|графа зависимости атрибутов]]'', или оптимальный нисходящий вычислитель, который может комбинироваться с методом разбора | ||
различных стратегий. | различных стратегий. | ||
Другое название --- <math>S</math>-''Грамматика''. | Другое название --- [[S-Грамматика|<math>S</math>-''Грамматика'']]. | ||
См. также ''Сильно ациклическая грамматика, <math>l</math>-Упорядоченные грамматики.'' | ==См. также == | ||
''[[Сильно ациклическая грамматика]], [[l-Упорядоченные грамматики|<math>l</math>-Упорядоченные грамматики]].'' | |||
==Литература== | ==Литература== | ||
[Евстигнеев-Касьянов/98] | [Евстигнеев-Касьянов/98] | ||
Версия от 13:48, 19 мая 2010
Чисто синтезированные грамматики (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]-Упорядоченные грамматики.
Литература
[Евстигнеев-Касьянов/98]