Consider the following context-free grammar where the set of terminals is…

GATE · 2021 · CS · Set 1 · Computer Science & IT

Consider the following context-free grammar where the set of terminals is {a,b,c,d,f}.

$\begin{array}{lll} \text{S} & \rightarrow & d \: a \: \text{T} \mid \text{R} \: f \\ \text{T} & \rightarrow & a \: \text{S} \: \mid \: b \: a \: \text{T} \: \mid \epsilon \\ \text{R} & \rightarrow & c \: a \: \text{T} \: \text{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 \text{S} & & & \boxed{1} & \text{S} \rightarrow da \text{T} & \boxed{2} & \\\hline \text{T} & \text{T} \rightarrow a\text{S} & \text{T} \rightarrow ba\text{T} & \boxed{3} & & \text{T} \rightarrow \varepsilon & \boxed{4}\\\hline \text{R} & & & \text{R} \rightarrow ca\text{T}\text{R} & & \text{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)?

A.
$\boxed{1}\;\text{S} \rightarrow \text{R}f \qquad \boxed{2}\;\text{S} \rightarrow \text{R}f \qquad \boxed{3}\; \text{T} \rightarrow \varepsilon \qquad \boxed{4}\;\text{T} \rightarrow \varepsilon$
B.
$\boxed{1}\;\text{blank} \qquad \boxed{2}\;\text{S} \rightarrow \text{R}f \qquad \boxed{3}\; \text{T} \rightarrow \varepsilon \qquad \boxed{4}\;\text{T} \rightarrow \varepsilon$
C.
$\boxed{1}\;\text{S} \rightarrow \text{R}f \qquad \boxed{2}\;\text{blank} \qquad \boxed{3}\; \text{blank} \qquad \boxed{4}\;\text{T} \rightarrow \varepsilon$
D.
$\boxed{1}\;\text{blank} \qquad \boxed{2}\;\text{S} \rightarrow \text{R}f \qquad \boxed{3}\; \text{blank} \qquad \boxed{4}\;\text{blank}$

Attempted by 156 students.

Explore the full course: Gate Guidance By Sanchit Sir