24 votes

Consider the grammar shown below

- $S \rightarrow i E t S S’ \mid a$
- $S’ \rightarrow e S \mid \epsilon$
- $E \rightarrow b$

In the predictive parse table, $M,$ of this grammar, the entries $M[S’ , e]$ and $M[S’ , \$]$ respectively are

- $\{S’ \rightarrow e S\}$ and $\{S’ \rightarrow \epsilon\}$
- $\{S’ \rightarrow e S\}$ and $\{ \}$
- $\{S’ \rightarrow \epsilon\}$ and $\{S’ \rightarrow \epsilon\}$
- $\{S’ \rightarrow e S, S’ \rightarrow \varepsilon$} and $\{S’ \rightarrow \epsilon\}$

47 votes

Best answer

- $\text{FIRST} (S)=\{i,a\}$
- $\text{FIRST}(S')=\{e, \epsilon\}$
- $\text{FIRST}(E)=\{b\}$
- $\text{FOLLOW}(S')=\{e,\$\}$

Only when $\text{FIRST}$ contains $\epsilon,$ we need to consider $\text{FOLLOW}$ for getting the parsing table entry.

$M[S',e]=\{S' \rightarrow eS(\text{FIRST}),S' \rightarrow \epsilon \;(\text{considering }\text{FOLLOW})\}$

$M[S',\$]=\{S \rightarrow \epsilon\}$

$$\begin{array}{|l|c|c|c|l|c|c|} \hline \text{} & \text{$a$} & \text{$i$} & \text{$b$} & \text{$e$} & \text{$t$} & \text{\$} \\\hline \text{$S$} & \text{$S \rightarrow a$} &\text{$S \rightarrow ietSS'$} &\text{} &\text{} &\text{} \\\hline \text{$S'$} & \text{} & \text{} & \text{} & \text{$S' \rightarrow eS$} ,&\\

&&&&

\text{$S' \rightarrow \epsilon$} & \text{} & \text{$S' \rightarrow \epsilon$} \\\hline E & \text{} & \text{} & \text{$E \rightarrow b$} & \text{} & \text{} & \text{} \\\hline \end{array}$$

Answer is **D**

0

You can see here about predictive parsing: https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/handouts/090%20Top-Down%20Parsing.pdf

0

By what I had understood till now, we add a production into a cell only if it's generating the respective terminal (of that cell). Here,S'-->eS was generating e, so it was placed in the cell M[S',e]. But why was S'--> epsilon required to be included there when its not even producing e? Please tell me what I'm grasping wrong in all this:)