retagged by
13,199 views
34 votes
34 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

  1. $\{S’ \rightarrow e S\}$ and $\{S’ \rightarrow \epsilon\}$
  2. $\{S’ \rightarrow e S\}$ and $\{ \}$
  3. $\{S’ \rightarrow \epsilon\}$ and $\{S’  \rightarrow \epsilon\}$
  4. $\{S’ \rightarrow  e S, S’ \rightarrow \varepsilon$} and $\{S’  \rightarrow \epsilon\}$
retagged by

3 Answers

Best answer
61 votes
61 votes
  • $\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

edited by
0 votes
0 votes
Solution: A

Since predictive parse table is constructed by filling the entry $T[A,\alpha]$ with productions of the form $A-> B$ , where $First(B)$ contains $\alpha$ and productions of the form $A-> \epsilon$ are filled in $T[A,\beta]$ ,where $\beta \in Follow(A)$
0 votes
0 votes
we have to put

S′→eS   into first(S) and

S′→ϵ     into follow(S′)

follow(S′)=($,e)
Answer:

Related questions

40 votes
40 votes
3 answers
1
Kathleen asked Sep 17, 2014
19,883 views
Consider the grammar shown below. $S \rightarrow C \ C$$C \rightarrow c \ C \mid d$This grammar isLL(1)SLR(1) but not LL(1)LALR(1) but not SLR(1)LR(I) but not LALR(1)
26 votes
26 votes
4 answers
3
67 votes
67 votes
10 answers
4
Kathleen asked Sep 16, 2014
26,978 views
Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?Removing left recursion aloneFactoring the grammar aloneRemoving left recursion and factor...