GATE CSE 2012 | Question: 52

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|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 FIRST and FOLLOW sets for the non-terminals $A$ and $B$ are

• A. $ \text{FIRST}(A) = \{a, b, \varepsilon\} =\text{FIRST}(B) $
  $ \text{FOLLOW}(A) = \{a, b\} $
  $ \text{FOLLOW}(B) = \{a, b, \$\} $
   
• B. $ \text{FIRST}(A) = \{a, b, \$\} $
  $ \text{FIRST}(B) = \{a, b, \varepsilon\} $
  $ \text{FOLLOW}(A) = \{a, b\} $
  $ \text{FOLLOW}(B) = \{\$\} $
   
• C. $ \text{FIRST}(A) = \{a, b, \varepsilon\} =\text{FIRST}(B) $
  $ \text{FOLLOW}(A) =\{a, b\} $
  $ \text{FOLLOW}(B) = \varnothing $
   
• D. $ \text{FIRST}(A) = \{a, b\} = \text{FIRST}(B) $
  $ \text{FOLLOW}(A) = \{a, b\} $
  $ \text{FOLLOW}(B) =\{a, b\} $

Comments

Can solve by eliminating options if we know the following-

First set can contain  (Follow set never contains  )

Follow set of start symbol S always contains \$ (and First set never contains $)

Thus,

• option B, First(A) contains $, hence eliminated.
• option C, Follow(B) = Follow(S) and as S is start symbol, hence, follow(B) should contain atleast  \$
• option D, as Follow(B)= Follow(S), it should contain \$

Hence, Answer is option A.

---

Why Follow(B)= Follow(S)?

It is a Rule to find follow.

Reference - Dragon Book.

Answer 1

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

So, the answer to question 52 is option A.

Comments

How can we now that the production to entered in E3 is B=>S and not B=>∊ ? Precisely, how do we decide to be inser B=>∊ versus some other production. For S at M[S, $], the production entered is S=>∊. What is the difference?

---

S can directly derive epsilon because S-->epsilon is a production that’s why we entered S-->epsilon in E1 and E2 .but we don’t have a production B--->epsilon. but since epsilon belongs to FIRST(B) so we find FOLLOW(B) which contains epsilon and we add B-->S in E3.

---

We have production rule A -> S, so shouldnt follow(A) = follow(S)? So follow(A) = {a,b,$}.

---

@Aviral_Tyagi when you say follow of a non-terminal the terminal that follows a non-terminal whose follow you need to find should be somewhere in the RHS of a production rule. In A->S follow of A can't be calculated as A is not in the RHS of the production rule.

Answer 2

Q 52 : ans is A.

first we can easly find.

follow of A = {a,b}, all symbols appeared after A in RHS

follow of B = {a,b,\$}, as B is at the end in RHS, follow(B) = follow (S) and S is also at the end in RHS so follow(S) = follow(A) = {a,b} and S is start symbol, so its follow contains \$ also.

hence, follow(B) = {a,b,\$}

Q 53.

ans is C.

Answer 3

Q52 answer - D

Q53 answer - A