Editing Left recursion (section)

== Definition ==
A grammar is left-recursive if and only if there exists a nonterminal symbol <math>A</math> that can derive to a [[Formal grammar#The semantics of grammars|sentential form]] with itself as the leftmost symbol.<ref>{{Webarchive|url=https://web.archive.org/web/20071127105226id_/http://www.cs.nuim.ie/~jpower/Courses/parsing/parsing.pdf#page=20|title=Notes on Formal Language Theory and Parsing}}. James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.[[JPR02]]</ref> Symbolically,
:<math> A \Rightarrow^+ A\alpha</math>,
where <math>\Rightarrow^+</math> indicates the operation of making one or more substitutions, and <math>\alpha</math> 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
:<math>A \to A\alpha</math>
where <math>\alpha</math> is a sequence of nonterminals and terminals . For example, the rule
:<math>\mathit{Expression} \to \mathit{Expression} + \mathit{Term}</math>
is directly left-recursive. A left-to-right [[recursive descent parser]] for this rule might look like
<syntaxhighlight lang="cpp">
void Expression() {
  Expression();
  match('+');
  Term();
}
</syntaxhighlight>
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
:<math>A_0 \to \beta_0A_1\alpha_0</math>
:<math>A_1 \to \beta_1A_2\alpha_1</math>
:<math>\cdots</math>
:<math>A_n \to \beta_nA_0\alpha_n</math>
where <math>\beta_0, \beta_1, \ldots, \beta_n</math> are sequences that can each yield the [[empty string]], while <math>\alpha_0, \alpha_1, \ldots, \alpha_n</math> may be any sequences of terminal and nonterminal symbols at all.  Note that these sequences may be empty.  The derivation
:<math>A_0\Rightarrow\beta_0A_1\alpha_0\Rightarrow^+ A_1\alpha_0\Rightarrow\beta_1A_2\alpha_1\alpha_0\Rightarrow^+\cdots\Rightarrow^+ A_0\alpha_n\dots\alpha_1\alpha_0</math>
then gives <math>A_0</math> as leftmost in its final sentential form.