Course contentsShow
← Computer Science
Lesson 1841 of 2,87241. Context-Free LanguagesFree lesson

Eliminating Left Recursion

Algorithmic method to transform left-recursive grammars into equivalent grammars without left recursion.

Eliminating Left Recursion

You'll learn: How to systematically transform a left-recursive grammar into an equivalent one that avoids left recursion—essential for top-down parsers.

Why This Matters

Recall from the previous lesson that left recursion causes top-down parsers to loop infinitely. A production like A → A α | β makes the parser immediately call itself on A without consuming any input, creating an endless cycle. We need a mechanical procedure to fix this.

The Core Algorithm

The transformation works by replacing left recursion with right recursion and introducing a new helper nonterminal.

Immediate Left Recursion

For a rule of the form:

A → A α₁ | A α₂ | ... | A αₙ | β₁ | β₂ | ... | βₘ

Where each β does not start with A, we replace it with:

A  → β₁ A' | β₂ A' | ... | βₘ A'
A' → α₁ A' | α₂ A' | ... | αₙ A' | ε

Example

Original (left-recursive):

E → E + T | T

Transformed:

E  → T E'
E' → + T E' | ε

Now E starts with T (consuming input immediately), and E' handles the repeating + T parts using right recursion.

Think of It Like...

Instead of saying "a number is itself plus more stuff" (which creates a circular dependency), we say "a number is a base value followed by zero-or-more additions." The new nonterminal A' captures "what comes after" the base case.

Key Takeaway: Eliminating left recursion systematically rewrites grammar rules to replace left-recursive patterns with right recursion and a helper nonterminal, making the grammar parsable by top-down methods without changing the language it generates.