search
Log In
24 votes
4.4k 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\}$
in Compiler Design 4.4k views
0
For those interested in knowing, this is a shorthand for a grammar that describes if-then-else constructs and suffers from ambiguity known as the dangling else ambiguity. That's why in the parse table there are multiple entries in a single cell. (source: dragon book under top-down parsing)

3 Answers

47 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


edited by
0
How?
5

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, \$).
16

FOLLOW(S')=FOLLOW(S)

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

                 ={e,$}

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

0
if multiple entry in a column, then that grammar is not LL(1).
0
Yes.
0
How is follow of S'=(e, $)
0
predictive parsing table means?
0
By what I had understood till now, we add a production into a cell only if it's generating the respective terminal (of that cell). Here,S'-->eS was generating e, so it was placed in the cell M[S',e]. But why was S'--> epsilon required to be included there when its not even producing e? Please tell me what I'm grasping wrong in all this:)
0

can this grammar be accepted by predictive parser as it contains ambiguity(As it could lead to Dangling else)  in it ???

0 votes
we have to put

S′→eS   into first(S) and

S′→ϵ     into follow(S′)

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)$
0
Predective parse table means LL1 Parser. Ans is D
Answer:

Related questions

28 votes
3 answers
1
4.5k views
Consider the translation scheme shown below. S $\rightarrow$ T R R $\rightarrow$ + T {print(‘+’);} R$\mid \varepsilon$ T $\rightarrow$ num {print(num.val);} Here num is a token that represents an integer and num.val represents the corresponding integer value. For an input string ‘$9 + 5 + 2$’, this translation scheme will print $9 + 5 + 2$ $9 \ 5 + 2 +$ $9 \ 5 \ 2 + +$ $+ + 9 \ 5 \ 2$
asked Sep 17, 2014 in Compiler Design Kathleen 4.5k views
29 votes
3 answers
2
7.5k views
Consider the grammar shown below. $S \rightarrow C \ C$ $C \rightarrow c \ C \mid d$ This grammar is LL(1) SLR(1) but not LL(1) LALR(1) but not SLR(1) LR(I) but not LALR(1)
asked Sep 17, 2014 in Compiler Design Kathleen 7.5k views
29 votes
6 answers
3
3.7k views
The following program fragment is written in a programming language that allows global variables and does not allow nested declarations of functions. global int i=100, j=5; void P(x) { int i=10; print(x+10); i=200; j=20; print (x); } main() {P(i+j);} If the ... scoping and call by name parameter passing mechanism, the values printed by the above program are $115, 220$ $25, 220$ $25, 15$ $115, 105$
asked Apr 24, 2016 in Compiler Design jothee 3.7k views
22 votes
3 answers
4
3.3k views
Consider the syntax directed definition shown below. ... is $X = Y + Z$ $t_1 = Y+Z; X=t_1$ $t_1 =Y; t_2=t_1 +Z; X=t_2$ $t_1 =Y; t_2=Z; t_3=t_1+t_2; X=t_3$
asked Sep 17, 2014 in Compiler Design Kathleen 3.3k views
...