The GATE Grind

GATE 2021 CS – Question 41

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

Consider the following context-free grammar where the set of terminals is {a, b, c, d, f}.
S -> d a T | R f
T -> a S | b a T | epsilon
R -> c a T R | epsilon
The partially-filled LL(1) parsing table has entries: S on d: S -> daT; T on a: T -> aS; T on b: T -> baT; T on f: T -> epsilon; R on c: R -> caTR; R on f: R -> epsilon. Which one of the following choices represents the correct combination for the numbered cells (1: S,c; 2: S,f; 3: T,c; 4: T,$)? ('blank' denotes that the corresponding cell is empty)

  1. (1) S -> Rf (2) S -> Rf (3) T -> epsilon (4) T -> epsilon
  2. (1) blank (2) S -> Rf (3) T -> epsilon (4) T -> epsilon
  3. (1) S -> Rf (2) blank (3) blank (4) T -> epsilon
  4. (1) blank (2) S -> Rf (3) blank (4) blank

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) (1) S -> Rf (2) S -> Rf (3) T -> epsilon (4) T -> epsilon

Explanation

FIRST(Rf) = {c, f}, so S -> Rf goes in cells c and f. FOLLOW(T) = {c, f, $}, since T can be followed by R, f, and end of input, so T -> epsilon fills the c and $ cells.