This articlemay be too technical for most readers to understand. Pleasehelp improve it tomake it understandable to non-experts, without removing the technical details.(November 2015) (Learn how and when to remove this message)

In theformal language theory ofcomputer science,left recursion is a special case ofrecursion where a string is recognized as part of a language by the fact that it decomposes into a string from that same language (on the left) and a suffix (on the right). For instance,${\displaystyle 1+2+3}$ can be recognized as a sum because it can be broken into${\displaystyle 1+2}$, also a sum, and${\displaystyle +3}$, a suitable suffix.

In terms ofcontext-free grammar, anonterminal is left-recursive if the leftmost symbol in one of its productions is itself (in the case of direct left recursion) or can be made itself by some sequence of substitutions (in the case of indirect left recursion).

A grammar is left-recursive if and only if there exists a nonterminal symbol${\displaystyle A}$ that can derive to asentential form with itself as the leftmost symbol.^[1] Symbolically,

${\displaystyle A{\Rightarrow }^{+}A\alpha }$,

where${\displaystyle {\Rightarrow }^{+}}$ indicates the operation of making one or more substitutions, and${\displaystyle \alpha }$ is any sequence of terminal and nonterminal symbols.

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{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}\to \mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}+\mathit{T}\mathit{e}\mathit{r}\mathit{m}}$

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

voidExpression(){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,\dots ,{\beta }_n}$ are sequences that can each yield theempty string, while${\displaystyle {\alpha }_0,{\alpha }_1,\dots ,{\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.

Left recursion is commonly used as an idiom for making operationsleft-associative: that an expressiona+b-c-d+e is evaluated as(((a+b)-c)-d)+e. In this case, that evaluation order could be achieved as a matter of syntax via the three grammatical rules

${\displaystyle \mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}\to \mathit{T}\mathit{e}\mathit{r}\mathit{m}}$

${\displaystyle \mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}\to \mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}+\mathit{T}\mathit{e}\mathit{r}\mathit{m}}$

${\displaystyle \mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}\to \mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}-\mathit{T}\mathit{e}\mathit{r}\mathit{m}}$

These only allow parsing the${\displaystyle \mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}}$a+b-c-d+e as consisting of the${\displaystyle \mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}}$a+b-c-d and${\displaystyle \mathit{T}\mathit{e}\mathit{r}\mathit{m}}$e, wherea+b-c-d in turn consists of the${\displaystyle \mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}}$a+b-c and${\displaystyle \mathit{T}\mathit{e}\mathit{r}\mathit{m}}$d, whilea+b-c consists of the${\displaystyle \mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}}$a+b and${\displaystyle \mathit{T}\mathit{e}\mathit{r}\mathit{m}}$c, etc.

Left recursion often poses problems for parsers, either because it leads them into infinite recursion (as in the case of mosttop-down parsers) or because they expect rules in a normal form that forbids it (as in the case of manybottom-up parsers^{[clarification needed]}). Therefore, a grammar is often preprocessed to eliminate the left recursion.

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\to A}$ and consider those that remain:

${\displaystyle A\to A{\alpha }_1\mid \dots \mid A{\alpha }_n\mid {\beta }_1\mid \dots \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\to {\beta }_1{A}^{\mathrm{\prime }}\mid \dots \mid {\beta }_m{A}^{\mathrm{\prime }}}$

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

${\displaystyle A^{\mathrm{\prime }}\to {\alpha }_1{A}^{\mathrm{\prime }}\mid \dots \mid {\alpha }_n{A}^{\mathrm{\prime }}\mid ϵ}$

Repeat this process until no direct left recursion remains.

As an example, consider the rule set

${\displaystyle \mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}\to \mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}+\mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}\mid \mathit{I}\mathit{n}\mathit{t}\mathit{e}\mathit{g}\mathit{e}\mathit{r}\mid \mathit{S}\mathit{t}\mathit{r}\mathit{i}\mathit{n}\mathit{g}}$

This could be rewritten to avoid left recursion as

${\displaystyle \mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}\to \mathit{I}\mathit{n}\mathit{t}\mathit{e}\mathit{g}\mathit{e}\mathit{r}{\mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}}^{\prime }\mid \mathit{S}\mathit{t}\mathit{r}\mathit{i}\mathit{n}\mathit{g}{\mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}}^{\prime }}$

${\displaystyle {\mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}}^{\prime }\to +\mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}{\mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}}^{\prime }\mid ϵ}$

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.

InputsA grammar: a set of nonterminals${\displaystyle A_1,\dots ,A_n}$ and their productions

