Алгоритм Устранение прямой левой рекурсии

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

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

Шаг 1. Вывести из грамматики все правила для рекурсивного нетерминала :

Шаг 2. Внести новый нетерминал так, чтобы он описывал любой «хвост» строки, порождаемой рекурсивным нетерминалом :

Шаг 3. Заменить в рекурсивном правиле для правую часть, используя новый нетерминал и все нерекурсивные правила для так, чтобы генерируемый язык не изменился:

Шаг 4. Пополнить множество нетерминалов грамматики новым нетерминалом . Пополнить множество правил грамматики правилами, полученными на шаге 3.

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

Пример Данаграмматика с правилами .

Шаг алгор. Действия и результ.

1.

2.

3.

4. V_N = { S,A,B,C,Z }, P’=

После устранения прямой левой рекурсии получим эквивалентную грамматику с правилами