GATE 2019 CS – Question 29
Consider the grammar given below:
S → Aa
A → BD
B → b | ε
D → d | ε
Let a, b, d, and $\char36$ be indexed as follows:
| a | b | d | $\char36$ |
|---|---|---|---|
| 3 | 2 | 1 | 0 |
Compute the FOLLOW set of the non-terminal B and write the index values for the symbols in the FOLLOW set in the descending order. (For example, if the FOLLOW set is {a, b, d, $\char36$}, then the answer should be 3210.)
Answer: ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 31
Explanation
Grammar: $S\to Aa$, $A\to BD$, $B\to b\mid\varepsilon$, $D\to d\mid\varepsilon$.
$B$ appears in $A\to BD$, followed by $D$. So $FOLLOW(B)\supseteq FIRST(D)\setminus\{\varepsilon\}=\{d\}$. Since $D$ can derive $\varepsilon$, whatever follows $A$ also follows $B$: $FOLLOW(B)\supseteq FOLLOW(A)$. In $S\to Aa$, $FOLLOW(A)=\{a\}$.
$FOLLOW(B)=\{d,a\}$. With the indices $a=3,\ d=1$, in descending order: **31**.