next up previous
Next: Exercise 3. Up: Final-13-04-2004 Previous: Exercise 1.

Exercise 2.

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 $\displaystyle \longmapsto$ $\displaystyle \alpha$B$\displaystyle \beta$ then $\displaystyle \mbox{{\sc FOLLOW}($B$)}$ : = $\displaystyle \mbox{{\sc FIRST}(${\beta}$)}$ $\displaystyle \setminus$ {$\displaystyle \varepsilon$$\displaystyle \cup$  $\displaystyle \mbox{{\sc FOLLOW}($B$)}$
if A $\displaystyle \longmapsto$ $\displaystyle \alpha$B then $\displaystyle \mbox{{\sc FOLLOW}($B$)}$ : = $\displaystyle \mbox{{\sc FOLLOW}($B$)}$  $\displaystyle \cup$  $\displaystyle \mbox{{\sc FOLLOW}($A$)}$
if $\displaystyle \left\{\vphantom{ \begin{array}{l} A \longmapsto {\alpha} B {\beta} \\  {\beta} \stackrel{\ast}{\Longrightarrow} {\varepsilon} \end{array} }\right.$$\displaystyle \begin{array}{l} A \longmapsto {\alpha} B {\beta} \\  {\beta} \stackrel{\ast}{\Longrightarrow} {\varepsilon} \end{array}$ then $\displaystyle \mbox{{\sc FOLLOW}($B$)}$ : = $\displaystyle \mbox{{\sc FOLLOW}($B$)}$  $\displaystyle \cup$  $\displaystyle \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 2  



next up previous
Next: Exercise 3. Up: Final-13-04-2004 Previous: Exercise 1.
Marc Moreno Maza
2004-12-02