Grammar transformations: eliminating left recursion (direct and indirect); left factoring

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• Which grammar makes + left associative: E → E + T | T or E → T + E | T? from Lesson 2.1.2
• What does Lex do when two rules match the same longest lexeme? from Lesson 1.3
• What is the difference between ∅ and {ε}? from Lesson 0.2.1

1 · The Story

📖

A junior clerk with a simple method

Kabir trains a junior clerk, Chetan, to check sentences with a simple method: “to check a phrase of some category, take its first rule and work through the rule’s parts from the left.”

The rulebook says: List → List , Item | Item. Chetan checks a List: first rule, first part … List. So he checks a List: first rule, first part … List. He writes “List” on his notepad forever and never reads a single word.

Kabir rewrites the rule so that it starts with something real: List → Item Rest, Rest → , Item Rest | (nothing). Same lists, no loop.

Chetan meets a second problem: Stmt → if Cond then Stmt and Stmt → if Cond then Stmt else Stmt start with the same four parts. Looking at the word “if”, he cannot choose. Kabir pulls the shared beginning out: Stmt → if Cond then Stmt Tail, Tail → else Stmt | (nothing). Now Chetan decides only when he reaches the point where the two rules differ.

2 · Predict First

🤔

After rewriting E → E + T | T to remove the loop, does the new grammar generate the same strings? Write your guess down. The answer is in the vault.

3 · Core Concept

Left recursion

A grammar is left recursive if some nonterminal A can derive a string beginning with A: A ⇒⁺ Aα. It is directly left recursive if a production has the form A → Aα, and indirectly if the loop goes through other nonterminals (A → Bβ, B → Aγ).

The parsing method of Chapter 2.3 expands the leftmost nonterminal by guessing a production. With A → Aα it expands A into A α, then that A into A α α, forever, without consuming input. So left recursion must be removed first.

Removing direct left recursion

Group A’s productions: A → Aα₁ | … | Aαₘ | β₁ | … | βₙ, where no βᵢ starts with A. Replace them by

A  → β₁ A' | … | βₙ A'
A' → α₁ A' | … | αₘ A' | ε

Idea: every A-string is one β followed by any number of α’s. The new A′ is right recursive (A′ → α A′).

Removing indirect left recursion

Order the nonterminals A₁, …, Aₙ. For i = 1 … n: for every j < i, replace each production Aᵢ → Aⱼγ by Aᵢ → δ₁γ | … | δₖγ, where Aⱼ → δ₁ | … | δₖ are Aⱼ’s current productions; then remove direct left recursion from Aᵢ. (Guaranteed to work if the grammar has no cycles A ⇒⁺ A; an ε-production in the input can be tolerated, as in the example below.)

Left factoring

When two alternatives of A start with the same prefix α, a one-token decision is impossible. Left factoring pulls out the longest common prefix:

A → α β₁ | α β₂ | γ      becomes      A  → α A' | γ
                                       A' → β₁ | β₂

Repeat until no two alternatives of any nonterminal share a first symbol.

Story → compiler term

4 · Visual

Three transformations, each computed by running the algorithm: direct left recursion (row 1), indirect left recursion with order S, A (row 2), left factoring of the if-then-else grammar (row 3; i = if, t = then, e = else).

5 · Worked Examples

Example 1 Easy

Remove left recursion from E → E + T | T, T → T * F | F, F → ( E ) | id.

Solution

Apply A → Aα | β ⇒ A → βA′, A′ → αA′ | ε to E (α = + T, β = T) and to T (α = * F, β = F):

E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | id

Like Kabir’s List → Item Rest, each E now starts with something real (a T).

Example 2 Medium

Remove all left recursion from S → A a | b, A → A c | S d | ε, using the order S, A.

Solution

i = 1 (S): no production of S starts with S; nothing to do.

i = 2 (A): substitute S into A → S d: A → A a d | b d. Now A → A c | A a d | b d | ε is directly left recursive with α₁ = c, α₂ = a d and β₁ = b d, β₂ = ε. Result:

