The GATE Grind

GATE 2012 CS (CS1) – Question 63

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

S→aAbB | bAaB | ε; A→S; B→S. The partial predictive table has S row (E1,E2,S→ε), A row (A→S,A→S,error), B row (B→S,B→S,E3), for lookaheads a,b,end-marker respectively. Find E1,E2,E3.

  1. E1={S→aAbB,A→S}; E2={S→bAaB,B→S}; E3=B→S
  2. E1={S→aAbB,S→ε}; E2={S→bAaB,S→ε}; E3=S→ε
  3. E1={S→aAbB,S→ε}; E2={S→bAaB,S→ε}; E3=B→S
  4. E1={A→S,S→ε}; E2={B→S,S→ε}; E3=B→S

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) E1={S→aAbB,S→ε}; E2={S→bAaB,S→ε}; E3=B→S

Explanation

The a-leading and b-leading S alternatives enter E1 and E2 respectively. Since S is nullable and a,b belong to FOLLOW(S), S→ε also enters both cells, revealing LL(1) conflicts. B→S is nullable and the end-marker belongs to FOLLOW(B), so E3 is B→S. These entries are C; the grammar is not conflict-free LL(1).

More Parsing and Syntax Analysis questions

All Parsing and Syntax Analysis questions →