Left Recursion

Understand what left recursion is, why it causes top-down parsers to loop forever, and how to eliminate it — both direct and indirect — using a systematic algorithm.

What is Left Recursion?

A grammar rule is left-recursive if a non-terminal can derive a string that begins with itself.

Direct left recursion:

Example

A → A α (A appears at the leftmost position of its own production)

Example:

Example

E → E + T | T

Here, E → E + T is directly left-recursive because E is the leftmost symbol on the right side.

Indirect left recursion:

Example

A → B α

B → A β

A does not directly start with A, but:

A expands to B...
B expands back to A...

So we have a cycle: A → B → A.

Intuitive Understanding

Think of left recursion like this: before a non-terminal A can produce anything, it first needs to process another copy of A. But that copy of A again needs to process a copy of A, and so on — infinitely.

Example

E → E + T

→ E + T + T

→ E + T + T + T

→ ... (never terminates)

This is exactly what happens when a top-down parser (like recursive descent) tries to handle a left-recursive grammar — it enters an infinite loop.

Why is Left Recursion a Problem?

Bottom-up parsers (LR parsers) handle left recursion fine. They work from the input upward, so they never need to predict what comes first — they just keep reducing.

Top-down parsers (LL parsers, recursive descent) read the input left to right and try to expand rules from the start symbol downward. When they see a left-recursive rule, they get stuck in an infinite loop.

Tracing a Recursive Descent Parser on E → E + T | T:

Example

parseE():

call parseE() ← immediately calls itself

call parseE() ← again...

... ← infinite recursion → stack overflow!

The parser never even looks at the input — it just keeps calling itself forever.

The Rule

Top-down parsers cannot handle left-recursive grammars. Left recursion must be eliminated before using LL or recursive descent parsing.

Eliminating Direct Left Recursion

Direct left recursion is removed by converting it into right recursion using a helper non-terminal.

The General Pattern

Left-recursive grammar:

Example

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

where:

A α are the left-recursive rules (A is the first symbol)
β are the non-left-recursive rules (do not start with A)

Transformed grammar (no left recursion):

Example

A → β₁ A' | β₂ A' | ... | βₘ A'

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

The new non-terminal A' (A-prime) captures the repeated trailing part. It recurses on the right, which is fine for top-down parsers.

Example 1 — Simple Expression Grammar

Original (left-recursive):

Example

E → E + T | T

Identify:

Left-recursive rule: E + T (α = + T)
Non-left-recursive rule: T (β = T)

Transformed:

Example

E → T E'

E' → + T E' | ε

Verification — derive "T + T + T":

Example

→ T E'

→ T + T E'

→ T + T + T E'

→ T + T + T ε

= T + T + T ✓

Same language — no left recursion.

Example 2 — Full Arithmetic Grammar

Original:

Example

E → E + T | E - T | T

T → T * F | T / F | F

F → ( E ) | id

Transformed:

Example

E → T E'

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

T → F T'

T' → * F T' | / F T' | ε

F → ( E ) | id

This is the classic LL(1)-ready form of arithmetic expressions.

Eliminating Indirect Left Recursion

Indirect left recursion is trickier. It requires a systematic algorithm that substitutes rules to reveal hidden direct left recursion, then eliminates it.

The Algorithm

Given: A grammar with non-terminals A₁, A₂, …, Aₙ in some fixed order.

Example

for i = 1 to n:

for j = 1 to i-1:

replace each production Aᵢ → Aⱼ γ

with: Aᵢ → δ₁ γ | δ₂ γ | ...

where Aⱼ → δ₁ | δ₂ | ... are the current productions for Aⱼ

eliminate any direct left recursion in Aᵢ's productions

The outer loop goes through each non-terminal in order. The inner loop substitutes earlier non-terminals to expose any hidden recursion.

Example — Indirect Left Recursion

Original grammar:

Example

S → A a | b

A → S b | d

Order: S = A₁, A = A₂.

Step 1 — Process A₁ = S:

No Aⱼ with j < 1, so skip the inner loop. Check for direct left recursion in S: none.

Example

S → A a | b (unchanged)

Step 2 — Process A₂ = A:

Inner loop: j = 1, substitute A₁ = S. A has production A → S b. Replace S with its productions:

Example

A → S b → becomes → (A a) b | b b

= A a b | b b

So A's productions are now:

Example

A → A a b | b b | d

Now A has direct left recursion! Eliminate it:

Identify: Left-recursive: A a b (α = a b), Non-left-recursive: b b and d (β)

Example

A → b b A' | d A'

A' → a b A' | ε

Final grammar (no left recursion):

Example

S → A a | b

A → b b A' | d A'

A' → a b A' | ε

Key Point

After eliminating indirect left recursion, the grammar generates the same language, but can now be parsed by a top-down parser without looping.

Left Recursion vs. Right Recursion

After eliminating left recursion, the grammar becomes right-recursive. It is worth understanding what this means for associativity.

Original Left-Recursive Grammar — Left-Associative

Example

E → E + T | T

Parse tree for a + b + c:

Result: (a + b) + c — left-associative. The leftmost E subtree groups first, so addition folds from the left.

Transformed Right-Recursive Grammar

Example

E → T E'

