Изменения

|definition=Говорят, что [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная(КС) грамматика]] <tex>\Gamma</tex> содержит '''непосредственную левую рекурсию''', если она содержит правило вида <tex>A \rightarrow Rightarrow A\alpha</tex>.

Методы нисходящего разбора(top=-down parsers) не в состоянии работать с леворекурсивными грамматиками. Проблема в том, что продукция вида <tex>A \Rightarrow^* A\alpha</tex> может применяться бесконечно долго, так и не выработав некий терминальный символ, который можно было бы сравнить со строкой. Поэтому требуется преобразование грамматики, которое бы устранило левую рекурсию.

Этот алгоритм не Нетерминал A порождает те же строки, что и ранее, но без левой рекурсии. Эта процедура устраняет произвольную левую рекурсиювсе непосредственные рекурсии из продукций для A,вызванную двумя или более шагами порожденияпри условии, что ни одна строка <tex>\alpha_i</tex> не является <tex>\epsilon</tex>.

<tex>A \rightarrow Ac|Sd|\epsilon</tex> S леворекурсивен, так как <tex>S \Rightarrow Aa \Rightarrow Sda</tex>, но эта рекурсия не является непосредственной. ==Устранение Алгоритм устранения произвольной левой рекурсии==Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{---}} упорядоченное множество всех нетерминалов.

==Алгоритм После <tex>i^ой</tex> итерации внешнего цикла в любой продукции вида <tex>A_k \rightarrow A_l\alpha<tex> где </tex> i > k будет l > k</tex>.В результате после каждой итерации растет нижний предел m, таких, что существует продукция вида <tex>A_i \rightarrow A_m\alpha</tex> до тех пор, пока не будет достигнуто <tex>m \geq i</tex>. Затем из <tex>A_i</tex> устраняется непосредственная левая рекурсия и достигается m > i. устранения левой рекурсии==