3.2 Grammar Ambiguity, Elimination of Left Recursion & Left Factoring Algorithms

Back to DBMS Notes

📚Module 01Grammar Ambiguity, Left Recursion & Left Factoring⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: The Confusing Fork in the Road

Imagine driving down an expressway toward an intersection:

1. The Ambiguous Road Sign: A sign reads: "Take Exit Left OR Take Exit Right to reach Airport", but one route charges a heavy toll while the other is free. Drivers make conflicting, unpredictable choices. An Ambiguous Grammar permits multiple distinct parse trees for the same string, creating undefined runtime behaviors.
2. The Left Recursion Roundabout (Infinite Loop): A roundabout instruction reads: "To exit the roundabout, first drive around the roundabout." A Left-Recursive Grammar ($A \to A \alpha$) forces a top-down parser to call itself recursively before consuming a single token, triggering a stack overflow.
3. The Left Factoring Dilemma (Delayed Decision): Two highway destinations share the exact same access highway for 10 miles before branching into Downtown and Suburbs. Left Factoring defers the parsing decision until the common prefix is consumed and the diverging token appears.

💻 Bridging to Computer Science: Ambiguity, Left Recursion, and Left Factoring

Before a top-down predictive parser (such as an LL(1) parser) can parse a programming language, the grammar must be made compiler-friendly:

• Eliminate Ambiguity: Ensure every valid sentence produces exactly one unique parse tree.
• Eliminate Left Recursion: Convert left-recursive rules into right-recursive forms so top-down parsers do not enter infinite recursion.
• Apply Left Factoring: Extract common prefixes to eliminate backtracking.

📑Table of Contents

• 🏗️ Architectural Foundations & Mechanics: Grammar Ambiguity
  • 📜 Formal Definition of Ambiguity
• 🔄 Algorithmic Elimination of Left Recursion
  • ⚡ Eliminating Immediate Left Recursion
• 🌐 The General (Indirect) Left Recursion Elimination Algorithm
• ✂️ The Left Factoring Transformation Algorithm
  • 🎯 Left Factoring Transformation Rule
• 🏭 Real-World Production Context: How Industry Builds This
• 📐 Numerical Applications & Worked Examples
  • Example 1: Eliminating Indirect Left Recursion
  • Example 2: Step-by-Step Left Factoring of Nested Prefixes
• 🎯 Exam & Interview Pitfall Check

---

🏗️ Architectural Foundations & Mechanics: Grammar Ambiguity

Ambiguous vs Unambiguous Grammar Architecture

Contrasting non-deterministic ambiguity against structured precedence hierarchies

Fatal Flaw

Ambiguous Grammar

⚠️

Dominant Architecture / DomainE -> E + E | E * E | id

• •A single string admits two or more distinct parse trees (or LMDs/RMDs).
• •Generates conflicting operator associativity and precedence.
• •Expression 2 + 3 * 4 could evaluate to 14 or 20 depending on the tree.
• •Undecidable: No general algorithm can determine if an arbitrary CFG is ambiguous.

"Computers require deterministic execution; ambiguity produces unpredictable binaries."

Compiler Ready

Unambiguous Structured Grammar

🎯

Dominant Architecture / DomainE -> E + T | T, T -> T * F | F

• •Every valid string produces exactly one unique parse tree.
• •Precedence is encoded structurally into the depth of the grammar rules.
• •Deeper subtrees execute prior to higher-level operators in post-order traversal.
• •Enforces deterministic Left-to-Right or Right-to-Left associativity.

"Structural hierarchy eliminates ambiguity and guarantees mathematically rigorous parsing."

📜 Formal Definition of Ambiguity

A Context-Free Grammar $G$ is Ambiguous if and only if there exists at least one terminal string $w \in \mathcal{L}(G)$ that admits:

1. Two or more distinct Parse Trees, OR
2. Two or more distinct Leftmost Derivations (LMD), OR
3. Two or more distinct Rightmost Derivations (RMD).

Concrete Ambiguity Proof for Grammar: S → aS | Sa | a

Consider the grammar $S \to aS \mid Sa \mid a$ and the input string $w = aa$:

• Derivation 1: $S \Rightarrow aS \Rightarrow aa$ (using $S \to a$).
• Derivation 2: $S \Rightarrow Sa \Rightarrow aa$ (using $S \to a$).

Because string $aa$ possesses two distinct parse trees, the grammar is Ambiguous.

Fundamental Ambiguity Theorem: A grammar that is both left and right recursive on the same non-terminal (e.g., $S \to S \alpha S$) is always ambiguous! However, a grammar that is ambiguous need not be both left and right recursive.

---

🔄 Algorithmic Elimination of Left Recursion

