GATE 2015 CS (CS3) – Question 65
Grammar G has S→F | H, F→p | c, H→d | c. S1: LL(1) can parse every string using grammar G. S2: LR(1) can parse every string using grammar G. Which are correct?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (D) Neither
Explanation
The terminal c has two distinct derivations, S→F→c and S→H→c, making this grammar ambiguous. LL(1) has a FIRST-set conflict at S on c; LR(1) has competing reductions for c. No deterministic LL(1) or LR(1) parser handles this grammar without alteration. Thus neither S1 nor S2, D; the language itself could have a different unambiguous grammar.