The GATE Grind

GATE 2021 CS (CS1) – 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,$\char36$)? ('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

Grammar: $S\to daT\mid Rf$, $T\to aS\mid baT\mid\varepsilon$, $R\to caTR\mid\varepsilon$.

**FIRST sets**
- $FIRST(daT)=\{d\}$
- $FIRST(Rf)=FIRST(R)\setminus\{\varepsilon\}\cup\{f\}=\{c,f\}$, because $R$ can vanish.

So $S\to Rf$ goes in the cells for `c` (cell 1) and `f` (cell 2).

**FOLLOW(T)** (needed for $T\to\varepsilon$)
- $T$ ends $S\to daT$, so $FOLLOW(T)\supseteq FOLLOW(S)$, and $T\to aS$ gives $FOLLOW(S)\supseteq FOLLOW(T)$.
- $FOLLOW(S)=\{\char36\}\cup FOLLOW(T)$.
- In $R\to caTR$, $T$ is followed by $R$: $FIRST(R)\setminus\{\varepsilon\}=\{c\}$, and since $R$ can vanish also $FOLLOW(R)=\{f\}$.

So $FOLLOW(T)=\{c,f,\char36\}$ and $T\to\varepsilon$ is placed in columns `c` (cell 3), `f` and the end marker $\char36$ (cell 4).

Answer: (1) $S\to Rf$, (2) $S\to Rf$, (3) $T\to\varepsilon$, (4) $T\to\varepsilon$: option (A).

More Parsing and Syntax Analysis questions

All Parsing and Syntax Analysis questions →