Устранение непосредственной левой рекурсии

Опишем процедуру, устраняющую все правила вида , для фиксированного нетерминала .

1. Запишем все правила вывода из в виде: , где

§ — непустая последовательность терминалов и нетерминалов ( );

§ — непустая последовательность терминалов и нетерминалов, не начинающаяся с .

2. Заменим правила вывода из на .

3. Создадим новый нетерминал .

Изначально нетерминал порождает сроки вида . В новой грамматике нетерминал порождает , а порождает строки вида . Из этого очевидно, что изначальная грамматика эквивалентна новой.

Пример

Есть непосредственная левая рекурсия . Добавим нетерминал и добавим правила , .

Новая грамматика:

В новой грамматике нет непосредственной левой рекурсии, но нетерминал леворекурсивен, так как есть