GATE 2017 CS (CS2) – Question 42

Compiler Design · Parsing and Syntax Analysis · 2 marks · Multiple choice

G has E→E−T|T, T→T+F|F, F→(E)|id. Which equivalent grammar has no left recursion?

E→E−T|T; T→T+F|F; F→(E)|id
E→TE′; E′→−TE′|ε; T→T+F|F; F→(E)|id
E→TX; X→−TX|ε; T→FY; Y→+FY|ε; F→(E)|id
E→TX|(TX); X→−TX|+TX|ε; T→id

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) E→TX; X→−TX|ε; T→FY; Y→+FY|ε; F→(E)|id

Explanation

For A→Aα|β, eliminate immediate left recursion using A→βA′ and A′→αA′|ε. Applying this separately to E and T produces exactly option C. A retains both recursions and B retains T’s recursion. D changes the language and operator grouping.

More Parsing and Syntax Analysis questions

GATE 2012 CS (CS1) Q62 – S→aAbB bAaB ε; A→S; B→S. The partial predictive table has S row (E1,E2,S→ε), A row…
GATE 2012 CS (CS1) Q63 – S→aAbB bAaB ε; A→S; B→S. The partial predictive table has S row (E1,E2,S→ε), A row…
GATE 2013 CS (CS1) Q19 – A grammar has no ε-productions or unit productions (the source gives types A→ε and A→a).…
GATE 2013 CS (CS1) Q50 – Two LR(1) item sets share core X→c·X, X→·cX, X→·d. Their lookaheads are respectively c,d…
GATE 2011 CS (CS1) Q37 – Binary operator ↓ has lower precedence than ↑. Operator ↑ is right-associative and ↓…
GATE 2010 CS (CS1) Q48 – For the grammar S→aSa bSb c, which classification holds?

All Parsing and Syntax Analysis questions →