LI.2.2 Grammar transformations · GATE 2027 Compiler Design

ACompressed recap

🧾

Some parsing methods need grammars without left recursion (A ⇒⁺ Aα) and without common prefixes among alternatives. Direct left recursion A → Aα | β becomes A → βA′, A′ → αA′ | ε; indirect left recursion is removed by substituting earlier nonterminals in a fixed order and then removing direct recursion. Left factoring pulls out the longest common prefix: A → αA′, A′ → β₁ | β₂. Both keep the language; neither removes ambiguity.

BMerged rule card

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

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.

CInterleaved GATE-style questions

Q1MCQ1 markDirect

Remove left recursion from L → L , id | id:

(A) L → id L', L' → , id L' | ε
(B) L → id L', L' → , id L'
(C) L → , id L | id
(D) L' → L , id | ε

Q2MCQ1 markDetect

Which grammar is left recursive?

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

Q3NAT2 marksCount

Remove left recursion from E → E + T | E − T | T. How many productions (alternatives counted separately, ε included) does E′ have?

Numerical answer: ________

Q4MCQ1 markLeft factoring

Left factoring A → x y z | x y w | x q gives first:

(A) A → x A', A' → y z | y w | q
(B) A → x y A' | x q, A' → z | w
(C) A → x y z | x A'
(D) A → A' z | A' w

Q5MSQ2 marksFacts

Which are true?

(A) A left-recursive grammar can be unambiguous.
(B) After removing left recursion, + in the expression grammar is still evaluated left to right if the translation is written carefully.
(C) Left factoring is needed when two alternatives begin with the same symbol.
(D) Removing left recursion always shortens the grammar.

Q6MCQ2 marksIndirect

With order S, A, removing left recursion from S → A a | b, A → A c | S d | ε yields A’s productions:

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

Q7MCQ1 markPurpose

Left recursion must be removed mainly for:

(A) the guessing (predictive) parsing methods of Chapter 2.3
(B) the lexer
(C) every parsing method
(D) type checking

Q8NAT1 markCount

Left factor S → a b | a c | a d | e. How many alternatives does the new nonterminal S′ have?

Numerical answer: ________

Answer Vault

Try the questions first. Open when you are ready to check.

Q1 Answer: (A)1 mark

L → id L'; L' → , id L' | ε.

(B) is wrong: Without ε, L′ never ends.
(C) is wrong: Generates strings starting with a comma.
(D) is wrong: Still left recursive and L is lost.