Consider the following expression grammar G: E -> E - T | T T -> T + F | F F…
2017
Consider the following expression grammar G:
E -> E - T | T T -> T + F | F F -> (E) | idWhich of the following grammars are not left recursive, but equivalent to G ?
Answer: C. E -> TX X -> -TX | ε T -> FY Y -> +FY | ε F -> (E) | id — Correct transformed grammar: The equivalent grammar with left recursion eliminated is shown below. E -> T X X -> - T X | ε T -> F Y Y -> + F Y | ε F -> (E) |…
- A.
E -> E - T | T
T -> T + F | F
F -> (E) | id - B.
E -> TE'
E' -> -TE' | ε
T -> T + F | F
F -> (E) | id - C.
E -> TX
X -> -TX | ε
T -> FY
Y -> +FY | ε
F -> (E) | id - D.
E -> TX | (TX)
X -> -TX | +TX | ε
T -> id
Attempted by 257 students.
Show answer & explanation
Correct answer: C
Correct transformed grammar: The equivalent grammar with left recursion eliminated is shown below.
E -> T X
X -> - T X | ε
T -> F Y
Y -> + F Y | ε
F -> (E) | id
Why this works: We removed immediate left recursion from both E and T by introducing new nonterminals X and Y that represent zero-or-more occurrences of the respective right-hand suffixes. X represents repeated '- T' segments and Y represents repeated '+ F' segments. This preserves the original operator precedence and left-associativity (plus binds tighter because it is handled inside T).
Brief notes on incorrect alternatives:
A grammar that keeps 'E -> E - T' and 'T -> T + F' remains left-recursive and thus is not the desired transformed form.
A grammar that removes left recursion only for E but keeps 'T -> T + F | F' still has left recursion in T and therefore is not fully transformed.
A grammar that restricts T to 'id' or embeds parentheses incorrectly (for example using '(TX)') changes the language and does not preserve the original 'F -> (E) | id' structure.
A video solution is available for this question — log in and enroll to watch it.
Explore the full course: Iocl Engineers Officers Grade A Paper 2