The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
1.8k views

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\}$
asked in Compiler Design by Veteran (59.6k points) | 1.8k views

2 Answers

+35 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

answered by Boss (31.7k points)
edited by
0
How?
+4

from table

M[S’ , e] =S'->eS , S'->episolon

M[S’ , $]=S'->episolon

So ans will be D

0
Can you please explain how follow(S') =  (e, \$).
+9

FOLLOW(S')=FOLLOW(S)

FOLLOW(S)={FIRST(S') , $} 

                 ={e,$}

           
So, FOLLOW(S') ={e,$}

–1 vote
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)$
answered by Active (1.4k points)
0
Predective parse table means LL1 Parser. Ans is D
Answer:


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,903 questions
47,560 answers
146,291 comments
62,306 users