2,938 views

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 $\textsf{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)?

1. $\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$
2. $\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$
3. $\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$
4. $\boxed{1}\;\text{blank} \qquad \boxed{2}\;\text{S} \rightarrow \text{R}f \qquad \boxed{3}\; \text{blank} \qquad \boxed{4}\;\text{blank}$

Option A?

yes A

$\begin{array}{|c|c|c|}\hline &\textsf{FIRST}&\textsf{FOLLOW}\\\hline S \rightarrow daT \mid Rf & \left \{ d,c,f \right \} & \left \{ c,f,\$ \right \} \\\hline
T \rightarrow aS \mid baT \mid \varepsilon & \left \{ a,b,\varepsilon \right \} & \left \{ c,f,\$\right \} \\ \hline R \rightarrow caTR\mid \varepsilon & \left \{ c,\varepsilon \right \} & \left \{ f \right \} \\\hline \end{array}$

$\begin{array}{|c|c|c|c|c|c|c|}\hline &a&b&c&d&f&\$ \\ \hline
S & & &\underset{\boxed{1}} {S \rightarrow Rf}& S \rightarrow daT &\underset{\boxed{2}}{S \rightarrow Rf}& \\ \hline
T & T \rightarrow aS & T \rightarrow  baT & \underset{\boxed{3}}{T \rightarrow  \varepsilon} &&T \rightarrow  \varepsilon & \underset{\boxed{4}}{T \rightarrow  \varepsilon} \\ \hline
R & && R \rightarrow caTR && R \rightarrow  \varepsilon \\ \hline
\end{array}$Ans: A (1)$S \rightarrow Rf\quad$(2)$S \rightarrow Rf\quad$(3)$T \rightarrow  \varepsilon \quad$(4)$T \rightarrow  \varepsilon $4 Comments In$1$and$2$, s→$\epsilon\$   will also be present right?

@Pranavpurkar in 1 and 2  S->epsilon will not be present because FIRST of S does not contain epsilon .

If  FIRST of a non terminal contains epsilon then we place epsilon on the FOLLOW of that non-terminal.

@abir_banerjee

yes, got it

Thanks bro!

Ans: A  (1) S→Rf (2) S→Rf (3) T→ε (4) T→ε

by