Course contentsShow
← Computer Science
Lesson 1954 of 2,87244. Lexical Analysis and ParsingFree lesson

Eliminating Left Recursion

Transforming left-recursive grammar rules into equivalent right-recursive or iterative forms for top-down parsing.

Eliminating Left Recursion

What You'll Learn

You'll learn how to transform left-recursive grammar rules into equivalent forms that work with top-down parsers.

The Problem Recap

In the previous lesson, you saw that left recursion causes infinite loops in recursive descent parsers. A rule like A → A α | β makes the parser call itself immediately, never consuming input.

The Transformation

The fix is to rewrite left-recursive rules using right recursion or iteration.

For a simple left-recursive rule:

A → A α | β

Transform it into two rules:

A  → β A'
A' → α A' | ε

Here, A' is a new non-terminal (read as "A-prime"). Instead of recursing before processing α, we now process β first, then let A' handle zero or more repetitions of α after.

How It Works

Think of it like building a train: left recursion tries to attach cars before the engine (impossible in a single pass), but right recursion attaches the engine first, then adds cars after one by one.

Example:

expr → expr + term | term

Becomes:

expr  → term expr'
expr' → + term expr' | ε

Now the parser reads term first, then repeatedly checks for + term sequences.

Why This Works

The transformed grammar generates the same language but parses left-to-right without immediate self-recursion. The parser consumes input before making recursive calls, preventing infinite loops.

Key Takeaway:
Eliminating left recursion transforms grammar rules so the parser processes input before recursing, enabling top-down parsing while preserving the language accepted.