Алгоритм Устранение цепных правил

Вход: КС-грамматика .

Выход: Эквивалентная КС-грамматика без цепных правил, т.е. правил вида , где .

Шаг 1. Для каждого нетерминала вычислить множество выводимых из него нетерминалов, т.е. множество где

1.1 Положить

1.2 Вычислить

1.3 Если , то положить i:= i +1 и перейти к пункту 1.2, иначе считать

Шаг 2. Построить множество так: если не является цепным правилом , то включить в правило для каждого , такого, что .

Пример Грамматика с правилами . Преобразуем ее в эквивалентную грамматику по алгоритму 4.5.

Шаг 1.

Т.к. , то

Т.к. , то

Т.к. , то

Шаг 2. Преобразовав правила вывода грамматики, получим грамматику с правилами

.