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

Left Recursion Problem

Why left-recursive grammars cause infinite loops in recursive descent parsers and how to detect them.

Left Recursion Problem

You'll learn why some grammar rules cause recursive descent parsers to spin forever, and how to spot them before they break your parser.

The Core Issue

Remember recursive descent parsing? Each grammar rule becomes a function that calls other functions. Left recursion happens when a grammar rule's first symbol refers back to itself—directly or indirectly. This creates an infinite loop because the parser immediately calls itself again without consuming any input tokens.

Why It Causes Infinite Loops

Consider this grammar rule:

Expr → Expr + Term | Term

When the recursive descent function for Expr starts, it sees the first alternative begins with Expr, so it immediately calls itself. That recursive call also sees Expr first, so it calls itself again. This continues forever—the parser never reads a single token or makes any progress.

Think of it like looking up a word in the dictionary, only to find: "See: this word." You're stuck in a circle.

Detecting Left Recursion

Direct left recursion is easy to spot: a rule like A → A α | β where the rule name A appears as its own first symbol.

Indirect left recursion is trickier:

A → B α
B → A β

Here A calls B, which immediately calls A back—still an infinite loop, just hidden across two rules.

Detection Strategy

Scan each grammar rule's alternatives. If any alternative starts with the rule's own non-terminal (directly or through a chain of nullable symbols), you've found left recursion.

Key Takeaway: Left-recursive grammars cause recursive descent parsers to loop infinitely because the parser calls itself without consuming input; detect left recursion by checking if any rule can derive itself as its first symbol.