Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Нормальная форма Грейбах




Носит имя исследователя Greibach, предложившего эту нормальную форму.

Определение. Контекстно свободная грамматика находится в нормальной форме Грейбах, если любое правило данной грамматики находится в одном из видов:

- на первом месте — терминал.

Пример грамматики в нормальной форме Грейбах.

S->aST

S->aT

T->bS

T->b

Цепное правило — правило вида , где и — нетерминалы.

Алгоритм удаления цепных правил из грамматики:

1. Найти все цепные пары в грамматике .

2. Для каждой цепной пары добавить в грамматику все правила вида , где — нецепное правило из .

3. Удалить все цепные правила

Пример

Рассмотрим грамматику: , в которой есть два цепных правила и .

1. Для каждого нетерминала создадим цепную пару. Теперь множество цепных пар будет

состоять из , , и .

2. Рассмотрим цепное правило . Так как существует цепная пара , второй элемент которой совпадает с левым нетерминалом из правила,
добавим в множество пару , у которой первый элемент такой же как у найденной, а второй равен правому нетерминалу из текущего правила.

3. Повторим второй пункт для правила и пары . Теперь множество цепных пар будет состоять из , , , , и .

4. Повторим второй пункт для правила и пары , и получим множество .

5. Для каждой пары добавим в новые правила:

§ для

§ и для

§ и для

§ Оставшиеся цепные пары новых правил не добавят.

 


Поделиться:

Дата добавления: 2015-01-29; просмотров: 247; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2023 год. (0.012 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты