Изменения

|definition=Говорят, что к.с. грамматика <tex>\Gamma</tex> содержит левую рекурсию, если в ней существует вывод вида <tex>A \Rightarrow^* A\alpha</tex>.

}}

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

Приведем алгоритм, позволяющий для к.с. грамматики '''без &epsilon;-правил''' построить эквивалентную ей к.с. грамматику (без &epsilon;-правил), не содержащую левой рекурсии.

#Воспользоваться алгоритмом для новой грамматики

#Если <tex>\epsilon</tex> присутствовал в языке исходной грамматики, добавить новый начальный символ <tex>S'</tex> и правила <tex>S' \rightarrow S \, | \, \epsilon </tex>

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

Опишем процедуру, устраняющую все правила вида <tex>A \rightarrow A\alpha</tex> для фиксированного нетерминала <tex>A</tex>.

*<tex>B_i \rightarrow c \alpha </tex>, где <tex>c</tex> - терминал

*<tex>B_i \rightarrow B_j \alpha </tex>, где <tex>i < j</tex>