The GATE Grind

GATE 2012 CS (CS1) – Question 62

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 FIRST/FOLLOW for A and B.

  1. FIRST(A)=FIRST(B)={a,b,ε}; FOLLOW(A)={a,b}; FOLLOW(B)={a,b,end-marker}
  2. FIRST(A)={a,b,end-marker}; FIRST(B)={a,b,ε}; FOLLOW(A)={a,b}; FOLLOW(B)={end-marker}
  3. FIRST(A)=FIRST(B)={a,b,ε}; FOLLOW(A)={a,b}; FOLLOW(B)=∅
  4. FIRST(A)=FIRST(B)={a,b}; FOLLOW(A)=FOLLOW(B)={a,b}

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) FIRST(A)=FIRST(B)={a,b,ε}; FOLLOW(A)={a,b}; FOLLOW(B)={a,b,end-marker}

Explanation

A and B each derive S, whose alternatives begin with a,b or ε, so both FIRST sets are {a,b,ε}. A is directly followed by terminal b or a, giving FOLLOW(A)={a,b}. Through A→S these enter FOLLOW(S), along with the start end-marker. B occurs at the end of S’s rules and inherits FOLLOW(S), giving {a,b,end-marker}. Thus A.

More Parsing and Syntax Analysis questions

All Parsing and Syntax Analysis questions →