Exercise 3.

Consider the following grammar G with terminals a, b, c, d and nonterminals S, A, B, C.

S	$\longmapsto$	C A
A	$\longmapsto$	a B A  |  $\varepsilon$
B	$\longmapsto$	b B  |  C d
C	$\longmapsto$	c C  |  $\varepsilon$

We recall the rules for the computation of the FOLLOW set of each nonterminal.

if	A $$\longmapsto$$ $$\alpha$$B$$\beta$$	then	$$\mbox{{\sc FOLLOW}($B$)}$$ : = $$\mbox{{\sc FIRST}(${\beta}$)}$$ $$\setminus$$ {$$\varepsilon$$}  $$\cup$$  $$\mbox{{\sc FOLLOW}($B$)}$$
if	A $$\longmapsto$$ $$\alpha$$B	then	$$\mbox{{\sc FOLLOW}($B$)}$$ : = $$\mbox{{\sc FOLLOW}($B$)}$$  $$\cup$$  $$\mbox{{\sc FOLLOW}($A$)}$$
if	$$\left\{\vphantom{ \begin{array}{l} A \longmapsto {\alpha} B {\beta} \\ {\beta} \stackrel{\ast}{\Longrightarrow} {\varepsilon} \end{array} }\right.$$$$\begin{array}{l} A \longmapsto {\alpha} B {\beta} \\ {\beta} \stackrel{\ast}{\Longrightarrow} {\varepsilon} \end{array}$$	then	$$\mbox{{\sc FOLLOW}($B$)}$$ : = $$\mbox{{\sc FOLLOW}($B$)}$$  $$\cup$$  $$\mbox{{\sc FOLLOW}($A$)}$$

Recall also that if $ denotes the end-of-line symbol and if S is the start symbol of the grammar (as it is the case above) then we have $ $\in$ FOLLOW(S). Give the parsing table of G (for the non-recursive implementation of predictive parsing).

Answer 3