The GATE Grind

GATE 2019 CS – Question 29

Compiler Design · Parsing and Syntax Analysis · 1 mark · Numerical answer

Consider the grammar given below:

S → Aa

A → BD

B → b | ε

D → d | ε

Let a, b, d, and $\char36$ be indexed as follows:

abd$\char36$
3210

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**.

More Parsing and Syntax Analysis questions

All Parsing and Syntax Analysis questions →