Editing Left recursion (section)

=== Removing all left recursion ===
The above process can be extended to eliminate all left recursion, by first converting indirect left recursion to direct left recursion on the highest numbered nonterminal in a cycle. 
:'''Inputs''' ''A grammar: a set of nonterminals <math>A_1,\ldots,A_n</math> and their productions''
:'''Output''' ''A modified grammar generating the same language but without left recursion''
:# ''For each nonterminal <math>A_i</math>:''
:## ''Repeat until an iteration leaves the grammar unchanged:''
:### ''For each rule <math>A_i\rightarrow\alpha_i</math>, <math>\alpha_i</math> being a sequence of terminals and nonterminals:''
:#### ''If <math>\alpha_i</math> begins with a nonterminal <math>A_j</math> and <math>j<i</math>:''
:##### ''Let <math>\beta_i</math> be <math>\alpha_i</math> without its leading <math>A_j</math>.''
:##### ''Remove the rule <math>A_i\rightarrow\alpha_i</math>.''
:##### ''For each rule <math>A_j\rightarrow\alpha_j</math>:''
:###### ''Add the rule <math>A_i\rightarrow\alpha_j\beta_i</math>.''
:## ''Remove direct left recursion for <math>A_i</math> as described above.''
Step 1.1.1 amounts to expanding the initial nonterminal <math>A_j</math> in the right hand side of some rule <math>A_i \to A_j \beta</math>, but only if <math>j<i</math>. If <math>A_i \to A_j \beta</math> was one step in a cycle of productions giving rise to a left recursion, then this has shortened that cycle by one step, but often at the price of increasing the number of rules.

The algorithm may be viewed as establishing a [[topological ordering]] on nonterminals: afterwards there can only be a rule <math>A_i \to A_j \beta</math> if <math>j>i</math>.
Note that this algorithm is highly sensitive to the nonterminal ordering; optimizations often focus on choosing this ordering well.{{Clarify|date=March 2022}}