In the formal language theory of computer science, left recursion is a special case of recursion 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, 1 + 2 + 3 {\displaystyle 1+2+3} can be recognized as a sum because it can be broken into 1 + 2 {\displaystyle 1+2} , also a sum, and
+ 3 {\displaystyle {}+3} , a suitable suffix. In terms of context-free grammar, a nonterminal 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).
Definition A grammar is left-recursive if and only if there exists a nonterminal symbol A {\displaystyle A} that can derive to a sentential form with itself as the leftmost symbol. Symbolically,
A ⇒ + A α {\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 Direct left recursion occurs when the definition can be satisfied with only one substitution. It requires a rule of the form
A → A α {\displaystyle A\to A\alpha }
where α {\displaystyle \alpha } is a sequence of nonterminals and terminals . For example, the rule
E x p r e s s i o n → E x p r e s s i o n + T e r m {\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
and such code would fall into infinite recursion when executed.
Indirect left recursion Indirect left recursion occurs when the definition of left recursion is satisfied via several substitutions. It entails a set of rules following the pattern
A 0 → β 0 A 1 α 0 {\displaystyle A_{0}\to \beta _{0}A_{1}\alpha _{0}}
A 1 → β 1 A 2 α 1 {\displaystyle A_{1}\to \beta _{1}A_{2}\alpha _{1}}
⋯ {\displaystyle \cdots }
A n → β n A 0 α n {\displaystyle A_{n}\to \beta _{n}A_{0}\alpha _{n}}
where β 0 , β 1 , … , β n {\displaystyle \beta _{0},\beta _{1},\ldots ,\beta _{n}} are sequences that can each yield the empty string, while α 0 , α 1 , … , α n {\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
A 0 ⇒ β 0 A 1 α 0 ⇒ + A 1 α 0 ⇒ β 1 A 2 α 1 α 0 ⇒ + ⋯ ⇒ + A 0 α n … α 1 α 0 {\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}}
… excerpt ends here. Continue reading the full article.
