The GATE Grind

GATE 2024 CS (CS1) – Question 38

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

Consider grammar G with start symbol S: S→daT | (1); T→aS | bT | (2); R→(3) | ε. Terminals are {a,b,c,d,f}. FIRST(S)={c,d,f}, FIRST(T)={a,b,ε}, FIRST(R)={c,ε}; FOLLOW(S)=FOLLOW(T)={c,f,$}, FOLLOW(R)={f}. Which option CORRECTLY fills in the incomplete productions?

  1. (1) S→Rf (2) T→ε (3) R→cTR
  2. (1) S→fR (2) T→ε (3) R→cTR
  3. (1) S→fR (2) T→cT (3) R→cR
  4. (1) S→Rf (2) T→cT (3) R→cR

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) (1) S→Rf (2) T→ε (3) R→cTR

Explanation

FIRST(S) includes c,f via S→Rf (R gives c or ε then f). T needs ε since FIRST(T) has ε. R→cTR yields FIRST(R)={c,ε} and FOLLOW(R)={f} since R is followed by f in S→Rf.