Вход: КС-грамматика .
Выход: Эквивалентная КС-грамматика без цепных правил, т.е. правил вида , где .
Шаг 1. Для каждого нетерминала вычислить множество выводимых из него нетерминалов, т.е. множество где
1.1 Положить
1.2 Вычислить
1.3 Если , то положить i:= i +1 и перейти к пункту 1.2, иначе считать
Шаг 2. Построить множество так: если не является цепным правилом , то включить в правило для каждого , такого, что .
Пример Грамматика с правилами . Преобразуем ее в эквивалентную грамматику по алгоритму 4.5.
Шаг 1.
Т.к. , то
Т.к. , то
Т.к. , то
Шаг 2. Преобразовав правила вывода грамматики, получим грамматику с правилами
.