GATE Overflow Test Series | Compiler Design | Test 1 | Question: 16

Question

Consider the grammar given below:

• $S \rightarrow ABA$
• $A \rightarrow Bc \mid dA \mid \epsilon $
• $B \rightarrow eA$

Let $a,b,c$ and $\$$ be indexed as follows:
$$\begin{array}{|c|c|c|c|c|} \hline
c & d & e & \$
\\\hline
2 & 3 & 5 & 7
\\\hline
\end{array}$$
If $\alpha$ is the index values for the symbols in the FOLLOW set of the non-terminal $A$, $\beta$ is the index values for the symbols in the FOLLOW set of the non-terminal $B$ and $\gamma$ is the index values for the symbols in the FOLLOW set of the non-terminal $S$, all in their ascending orders, the value of $\alpha - \beta + \gamma =$ _______

(For example, if the FOLLOW set is $(c,d,e,\$)$ , then the answer should be $2357$)

Comments

Can anyone explain why Follow of A have c and d in it?

 

EDIT – I figured out the reason. I missed something initially.

Answer 1

Given that the grammar:

• $S \rightarrow ABA$
• $A \rightarrow Bc \mid dA \mid \epsilon $
• $B \rightarrow eA$

Now, we can calculate the FIRST and FOLLOW sets:

• $FIRST(S) = \{d,e\}$
• $FIRST(A) = \{d,e,\epsilon\}$
• $FIRST(B) = \{e\}$
• $FOLLOW(S) = \{\$\}$
• $FOLLOW(A) = \{\$,c,d,e\}$
• $FOLLOW(B) = \{\$,c,d,e\}$

$\textbf{For A:}$ Follow set in ascending order:

$$\begin{array}{|c|c|c|c|c|} \hline
 c & d & e & \$ \\\hline
 2 & 3 & 5 & 7 \\\hline
\end{array}$$

$\therefore \alpha = 2357$

$\textbf{For B:}$ Follow set in ascending order:
$$\begin{array}{|c|c|c|c|c|} \hline
 c & d & e & \$ \\\hline
 2 & 3 & 5 & 7 \\\hline
\end{array}$$

$\therefore \beta = 2357$

$\textbf{For S:}$ Follow set in ascending order:
$$\begin{array}{|c|c|c|c|c|} \hline
  \$ \\\hline
  7 \\\hline
\end{array}$$
$\therefore \gamma = 7$

Now, $\alpha - \beta + \gamma =  7.$

So, the correct answer is $7.$

Comments

yeah it is correct

---

follow A  explain kardo sir

---

@mayank pathak 

Following is the detailed explanation. Hope it might help other aspirants as well

$FOLLOW(S)$ = { \$ } ( $\because$ S is the start symbol )

$FOLLOW(A)$ includes union of

• { e } ( $\because$ S → ABA and FIRST(B) = {e} )
   
• { \$ } ( $\because$ S → ABA and FOLLOW(S) ={$} )
   
• $FOLLOW(B)$ ( $\because$ B → eA )

$FOLLOW(B)$ includes union of

• { c } ( $\because$ A → Bc )
   
• { d ,e } ( $\because$ S→ ABA and FIRST(A) includes { d ,e } ) 
   
• $FOLLOW(A)$ ( $\because$ S→ ABA and FIRST(A) includes $\epsilon$ ) 
   

$FOLLOW(A)$ = { \$, e } $\cup$ $FOLLOW(B)$ = { c, d, e, \$ }

$FOLLOW(B)$ = { c,d,e } $\cup$ $FOLLOW(A)$ = { c, d, e, \$ }