E' → + T E' | ε

Parse tree for a + b + c:

When you evaluate this tree the standard way (left to right, collecting operators), you still get (a + b) + c — the same left-associative result.

The tree shape changes, but the semantic result is the same. The elimination is safe.

What is Left Recursion?

A grammar rule is left-recursive if a non-terminal can derive a string that begins with itself.

Direct left recursion:

Example

A → A α (A appears at the leftmost position of its own production)

Example:

Example

E → E + T | T

Here, E → E + T is directly left-recursive because E is the leftmost symbol on the right side.

Indirect left recursion:

Example

A → B α

B → A β

A does not directly start with A, but:

A expands to B...
B expands back to A...

So we have a cycle: A → B → A.

Intuitive Understanding

Example

E → E + T

→ E + T + T

→ E + T + T + T

→ ... (never terminates)

This is exactly what happens when a top-down parser (like recursive descent) tries to handle a left-recursive grammar — it enters an infinite loop.

Why is Left Recursion a Problem?

Bottom-up parsers (LR parsers) handle left recursion fine. They work from the input upward, so they never need to predict what comes first — they just keep reducing.

Tracing a Recursive Descent Parser on E → E + T | T:

Example

parseE():

call parseE() ← immediately calls itself

call parseE() ← again...

... ← infinite recursion → stack overflow!

The parser never even looks at the input — it just keeps calling itself forever.

The Rule

Top-down parsers cannot handle left-recursive grammars. Left recursion must be eliminated before using LL or recursive descent parsing.

Eliminating Direct Left Recursion

Direct left recursion is removed by converting it into right recursion using a helper non-terminal.

The General Pattern

Left-recursive grammar:

Example

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

where:

A α are the left-recursive rules (A is the first symbol)
β are the non-left-recursive rules (do not start with A)

Transformed grammar (no left recursion):

Example

A → β₁ A' | β₂ A' | ... | βₘ A'

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

The new non-terminal A' (A-prime) captures the repeated trailing part. It recurses on the right, which is fine for top-down parsers.

Example 1 — Simple Expression Grammar

Original (left-recursive):

Example

E → E + T | T

Identify:

Left-recursive rule: E + T (α = + T)
Non-left-recursive rule: T (β = T)

Transformed:

Example

E → T E'

E' → + T E' | ε

Verification — derive "T + T + T":

Example

→ T E'

→ T + T E'

→ T + T + T E'

→ T + T + T ε

= T + T + T ✓

Same language — no left recursion.

Example 2 — Full Arithmetic Grammar

Original:

Example

E → E + T | E - T | T

T → T * F | T / F | F

F → ( E ) | id

Transformed:

Example

E → T E'

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

T → F T'

T' → * F T' | / F T' | ε

F → ( E ) | id

This is the classic LL(1)-ready form of arithmetic expressions.

Eliminating Indirect Left Recursion

Indirect left recursion is trickier. It requires a systematic algorithm that substitutes rules to reveal hidden direct left recursion, then eliminates it.

The Algorithm

Given: A grammar with non-terminals A₁, A₂, …, Aₙ in some fixed order.

Example

for i = 1 to n:

for j = 1 to i-1:

replace each production Aᵢ → Aⱼ γ

with: Aᵢ → δ₁ γ | δ₂ γ | ...

where Aⱼ → δ₁ | δ₂ | ... are the current productions for Aⱼ

eliminate any direct left recursion in Aᵢ's productions

The outer loop goes through each non-terminal in order. The inner loop substitutes earlier non-terminals to expose any hidden recursion.

Example — Indirect Left Recursion

Original grammar:

Example

S → A a | b

A → S b | d

Order: S = A₁, A = A₂.

Step 1 — Process A₁ = S:

No Aⱼ with j < 1, so skip the inner loop. Check for direct left recursion in S: none.

Example

S → A a | b (unchanged)

Step 2 — Process A₂ = A:

Inner loop: j = 1, substitute A₁ = S. A has production A → S b. Replace S with its productions:

Example

A → S b → becomes → (A a) b | b b

= A a b | b b

So A's productions are now:

Example

A → A a b | b b | d

Now A has direct left recursion! Eliminate it:

Identify: Left-recursive: A a b (α = a b), Non-left-recursive: b b and d (β)

Example

A → b b A' | d A'

A' → a b A' | ε

Final grammar (no left recursion):

Example

S → A a | b

A → b b A' | d A'

A' → a b A' | ε

Key Point

After eliminating indirect left recursion, the grammar generates the same language, but can now be parsed by a top-down parser without looping.

Left Recursion vs. Right Recursion

After eliminating left recursion, the grammar becomes right-recursive. It is worth understanding what this means for associativity.

Original Left-Recursive Grammar — Left-Associative

Example

E → E + T | T

Parse tree for a + b + c:

Result: (a + b) + c — left-associative. The leftmost E subtree groups first, so addition folds from the left.

Transformed Right-Recursive Grammar

Example

E → T E'

E' → + T E' | ε

Parse tree for a + b + c:

When you evaluate this tree the standard way (left to right, collecting operators), you still get (a + b) + c — the same left-associative result.

The tree shape changes, but the semantic result is the same. The elimination is safe.