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

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

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

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

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

S->aST

S->aT

T->bS

T->b

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

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

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

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

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

Пример

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

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

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

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

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

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

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

§ для

§ и для

§ и для

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