GATE CSE 2012 | Question: 53

Question

For the grammar below, a partial $LL(1)$ parsing table is also presented along with the grammar. Entries that need to be filled are indicated as $E1, E2,$ and $E3$. $\varepsilon$ is the empty string, \$ indicates end of input, and, $ \mid $ separates alternate right hand sides of productions.

• $ S \rightarrow a A b B \mid b A a B \mid \varepsilon $
• $ A \rightarrow S $
• $ B \rightarrow S $

$$\begin{array}{|l|l|}\hline \text{}  &  \textbf{a} & \textbf{b}  &  \textbf{\$} \\\hline  \text{$S$} & \text{E1} &  \text{E2}  &  \text{$S\rightarrow \varepsilon $} \\\hline  \text{$A$} & \text{$A\rightarrow S$} &  \text{$A\rightarrow S$}  &  \text{error} \\\hline  \text{$B$} & \text{$B\rightarrow S$} & \text{$B\rightarrow S$}  &  \text{$E3$} \\\hline \end{array}$$The appropriate entries for $E1, E2,$ and $E3$ are

• A. $ E1 : S \rightarrow aAbB, A\rightarrow S$
  $ E2 : S \rightarrow bAaB, B\rightarrow S $
  $ E3 : B \rightarrow S$
   
• B. $ E1 : S \rightarrow aAbB, S \rightarrow \varepsilon$
  $ E2 : S \rightarrow bAaB, S \rightarrow \varepsilon$
  $ E3 : S \rightarrow \varepsilon$
   
• C. $ E1 : S \rightarrow aAbB, S \rightarrow \varepsilon$
  $ E2 : S \rightarrow bAaB, S \rightarrow \varepsilon$
  $ E3 : B \rightarrow S$
   
• D. $ E1 : A \rightarrow S, S \rightarrow \varepsilon$
  $ E2 : B \rightarrow S, S \rightarrow \varepsilon$
  $ E3 : B \rightarrow S$

Comments

for E3  we have to do replace  S in this production  B->S  is like B->aAbB/bAaB/e  then the row of B must contain        B->S for first column and same for second column and then for third column given as E3 for that u have to calculate      B->e means follow(B) which is {a,b,$} then put B->S into all three column due to first  and second column already have this B->S so no effect and for E3 it will be B->S but not B->e   where e is epsilon 

Answer 1

To make $LL(1)$ parsing table first we have to find $\text{FIRST}$ and $\text{FOLLOW}$ sets from the given grammar.

• $\text{FIRST}(S)=\{a,b,\epsilon\}$
• $\text{FIRST}(A)=\{a,b,\epsilon\}$
• $\text{FIRST}(B)=\{a,b,\epsilon\}$
• $\text{FOLLOW}(S)= \{a,b,\$\}$
• $\text{FOLLOW}(A)= \{a,b\}$
• $\text{FOLLOW}(B)= \{a,b,\$\}$

Now lets make $LL(1)$ parse table

$$\begin{array}{|c|l|l|l|}\hline \textbf{Non Terminal} & \textbf{a} & \textbf{b}  &  \textbf{\$} \\\hline
\text{$S$} & \text{$S \rightarrow aAbB$},&\text{$S \rightarrow bAbB$},& \text{$S\rightarrow \varepsilon $}\\
& \text{$S \rightarrow \epsilon$} &  \text{$S \rightarrow \epsilon$}  &  \\\hline 
\text{$A$} & \text{$A\rightarrow S$} &  \text{$A\rightarrow S$}  &  \text{} \\\hline  \text{$B$} & \text{$B\rightarrow S$} & \text{$B\rightarrow S$}  &  \text{$B \rightarrow S$} \\\hline \end{array}$$

 Here is the explanation of entries asked in question

1. For E1 and E2 Look into $\text{FIRST}(S)=\{a,b,\epsilon\}$.
   a is because of $S \rightarrow aAbB$ and b is because of $S \rightarrow bAaB$
   So $M[S,a]$ and $M[S,b]$ will contain $S \rightarrow aAbB$ and $S \rightarrow bAaB$ respectively. For epsilon look into $\text{FOLLOW}(S)= \{a,b,\$\}$. So $S \rightarrow \epsilon$ will be in $M[S,a]$, $M[S,b]$ and $M[S,\$]$
2. Now for E3 look into $\text{FIRST}(B)= \{a,b,\epsilon\}$. $a$ and $b$ are because of $B \rightarrow S$.
   So $M[B,a]$ and $M[B,b]$ will contain $B \rightarrow S$ and for $\epsilon$, look into $\text{FOLLOW}(B)= \{a,b,\$\}$. Hence $M[B,\$]$ will contain $B \rightarrow S.$

Now we get the answer as E1 is $S\rightarrow aAbB,$ $S\rightarrow \epsilon,$ E2 is $S\rightarrow bAaB,$ $S\rightarrow \epsilon$ and E3 is $B \rightarrow S.$

Hence, Option (C) is correct.

Comments

In given question , why we fill B-->S in E3 because in LL(1) we fill only epsilon production under follow symbol..And Non epsilon production under First symbol..

---

Siddhartha1997  read this discussion https://gateoverflow.in/234905/madeeasy-test-series-compiler-design-parsing

& read Shaik Masthan sir’s  discussion. copying his comments   here-

 

 

LL(1) parsing definition :-

for each production A-> α

1)for each terminal a in first(α) ;add A->α in M[A,a]

2)if α is nullable ,then for each terminal a in follow(A) , add A−>α in M[A,a]

 

example-

let take A -> α | ϵ

if A -> α also lead to empty string, then you have to keep both A -> α and A -> ϵ productions in Follow(A).

in simple terms,

First separate the productions like 

A --> α | β    ===========>  A -> α   and A --> β

then take each production, apply first of RHS but not LHS.

keep A -> α  in First(α) , if  First(α) contains ϵ, then keep A -> α  in Follow(A

 

---

typo:

2.now for E3, look into...

Answer 2

Entry E1 is $S \to aAbB$, $S \to \epsilon$ (Follow of $S$ contains $a$)

E2 is $S \to bAaB$, $S \to \epsilon$ (Follow  of $S$ contains $b$)

E3 is $B \to S$ (Follow of $B$ contains $\$$)

Hence, the answer to question 53 is option C.

Comments

Why aren't we adding  B→∊ in   M[B,a ] and  M[B,b] and  M[B,$] ..... ?

---

@pooja palod ma'am can u telll  the follow of B CONTAIN {a,b,$} so epsilon should be in entire row na??

---

read the comment of Shaik Masthan sir hope it will help  https://gateoverflow.in/234905/parsing

---

Only finding the FOLLOW of variables does the job, right?

---

@arpit_18 we  find the FOLLOW of any non terminal when  that non-terminal contains epsilon .

Answer 3

Ans C

Here First(S)={∊,a,b} ,

Follow (S)={ \$,a,b}

Follow (B)={\$,a,b}

Comments

@Arjun Sir pls check here is content loss.

---

\$ is used as latex delimiter, so to type in \$, escape it as \\\$