# GATE2003-56

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

## Related questions

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$
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)
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$
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$