Editing Left recursion (section)

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