Project ForgeCompiler Design
Lexical Analysis & Parsing
GATE 2016
Hard
Which one of the following grammars is free from left recursion?
(A) S→AB, A→Aa|b, B→c (B) S→Ab|Bb|c, A→Bd|ε, B→e (C) S→Aa|B, A→Bb|Sc|ε, B→d (D) S→Aa|Bb|c, A→Bd|ε, B→Ae|ε
- A(A)
- (B)
- C(C)
- D(D)
Explanation
(A) A→Aa is directly left-recursive. (C) has indirect left recursion: S→Aa where A→Sc gives S⇒Aa⇒Sca. (D) has indirect left recursion: A→Bd where B→Ae gives A⇒Bd⇒Aed. (B) has no cycle back to S or A: S's productions never reinvoke S, A only leads to Bd or ε, and B is purely terminal (e) — no left recursion anywhere.
Source: GATE CS 2016 (Session 2 / Set B) (2016)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.