Project ForgeCompiler Design
Lexical Analysis & Parsing
GATE 2017
Hard
Consider the following expression grammar G:
E -> E - T | T T -> T + F | F F -> (E) | id
Which of the following grammars is NOT left recursive, but is equivalent to G?
- AE -> E-T | T ; T -> T+F | F ; F -> (E) | id
- BE -> TE' ; E' -> -TE' | ε ; T -> T+F | F ; F -> (E) | id
- E -> TX ; X -> -TX | ε ; T -> FY ; Y -> +FY | ε ; F -> (E) | id
- DE -> TX | (TX) ; X -> -TX | +TX | ε ; T -> id
Explanation
The original grammar has left recursion in BOTH E (E→E-T) and T (T→T+F). Option B only removes E's left recursion, leaving T→T+F|F still left-recursive — not fully non-left-recursive. Option C correctly applies the standard elimination to BOTH: E→TX, X→-TX|ε removes E's left recursion, and T→FY, Y→+FY|ε removes T's, while preserving the same language and operator associativity.
Source: GATE CS 2017 (Session 2) (2017)
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.