Editing Left recursion (section)

== Removing left recursion ==
Left recursion often poses problems for parsers, either because it leads them into infinite recursion (as in the case of most [[top-down parsing|top-down parsers]]) or because they expect rules in a normal form that forbids it (as in the case of many [[bottom-up parsing|bottom-up parsers]]{{clarify|reason=Which bottom-up parser needs a normal form and/or can not handle left recursion?|date=July 2023}}).  Therefore, a grammar is often preprocessed to eliminate the left recursion.

=== Removing direct left recursion ===
The general algorithm to remove direct left recursion follows. Several improvements to this method have been made.<ref name="Moore2000">{{cite journal|last=Moore|first=Robert C.|title=Removing Left Recursion from Context-Free Grammars|journal=6th Applied Natural Language Processing Conference|date=May 2000|pages=249–255|url=https://www.microsoft.com/en-us/research/wp-content/uploads/2000/04/naacl2k-proc-rev.pdf}}</ref>
For a left-recursive nonterminal <math>A</math>, discard any rules of the form <math>A\rightarrow A</math> and consider those that remain:
:<math>A \rightarrow A\alpha_1 \mid \ldots \mid A\alpha_n \mid \beta_1 \mid \ldots \mid \beta_m </math>
where:
* each <math>\alpha</math> is a nonempty sequence of nonterminals and terminals, and
* each <math>\beta</math> is a sequence of nonterminals and terminals that does not start with <math>A</math>.
Replace these with two sets of productions, one set for <math>A</math>:
:<math>A \rightarrow \beta_1A^\prime \mid \ldots \mid \beta_mA^\prime</math>
and another set for the fresh nonterminal <math>A'</math> (often called the "tail" or the "rest"):
:<math>A^\prime \rightarrow \alpha_1A^\prime \mid \ldots \mid \alpha_nA^\prime \mid \epsilon</math>
Repeat this process until no direct left recursion remains.

As an example, consider the rule set
:<math>\mathit{Expression} \rightarrow \mathit{Expression}+\mathit{Expression} \mid \mathit{Integer} \mid \mathit{String}</math>
This could be rewritten to avoid left recursion as
:<math>\mathit{Expression} \rightarrow \mathit{Integer}\,\mathit{Expression}' \mid \mathit{String}\,\mathit{Expression}'</math>
:<math>\mathit{Expression}' \rightarrow {}+\mathit{Expression} \,\mathit{Expression}'\mid \epsilon</math>

=== 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}}