A grammar is Left-Recursive if it contains a non-terminal $A$ such that:

$$A \Rightarrow^+ A \alpha \quad \text{for some string } \alpha \in (V \cup \Sigma)^*$$

If a CFG contains left recursion, a top-down parser will enter an infinite recursive loop without consuming any input token. To avoid this, we transform left-recursive grammars into equivalent right-recursive productions.

⚡ Eliminating Immediate Left Recursion

Consider the immediate left-recursive production:

$$A \to A \alpha \mid \beta \quad (\text{where } \beta \text{ does not begin with } A)$$

This generates strings of the regular expression pattern $\beta \alpha^*$:

$$A \Rightarrow A \alpha \Rightarrow A \alpha \alpha \Rightarrow \beta \alpha \alpha$$

We replace left recursion with right recursion by introducing an auxiliary non-terminal $A'$:

$$\begin{aligned} A &\to \beta A' \\ A' &\to \alpha A' \mid \epsilon \end{aligned}$$

Universal Formula for Multiple Productions:

For productions of the form:

$$A \to A \alpha_1 \mid A \alpha_2 \mid \dots \mid A \alpha_m \mid \beta_1 \mid \beta_2 \mid \dots \mid \beta_n$$

The equivalent transformed grammar is:

📐Universal Immediate Left Recursion Elimination Formulaformula

$$\begin{aligned} A &\to \beta_1 A' \mid \beta_2 A' \mid \dots \mid \beta_n A' \\ A' &\to \alpha_1 A' \mid \alpha_2 A' \mid \dots \mid \alpha_m A' \mid \epsilon \end{aligned}$$

---

🌐 The General (Indirect) Left Recursion Elimination Algorithm

A grammar may contain indirect left recursion where recursion spans multiple non-terminals:

$$S \to A a \mid b, \quad A \to S c \mid d$$

Here, $S \Rightarrow A a \Rightarrow S c a$, forming a cycle $S \Rightarrow^+ S c a$. Immediate elimination cannot be applied directly. We apply the systematic ordering algorithm:

Systematic Indirect Left Recursion Elimination Algorithm

Systematic algorithm eliminating cycles and indirect left-recursive dependencies

1

Impose Global Ordering on Non-Terminals

Ordering

Arrange all non-terminals in some arbitrary fixed linear order: A₁, A₂, ..., Aₙ.

2

Nested Forward-Substitution Loop

Substitution

For i = 1 to n: For j = 1 to i - 1: Replace every production Aᵢ -> Aⱼ γ with Aᵢ -> δ₁ γ | δ₂ γ | ... where Aⱼ -> δ₁ | δ₂ | ... are current productions of Aⱼ.

3

Eliminate Immediate Left Recursion on Aᵢ

Immediate Fix

Apply the standard immediate left recursion transformation formula to the productions of Aᵢ.

4

Eliminate Unreachable Non-Terminals

Cleanup

Remove any non-terminals that became dead or unreachable during substitution passes.

---

✂️ The Left Factoring Transformation Algorithm

A grammar is Non-Deterministic if two or more alternatives for a non-terminal share a common prefix:

$$A \to \alpha \beta_1 \mid \alpha \beta_2$$

A predictive top-down parser cannot determine whether to expand $A \to \alpha \beta_1$ or $A \to \alpha \beta_2$ by inspecting the lookahead token because both alternatives begin with $\alpha$. Without left factoring, the parser must rely on expensive backtracking.

🎯 Left Factoring Transformation Rule

To remove the common prefix and make the grammar deterministic:

$$\begin{aligned} A &\to \alpha A' \\ A' &\to \beta_1 \mid \beta_2 \end{aligned}$$

This defers the parsing decision until the common prefix $\alpha$ has been consumed and the divergent token appears.

---

🏭 Real-World Production Context: How Industry Builds This

In industrial compiler engineering:

• Top-Down Parsers (LL, Recursive Descent, ANTLR 3):
  • Require strict elimination of all left recursion and full left factoring.
  • Converting $E \to E + T \mid T$ into $E \to T E', E' \to + T E' \mid \epsilon$ flips the parse tree associativity from left-associative to right-associative. The compiler's AST construction actions must explicitly reconstruct left associativity.
• Bottom-Up Parsers (LR, LALR, GNU Bison, Yacc):
  • Left recursion is actively preferred! In an LR parser, left-recursive rules reduce tokens immediately, keeping the parser state stack bounded at $O(1)$ memory. Right-recursive rules force the parser to shift the entire input onto the stack, consuming $O(n)$ stack space!

Modern parser generators like ANTLR 4 accept direct left-recursive expressions natively. At runtime, ANTLR's $ALL(*)$ algorithm dynamically rewires left-recursive rules into precedence-climbing state graphs, sparing engineers from manual grammar rewrites.

