The Gateway to Computer Science Excellence

+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\}$

+46 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**

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,741 questions

57,253 answers

198,069 comments

104,708 users