Алгоритм Устранение левой факторизации правил

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

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

Шаг 1. Записать все правила для нетерминала , имеющие одинаковые префиксы , в виде одного правила с альтернативами:

Шаг 2. Вынести за скобки влево префикс в каждой строке-альтернативе:

Шаг 3. Обозначить новым нетерминалом выражение, оставшееся в скобках:

Шаг 4. Пополнить множество нетерминалов новым нетерминалом и заменить правила, подвергшиеся факторизации, новыми правилами для и .

Шаг 5. Повторить шаги 1-4 для всех нетерминалов грамматики, для которых это возможно и необходимо.

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

Шаг 1. .

Шаг 2. .

Шаг 3,4. Пополнив множество нетерминалов новым нетерминалом С и заменив правила, подвергшиеся факторизации, получим грамматику с правилами