edited by
17,187 views
42 votes
42 votes

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

  1. $ E1 : S \rightarrow aAbB, A\rightarrow S$
    $ E2 : S \rightarrow bAaB, B\rightarrow S $
    $ E3 : B \rightarrow S$
     
  2. $ E1 : S \rightarrow aAbB, S \rightarrow \varepsilon$
    $ E2 : S \rightarrow bAaB, S \rightarrow \varepsilon$
    $ E3 : S \rightarrow \varepsilon$
     
  3. $ E1 : S \rightarrow aAbB, S \rightarrow \varepsilon$
    $ E2 : S \rightarrow bAaB, S \rightarrow \varepsilon$
    $ E3 : B \rightarrow S$
     
  4. $ E1 : A \rightarrow S, S \rightarrow \varepsilon$
    $ E2 : B \rightarrow S, S \rightarrow \varepsilon$
    $ E3 : B \rightarrow S$
edited by

3 Answers

Best answer
44 votes
44 votes

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.

edited by
6 votes
6 votes

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.

1 votes
1 votes
Ans C

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

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

Follow (B)={\$,a,b}
edited by
Answer:

Related questions

29 votes
29 votes
3 answers
1
48 votes
48 votes
4 answers
4
go_editor asked Apr 21, 2016
13,583 views
Consider the following relations $A, B$ and $C:$ $$\overset{\textbf{A}}{\begin{array}{|c|c|c|}\hline\\\textbf{Id}& \textbf{Name}& \textbf{Age} \\\hline12& \text{A...