S → A a | b
A → b d A' | A'
A' → c A' | a d A' | ε

The loop S → A a, A → S d went through two nonterminals: indirect left recursion, the hidden version of Chetan’s loop.

Example 3 GATE

Left factor A → a b c | a b d | a e | f.

Solution

First factor the common prefix a of the first three alternatives, then the common prefix b of b c | b d:

A → a A' | f
A' → b A'' | e
A'' → c | d

Each decision now waits until the point where alternatives differ, as Kabir taught Chetan with the if-statements.

6 · Shortcuts

⚡

Direct left recursion in one line: A → Aα | β ⇒ A → βA′, A′ → αA′ | ε. Count: one new nonterminal per left-recursive nonterminal, and one extra ε-production each. Valid when: directly left-recursive productions with at least one non-recursive alternative β.

⚡

Left factoring: group alternatives by first symbol; factor the longest common prefix; repeat inside the new nonterminal. Valid when: any grammar where two alternatives share a first symbol.

7 · GATE Traps

⚠️

• Removing left recursion does not change the language, but it changes the parse trees (and associativity is now carried by A′).
• Removing left recursion does not remove ambiguity, and left factoring does not either.
• Indirect left recursion is invisible in single productions: look for chains A → B…, B → A….
• A grammar can be free of left recursion and still need left factoring (and the reverse).
• If there is no β (A → Aα only), A generates no terminal string at all.

8 · Memory Hook

🧠

“Start with something real.” Left recursion: move the repeating part behind a new tail nonterminal. Left factoring: say the shared part once, decide later.

9 · Connect the Dots

The grammar is now in a shape a guessing clerk can follow. The next lesson builds that clerk properly: one procedure per nonterminal, guessing productions from the start symbol down, and rewinding when a guess fails.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markLeft recursion

After removing left recursion from S → S a b | S c | d, the grammar is:

• (A) S → d S', S' → a b S' | c S' | ε
• (B) S → d S' | ε, S' → a b | c
• (C) S → a b S | c S | d
• (D) S' → S a b | S c, S → d

Q2NAT1 markCount

After removing left recursion from S → S a b | S c | d, how many productions (counting each alternative separately, including ε) does the grammar have?

Numerical answer: ________

Q3MCQ1 markLeft factoring

Left factoring S → i E t S | i E t S e S | a gives:

• (A) S → i E t S S' | a, S' → e S | ε
• (B) S → i E t S | a, S' → e S
• (C) S → i E t S e S | a
• (D) S → S' | a, S' → i E t S e S | ε

Q4MSQ1 markFacts

Which are true?

• (A) Removing left recursion preserves the language.
• (B) Left factoring removes ambiguity.
• (C) A → B x, B → A y | z is left recursive.
• (D) The new nonterminal A′ in A → βA′ is right recursive.

Q5MCQ2 marksIndirect

Removing left recursion from A → A B | a, B → B b | c gives:

• (A) A → a A', A' → B A' | ε, B → c B', B' → b B' | ε
• (B) A → a B, B → b B | c
• (C) A → a A' | ε, B → c B'
• (D) A → B A | a, B → b B | c

11 · Rule Card

• Left recursion: A ⇒⁺ Aα; direct if A → Aα.
• A → Aα₁|…|Aαₘ|β₁|…|βₙ ⇒ A → β₁A′|…|βₙA′; A′ → α₁A′|…|αₘA′|ε.
• Indirect: order nonterminals; substitute earlier ones into Aᵢ → Aⱼγ; then remove direct.
• Left factoring: A → αβ₁|αβ₂ ⇒ A → αA′; A′ → β₁|β₂ (longest common prefix, repeat).
• Neither transformation changes the language; neither removes ambiguity.

12 · Concept Ledger

left recursion (direct, indirect)right recursionA′ (new tail nonterminal)left factoringcommon prefix

13 · Answer Vault