---

📐 Numerical Applications & Worked Examples

Example 1: Eliminating Indirect Left Recursion

Apply the general left recursion elimination algorithm to the following grammar:

$$\begin{aligned} S &\to A a \mid b \\ A &\to A c \mid S d \mid \epsilon \end{aligned}$$

Step-by-Step Analytical Solution:

Step 1: Order the Non-Terminals
Let $A_1 = S$ and $A_2 = A$.

Step 2: Process $i = 1$ ($A_1 = S$)
Productions for $S$: $S \to A a \mid b$ There is no immediate left recursion on $S$. $S$ remains unchanged.

Step 3: Process $i = 2$ ($A_2 = A$)
Substitute productions of $S$ into $A \to S d$: Since $S \to A a \mid b$, replacing $S$ in $A \to S d$ gives:

$$A \to A c \mid (A a \mid b) d \mid \epsilon \implies A \to A c \mid A a d \mid b d \mid \epsilon$$

Group $A$-productions into left-recursive and non-left-recursive sets:

• Left-recursive terms: $A \to A c \mid A (a d)$ (so $\alpha_1 = c, \alpha_2 = a d$).
• Non-left-recursive terms: $A \to b d \mid \epsilon$ (so $\beta_1 = b d, \beta_2 = \epsilon$).

Apply immediate left recursion elimination on $A$:

$$\begin{aligned} A &\to b d A' \mid A' \\ A' &\to c A' \mid a d A' \mid \epsilon \end{aligned}$$

Final Transformed Grammar:

$$\begin{aligned} S &\to A a \mid b \\ A &\to b d A' \mid A' \\ A' &\to c A' \mid a d A' \mid \epsilon \end{aligned}$$

The grammar is now completely free of both direct and indirect left recursion!

---

Example 2: Step-by-Step Left Factoring of Nested Prefixes

Left-factor the following non-deterministic grammar:

$$S \to a S b \mid a b S \mid a b$$

Step-by-Step Analytical Solution:

Pass 1: Extract Common Prefix $a$
All three alternatives share the common prefix $\alpha = a$:

$$\begin{aligned} S &\to a S' \\ S' &\to S b \mid b S \mid b \end{aligned}$$

Pass 2: Factor Remaining Alternatives in $S'$
Observe that in $S'$, the alternatives $b S$ and $b$ share a common prefix $\alpha_2 = b$:

$$\begin{aligned} S &\to a S' \\ S' &\to S b \mid b S'' \\ S'' &\to S \mid \epsilon \end{aligned}$$

The grammar is now completely left-factored and ready for deterministic predictive parsing without backtracking!

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: "Why do Top-Down predictive parsers fail on Left-Recursive grammars while Bottom-Up parsers thrive on them?"
Key Focus Points:

• Top-Down Failure: A top-down parser predicts productions from the start symbol down to terminals. For $A \to A \alpha$, the parser calls function A(), which immediately calls A() again before consuming any input token, resulting in infinite recursion.
• Bottom-Up Advantage: A bottom-up parser shifts terminals onto its stack and reduces them when a handle appears. For $A \to A \alpha$, the parser shifts $\alpha$ and reduces $A \alpha \to A$ iteratively, maintaining $O(1)$ stack depth.

Question 2: "Does Left Factoring eliminate ambiguity from an ambiguous grammar?"
Key Focus Points:

• No: Left factoring eliminates local non-determinism (shared prefixes), allowing a parser with 1-token lookahead to pick a branch.
• Preservation of Ambiguity: If the underlying language construct is ambiguous (e.g. the Dangling-Else), left factoring merely packages the conflict into a subsequent non-terminal ($S' \to e S \mid \epsilon$). Resolving ambiguity requires explicit disambiguation rules.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Does eliminating left recursion alter the language generated by the grammar?
Answer: No, but it alters the parse tree structure. The transformed right-recursive grammar generates the exact same language $\mathcal{L}(G)$, but the parse trees become right-leaning rather than left-leaning. This reverses the apparent operator associativity from left-to-right to right-to-left.

Trap 2: Is every grammar that is both left and right recursive ambiguous?
Answer: Yes, if the recursion is on the same non-terminal symbol. For example, $E \to E + E \mid id$ is both left and right recursive on $E$, and is guaranteed to be ambiguous. However, having left recursion on one symbol ($A \to A a$) and right recursion on another symbol ($B \to b B$) does not imply ambiguity.

---

🗺️View Complete Compiler Design Roadmap & Syllabus

← Previous Topic3.1 Context-Free Grammars & Parse TreesNext Topic →4.1 FIRST and FOLLOW Sets