Left recursion

Direct left recursion occurs when the definition can be satisfied with only one substitution. It requires a rule of the form

${\displaystyle A\to A\alpha }$

where ${\displaystyle \alpha }$ is a sequence of nonterminals and terminals . For example, the rule

${\displaystyle {\mathit {Expression}}\to {\mathit {Expression}}+{\mathit {Term}}}$

is directly left-recursive. A left-to-right recursive descent parser for this rule might look like

void Expression() {
  Expression();
  match('+');
  Term();
}

and such code would fall into infinite recursion when executed.

Indirect left recursion occurs when the definition of left recursion is satisfied via several substitutions. It entails a set of rules following the pattern

${\displaystyle A_{0}\to \beta _{0}A_{1}\alpha _{0}}$

${\displaystyle A_{1}\to \beta _{1}A_{2}\alpha _{1}}$

${\displaystyle \cdots }$

${\displaystyle A_{n}\to \beta _{n}A_{0}\alpha _{n}}$

where ${\displaystyle \beta _{0},\beta _{1},\ldots ,\beta _{n}}$ are sequences that can each yield the empty string, while ${\displaystyle \alpha _{0},\alpha _{1},\ldots ,\alpha _{n}}$ may be any sequences of terminal and nonterminal symbols at all. Note that these sequences may be empty. The derivation

${\displaystyle A_{0}\Rightarrow \beta _{0}A_{1}\alpha _{0}\Rightarrow ^{+}A_{1}\alpha _{0}\Rightarrow \beta _{1}A_{2}\alpha _{1}\alpha _{0}\Rightarrow ^{+}\cdots \Rightarrow ^{+}A_{0}\alpha _{n}\dots \alpha _{1}\alpha _{0}}$

then gives ${\displaystyle A_{0}}$ as leftmost in its final sentential form.

The general algorithm to remove direct left recursion follows. Several improvements to this method have been made.[2] For a left-recursive nonterminal ${\displaystyle A}$, discard any rules of the form ${\displaystyle A\rightarrow A}$ and consider those that remain:

${\displaystyle A\rightarrow A\alpha _{1}\mid \ldots \mid A\alpha _{n}\mid \beta _{1}\mid \ldots \mid \beta _{m}}$

where:

• each ${\displaystyle \alpha }$ is a nonempty sequence of nonterminals and terminals, and
• each ${\displaystyle \beta }$ is a sequence of nonterminals and terminals that does not start with ${\displaystyle A}$.

Replace these with two sets of productions, one set for ${\displaystyle A}$:

${\displaystyle A\rightarrow \beta _{1}A^{\prime }\mid \ldots \mid \beta _{m}A^{\prime }}$

and another set for the fresh nonterminal ${\displaystyle A'}$ (often called the "tail" or the "rest"):

${\displaystyle A^{\prime }\rightarrow \alpha _{1}A^{\prime }\mid \ldots \mid \alpha _{n}A^{\prime }\mid \epsilon }$

Repeat this process until no direct left recursion remains.

As an example, consider the rule set

${\displaystyle {\mathit {Expression}}\rightarrow {\mathit {Expression}}+{\mathit {Expression}}\mid {\mathit {Integer}}\mid {\mathit {String}}}$

This could be rewritten to avoid left recursion as

${\displaystyle {\mathit {Expression}}\rightarrow {\mathit {Integer}}\,{\mathit {Expression}}'\mid {\mathit {String}}\,{\mathit {Expression}}'}$

${\displaystyle {\mathit {Expression}}'\rightarrow {}+{\mathit {Expression}}\,{\mathit {Expression}}'\mid \epsilon }$

By establishing a topological ordering on nonterminals, the above process can be extended to also eliminate indirect left recursion :

Inputs A grammar: a set of nonterminals ${\displaystyle A_{1},\ldots ,A_{n}}$ and their productions

Output A modified grammar generating the same language but without left recursion

1. For each nonterminal ${\displaystyle A_{i}}$:
   1. Repeat until an iteration leaves the grammar unchanged:
      1. For each rule ${\displaystyle A_{i}\rightarrow \alpha _{i}}$, ${\displaystyle \alpha _{i}}$ being a sequence of terminals and nonterminals:
         1. If ${\displaystyle \alpha _{i}}$ begins with a nonterminal ${\displaystyle A_{j}}$ and ${\displaystyle j<i}$:
            1. Let ${\displaystyle \beta _{i}}$ be ${\displaystyle \alpha _{i}}$ without its leading ${\displaystyle A_{j}}$.
            2. Remove the rule ${\displaystyle A_{i}\rightarrow \alpha _{i}}$.
            3. For each rule ${\displaystyle A_{j}\rightarrow \alpha _{j}}$:
               1. Add the rule ${\displaystyle A_{i}\rightarrow \alpha _{j}\beta _{i}}$.
   2. Remove direct left recursion for ${\displaystyle A_{i}}$ as described above.

Note that this algorithm is highly sensitive to the nonterminal ordering; optimizations often focus on choosing this ordering well.