OutputA 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\to {\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:
            1. Let${\displaystyle {\beta }_i}$ be${\displaystyle {\alpha }_i}$ without its leading${\displaystyle A_j}$.
            2. Remove the rule${\displaystyle A_i\to {\alpha }_i}$.
            3. For each rule${\displaystyle A_j\to {\alpha }_j}$:
               1. Add the rule${\displaystyle A_i\to {\alpha }_j{\beta }_i}$.
   2. Remove direct left recursion for${\displaystyle A_i}$ as described above.

Step 1.1.1 amounts to expanding the initial nonterminal${\displaystyle A_j}$ in the right hand side of some rule${\displaystyle A_i\to A_j\beta }$, but only if. If${\displaystyle A_i\to A_j\beta }$ 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 atopological ordering on nonterminals: afterwards there can only be a rule${\displaystyle A_i\to A_j\beta }$ if${\displaystyle j>i}$.Note that this algorithm is highly sensitive to the nonterminal ordering; optimizations often focus on choosing this ordering well.^{[clarification needed]}

Although the above transformations preserve the language generated by a grammar, they may change theparse trees thatwitness strings' recognition. With suitable bookkeeping,tree rewriting can recover the originals, but if this step is omitted, the differences may change the semantics of a parse.

Associativity is particularly vulnerable; left-associative operators typically appear in right-associative-like arrangements under the new grammar. For example, starting with this grammar:

${\displaystyle \mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}\to \mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}-\mathit{T}\mathit{e}\mathit{r}\mathit{m}\mid \mathit{T}\mathit{e}\mathit{r}\mathit{m}}$

${\displaystyle \mathit{T}\mathit{e}\mathit{r}\mathit{m}\to \mathit{T}\mathit{e}\mathit{r}\mathit{m}\ast \mathit{F}\mathit{a}\mathit{c}\mathit{t}\mathit{o}\mathit{r}\mid \mathit{F}\mathit{a}\mathit{c}\mathit{t}\mathit{o}\mathit{r}}$

${\displaystyle \mathit{F}\mathit{a}\mathit{c}\mathit{t}\mathit{o}\mathit{r}\to (\mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n})\mid \mathit{I}\mathit{n}\mathit{t}\mathit{e}\mathit{g}\mathit{e}\mathit{r}}$

the standard transformations to remove left recursion yield the following:

${\displaystyle \mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}\to \mathit{T}\mathit{e}\mathit{r}\mathit{m}{\mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}}^{\prime }}$

${\displaystyle {\mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}}^{\prime }\to -\mathit{T}\mathit{e}\mathit{r}\mathit{m}{\mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n}}^{\prime }\mid ϵ}$

${\displaystyle \mathit{T}\mathit{e}\mathit{r}\mathit{m}\to \mathit{F}\mathit{a}\mathit{c}\mathit{t}\mathit{o}\mathit{r}{\mathit{T}\mathit{e}\mathit{r}\mathit{m}}^{\prime }}$

${\displaystyle {\mathit{T}\mathit{e}\mathit{r}\mathit{m}}^{\prime }\to \ast \mathit{F}\mathit{a}\mathit{c}\mathit{t}\mathit{o}\mathit{r}{\mathit{T}\mathit{e}\mathit{r}\mathit{m}}^{\prime }\mid ϵ}$

${\displaystyle \mathit{F}\mathit{a}\mathit{c}\mathit{t}\mathit{o}\mathit{r}\to (\mathit{E}\mathit{x}\mathit{p}\mathit{r}\mathit{e}\mathit{s}\mathit{s}\mathit{i}\mathit{o}\mathit{n})\mid \mathit{I}\mathit{n}\mathit{t}\mathit{e}\mathit{g}\mathit{e}\mathit{r}}$

Parsing the string "1 - 2 - 3" with the first grammar in an LALR parser (which can handle left-recursive grammars) would have resulted in the parse tree:

This parse tree groups the terms on the left, giving the correct semantics(1 - 2) - 3.

Parsing with the second grammar gives

which, properly interpreted, signifies1 + (-2 + (-3)), also correct, but less faithful to the input and much harder to implement for some operators. Notice how terms to the right appear deeper in the tree, much as a right-recursive grammar would arrange them for1 - (2 - 3).

Aformal grammar that contains left recursion cannot beparsed by aLL(k)-parser or other naiverecursive descent parser unless it is converted to aweakly equivalent right-recursive form. In contrast, left recursion is preferred forLALR parsers because it results in lower stack usage thanright recursion. However, more sophisticated top-down parsers can implement generalcontext-free grammars by use of curtailment. In 2006, Frost and Hafiz described an algorithm which accommodatesambiguous grammars with direct left-recursiveproduction rules.^[3] That algorithm was extended to a completeparsing algorithm to accommodate indirect as well as direct left recursion inpolynomial time, and to generate compact polynomial-size representations of the potentially exponential number of parse trees for highly ambiguous grammars by Frost, Hafiz and Callaghan in 2007.^[4] The authors then implemented the algorithm as a set ofparser combinators written in theHaskell programming language.^[5]

• Tail recursion

• Practical Considerations for LALR(1) Grammars

• Control flow
• Formal languages
• Parsing
• Recursion

• Webarchive template wayback links
• Articles with short description
• Short description matches Wikidata
• Wikipedia articles that are too technical from November 2015
• All articles that are too technical
• Wikipedia articles needing clarification from July 2023
• Wikipedia articles needing clarification from March 2022