GATE Overflow Test Series | Compiler Design | Test 1 | Question: 15

Question

Consider the following grammar:

• $E \rightarrow TE'$
• $E' \rightarrow +TE' \mid \epsilon$
• $T \rightarrow FT'$
• $T' \rightarrow \ast FT' \mid \epsilon$
• $F \rightarrow (E) \mid id$

In the predictive parser table $M,$ of the grammar, the entries $M[E,id]$ and $M[T',\$]$ respectively are _______

• A. $E \rightarrow TE'\:\text{and}\: T' \rightarrow \ast FT'$
• B. $E \rightarrow TE'\:\text{and}\: T' \rightarrow \epsilon$
• C. $E' \rightarrow +TE'\:\text{and}\: T' \rightarrow \ast FT'$
• D. $E \rightarrow id\:\text{and}\: T' \rightarrow \epsilon$

Answer 1

Given that the grammar:

• $E \rightarrow TE'$
• $E' \rightarrow +TE' \mid \epsilon$
• $T \rightarrow FT'$
• $T' \rightarrow \ast FT' \mid \epsilon$
• $F \rightarrow (E) \mid id$

Then:

• $FIRST(E) = FIRST(T) = FIRST(F) = \{( , id\}$
• $FIRST(E’) = \{+, \epsilon\}$
• $FIRST(T’) = \{\ast,\epsilon \}$
• $FOLLOW(E) = FOLLOW(E’) = \{) , \$\}$
• $FOLLOW(T) = FOLLOW(T’) = \{+, ), \$\}$
• $FOLLOW(F) = \{+, \ast, ), \$\}$

After FIRST and FOLLOW sets are done, Predictive parsing table is filled as:

For each production $A \to \alpha,$ do the following :

For each terminal $‘a’$ in FIRST(A), add       $A \to \alpha$ to $M[A,a].$ (For everything in FIRST(A), $A \to \alpha$ is a valid parser move)

If $\epsilon$ is in $\text{FIRST}(\alpha)$ then for each terminal or end delimiter $b$ in $\text{FOLLOW}(A),$ add $A \to \alpha$ to $M[A,b].$

Now for the given grammar, for $E \rightarrow TE',$ FIRST(E) has $\{(,id\}$ and so we add $E \rightarrow TE'$ to both $M[E,(]$ and $M[E,id].$

For $T' \rightarrow \epsilon,$ we add $T' \rightarrow \epsilon$ to $M[T', \$], M[T', )]$ and $M[T', +]$ as $FOLLOW(T')=\{+, ),\$\}.$

$\therefore M[E,id] = E \rightarrow TE',$ and $M[T',\$] = T' \rightarrow \epsilon.$

So, the correct answer is $(B).$