How?

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

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

$a $ | $i $ | $b$ | $e $ | $t $ | $\$$ | |

$S$ | $S \rightarrow a$ | $S \rightarrow ietSS'$ | ||||

$S'$ |
$S' \rightarrow eS$ $S' \rightarrow \epsilon$ |
$S' \rightarrow \epsilon$ | ||||

$E$ | $E \rightarrow b$ |

Answer is **D**

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.9k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 449
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

37,999 questions

45,495 answers

131,568 comments

48,630 users