in Compiler Design retagged by
13,058 views
34 votes
34 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

  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 retagged by
13.1k views

2 Comments

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

The grammar is NOT LL(1) because it is ambiguous.

To know why this grammar is ambiguous see GATE2007-52.

0
0

3 Answers

61 votes
61 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

4 Comments

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:)
1
1

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

0
0

@Jithendra319 no this grammar won’t be accepted by predictive parser because it contains ambiguity.

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

1 comment

Predective parse table means LL1 Parser. Ans is D
0
0
0 votes
0 votes
we have to put

S′→eS   into first(S) and

S′→ϵ     into follow(S′)

follow(S′)=($,e)
Answer:

Related questions