![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Нормальная форма ГрейбахНосит имя исследователя Greibach, предложившего эту нормальную форму. Определение. Контекстно свободная грамматика находится в нормальной форме Грейбах, если любое правило данной грамматики находится в одном из видов:
Пример грамматики в нормальной форме Грейбах. S->aST S->aT T->bS T->b Цепное правило — правило вида Алгоритм удаления цепных правил из грамматики: 1. Найти все цепные пары в грамматике 2. Для каждой цепной пары 3. Удалить все цепные правила Пример Рассмотрим грамматику: 1. Для каждого нетерминала создадим цепную пару. Теперь множество цепных пар будет состоять из 2. Рассмотрим цепное правило 3. Повторим второй пункт для правила 4. Повторим второй пункт для правила 5. Для каждой пары добавим в § § § § Оставшиеся цепные пары новых правил не добавят.
|