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

Вход

• Эпсилон-свободная грамматика $G=(\Sigma ,\Gamma ,P,S)$, $\Gamma =\{A_i{\}}_{i=1}^n,A_1=S$

Выход

• Контекстно-свободная грамматика $G^{\prime }=(\Sigma ,{\Gamma }^{\prime },P^{\prime },S)$ без левой рекурсии

Алгоритм

$A_{-i}$ - добавляемые на $i$-ой итерации нетерминалы. Имеют отрицательный индекс, чтобы не участвовать в основном цикле. Гарантируется, что с их участием левой рекурсии не возникнет

Обоснование

пох?

Практика

На практике более хорошо алгоритм удаления левой рекурсии описан на сайте итмо.

Для работы алгоритма также необходим алгоритм из леммы