Изменения
→Алгоритм устранения произвольной левой рекурсии
Если <tex>\varepsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \to S \, | \, \varepsilon </tex>.
После <tex>i</tex> итерации внешнего цикла в любой продукции внешнего цикла в любой продукции вида <tex>A_k \to A_l\alpha, k < i</tex>, должно быть <tex>l > k</tex>. В результате при следующей итерации внутреннего цикла растет нижний предел <tex>m</tex> всех продукций вида <tex>A_i \to A_m\alpha</tex> до тех пор, пока не будет достигнуто <tex>i \le m </tex>.
После <tex>i</tex> итерации внешнего цикла в грамматике будут только правила вида <tex>A_i \to A_j\alpha</tex>, где <tex>j > i</tex>.
Можно заметить, что неравенство становится строгим только после применения алгоритма устранения непосредственной левой рекурсии. При этом добавляются новые нетерминалы. Пусть <tex>{A^\prime}_i </tex> новый нетерминал. Можно заметить, что нет правила вида <tex>\ldots \to {A^\prime}_i</tex>, где <tex>{A^\prime}_i</tex> самый левый нетерминал, а значит новые нетерминалы можно не рассматривать во внешнем цикле.
