How to Eliminate Left Recursion in Grammars

To eliminate left recursion from a grammar, rewrite rules where a non-terminal calls itself first by introducing a new non-terminal that captures the recursion on the right side. This transforms rules like A → A α | β into A → β A' and A' → α A' | ε, removing immediate left recursion.

Syntax

Left recursion occurs when a grammar rule calls itself as the first element on the right side, like A → A α | β. To remove it, rewrite the rule into two parts:

• A → β A' where β is a non-left-recursive alternative.
• A' → α A' | ε where α is the recursive part and ε means empty (no input).

This change moves recursion to the right side, making the grammar suitable for top-down parsing.

plaintext

Original rule with left recursion:
A → A α | β

After elimination:
A → β A'
A' → α A' | ε

Example

This example shows how to eliminate immediate left recursion from a simple grammar rule for expressions:

plaintext

Original grammar:
Expr → Expr + Term | Term

Eliminated left recursion:
Expr → Term Expr'
Expr' → + Term Expr' | ε

Common Pitfalls

One common mistake is trying to eliminate left recursion without separating the recursive and non-recursive parts correctly, which can cause infinite loops in parsers.

Also, indirect left recursion (where recursion happens through multiple rules) requires first rewriting the grammar to expose immediate left recursion before elimination.

plaintext

Wrong approach (causes infinite recursion):
A → A α | β

Right approach:
A → β A'
A' → α A' | ε

Quick Reference

Step	Action
1	Identify rules with immediate left recursion (A → A α | β)
2	Rewrite as A → β A'
3	Define A' → α A' | ε to capture recursion on the right
4	For indirect left recursion, reorder rules to expose immediate recursion first
5	Test the new grammar with a top-down parser

Key Takeaways

Eliminate immediate left recursion by rewriting rules to move recursion to the right side.

Use a new non-terminal to represent repeated recursive parts.

Indirect left recursion must be converted to immediate before elimination.

Proper elimination prevents infinite loops in top-down parsers.

Test the transformed grammar to ensure correctness.