# GATE CSE 2021 Set 1 | Question: 31

334 views

Consider the following context-free grammar where the set of terminals is $\{a,b,c,d,f\}$. $$\begin{array}{lll} S & \rightarrow & d \: a \: T \mid R \: f \\ T & \rightarrow & a \: S \: \mid \: b \: a \: T \: \mid \epsilon \\ R & \rightarrow & c \: a \: T \: R \: \mid \epsilon \end{array}$$

The following is a partially-filled $LL(1)$ parsing table.

$$\begin{array} {c c c } & a & b & c & d & f & \ \\\hline S & & & \bigcirc{1} & S \rightarrow daT & 2 & \\\hline T & T \rightarrow aS & T \rightarrow baT & 3 & & T \rightarrow \varepsilon & 4\\\hline R & & & R \rightarrow caTR & & R \rightarrow \varepsilon & \end{array}$$

Which one of the following choices represents the correct combination for the numbered cells in the parsing table (“blank” denotes that the corresponding cell is empty)?

1. $1\;S \rightarrow Rf \qquad 2\;S \rightarrow Rf \qquad 3\; T \rightarrow \varepsilon \qquad 4\;T \rightarrow \varepsilon$
2. $1\;\text{blank} \qquad 2\;S \rightarrow Rf \qquad 3\; T \rightarrow \varepsilon \qquad 4\;T \rightarrow \varepsilon$
3. $1\;S \rightarrow Rf \qquad 2\;\text{blank} \qquad 3\; \text{blank} \qquad 4\;T \rightarrow \varepsilon$
4. $1\;\text{blank} \qquad 2\;S \rightarrow Rf \qquad 3\; \text{blank} \qquad 4\;\text{blank}$

recategorized ago
0
Option A?
1

yes A

 FIRST Follow $S \rightarrow daT / Rf$ $\left \{ d,c,f \right \}$ $\left \{ c,f,\$ \right \}T \rightarrow aS / baT/ \varepsilon \left \{ a,b,\varepsilon \right \}\left \{ c,f,\$\right \}$ $R \rightarrow caTR/ \varepsilon$ $\left \{ c,\varepsilon \right \}$ $\left \{ f \right \}$