Coursify

Left Recursion in Context-Free Grammars and Its Elimination (LL Parsing)

Left Recursion in Context-Free Grammars and Its Elimination (LL Parsing)

Verified Sources
Nov 4, 2026

In context-free grammars, left recursion occurs when a nonterminal AA can derive a string that begins with AA itself—i.e., there is a derivation of the form A⇒+AαA \Rightarrow^+ A\alpha for some α\alpha. This prevents a top-down predictive parser (e.g., an LL(1) parser) from deciding which production to use, because the parser can keep expanding AA without consuming any input.

For direct left recursion, a production has the specific form: A→Aα∣βA \rightarrow A\alpha \mid \beta where β\beta does not begin with AA. The classic transformation rewrites the grammar into an equivalent one that removes left recursion by introducing a new nonterminal A′A':

A→βA′A′→αA′∣ϵA \rightarrow \beta A' \\ A' \rightarrow \alpha A' \mid \epsilon

This ensures recursive repetition happens after the parser consumes a β\beta-prefix from the input, enabling predictive parsing.

We will apply this to the grammar:

E→E+T∣TT→T∗F∣FF→(E)∣idE \rightarrow E+T \mid T\\ T \rightarrow T*F \mid F\\ F \rightarrow (E) \mid id

Key terms: left recursion , direct left recursion , LL(1) parser , [ϵ\epsilon-production]{def="A production that derives the empty string"}.

Footnotes

  1. (Example authoritative source on left recursion elimination / parsing) Wikipedia: "Left recursion" and related parsing/LL transformation notes—https://en.wikipedia.org/wiki/Left_recursion - Defines left recursion and standard transformation patterns used in top-down parsing. ↩ ↩2

Eliminating Left Recursion (Direct Left Recursion) — Theory + Example

Step-by-step elimination strategy

We handle each nonterminal with direct left-recursive alternatives separately:

  • For A→Aα∣βA \rightarrow A\alpha \mid \beta, rewrite as:
    • A→βA′A \rightarrow \beta A'
    • A′→αA′∣ϵA' \rightarrow \alpha A' \mid \epsilon

In our grammar, the problematic parts are:

  • E→E+T∣TE \rightarrow E+T \mid T (direct left recursion in EE)
  • T→T∗F∣FT \rightarrow T*F \mid F (direct left recursion in TT)
  • F→(E)∣idF \rightarrow (E) \mid id (no left recursion)

Key terms: direct recursion elimination , auxiliary nonterminal , lookahead.

Footnotes

  1. (Example authoritative source on left recursion elimination / parsing) Wikipedia: "Left recursion" and related parsing/LL transformation notes—https://en.wikipedia.org/wiki/Left_recursion - Defines left recursion and standard transformation patterns used in top-down parsing. ↩

Eliminate left recursion from the given grammar

  1. 1
    Step 1

    Here, EE has the form E→E+T∣TE\rightarrow E+T\mid T and TT has T→T∗F∣FT\rightarrow T*F\mid F. The nonterminal FF has no left recursion since its alternatives begin with (E)(E) or idid.

  2. 2
    Step 2

    Match E→E+T∣TE\rightarrow E+T\mid T to A→Aα∣βA\rightarrow A\alpha\mid\beta with A=EA=E, α=+T\alpha=+T, and β=T\beta=T. Introduce E′E' to get: E→TE′E\rightarrow T E' and E′→+TE′∣ϵE'\rightarrow +T E'\mid\epsilon.

  3. 3
    Step 3

    Match T→T∗F∣FT\rightarrow T*F\mid F with A=TA=T, α=∗F\alpha=*F, and β=F\beta=F. Introduce T′T' to obtain: T→FT′T\rightarrow F T' and T′→∗FT′∣ϵT'\rightarrow *F T'\mid\epsilon.

  4. 4
    Step 4

    Since F→(E)∣idF\rightarrow (E)\mid id has no left-recursive alternative, we retain it as-is.

  5. 5
    Step 5

    Combine the rewritten rules to form the new grammar without left recursion.

Resulting grammar (left-recursion free)

The eliminated grammar is:

E→TE′E′→+TE′∣ϵT→FT′T′→∗FT′∣ϵF→(E)∣idE \rightarrow T E' \\ E' \rightarrow +T E' \mid \epsilon \\ T \rightarrow F T' \\ T' \rightarrow *F T' \mid \epsilon \\ F \rightarrow (E) \mid id

This grammar preserves the language of the original grammar while enabling LL-style top-down parsing because recursion now appears in E′E' and T′T' after consuming the initial TT or FF token sequence.

Footnotes

  1. (Example authoritative source on left recursion elimination / parsing) Wikipedia: "Left recursion" and related parsing/LL transformation notes—https://en.wikipedia.org/wiki/Left_recursion - Defines left recursion and standard transformation patterns used in top-down parsing. ↩

What changed during left-recursion elimination?

Direct recursion moved from E and T into E' and T' with ε-termination.

Common checks and pitfalls

Pro Tip

When you see A→Aα∣βA \rightarrow A\alpha \mid \beta in a grammar you plan to parse with LL(1), rewrite it using the standard A′A' + ϵ\epsilon pattern. Then re-check FIRST/FOLLOW to ensure LL(1) predictability.

Footnotes

  1. (Example authoritative source on left recursion elimination / parsing) Wikipedia: "Left recursion" and related parsing/LL transformation notes—https://en.wikipedia.org/wiki/Left_recursion - Defines left recursion and standard transformation patterns used in top-down parsing. ↩

Common mistake

A frequent error is to drop the ϵ\epsilon alternative in A′→αA′∣ϵA' \rightarrow \alpha A' \mid \epsilon. Without ϵ\epsilon, derivations cannot stop, and the grammar may generate only infinitely long recursive patterns (or become incomplete).

Footnotes

  1. (Example authoritative source on left recursion elimination / parsing) Wikipedia: "Left recursion" and related parsing/LL transformation notes—https://en.wikipedia.org/wiki/Left_recursion - Defines left recursion and standard transformation patterns used in top-down parsing. ↩

Conceptual workflow for handling left recursion

Detect

1

Look for productions where a nonterminal can derive a string starting with itself: A⇒+AαA \Rightarrow^+ A\alpha."

Classify

2

Identify direct left recursion (A→Aα∣βA \rightarrow A\alpha \mid \beta)."

Transform

3

Rewrite using A→βA′A \rightarrow \beta A' and A′→αA′∣ϵA' \rightarrow \alpha A' \mid \epsilon."

Validate for LL(1)

4

Check FIRST/FOLLOW conflicts for predictive parsing."

Knowledge Check

Question 1 of 4
Q1Single choice

Which of the following best describes left recursion?

Explore Related Topics

1

Correct Answer: Eliminating Immediate Left Recursion \(A \rightarrow A\alpha / \beta\)

2

Course Section: Left Factoring, Eliminating Left Recursion, and Top-Down Parsing Suitability for

3

FIRST, FOLLOW, and LL(1) Parsing Table for the Given Expression Grammar

Browse all research articles