Consider the grammar with the following rules (capital letters are nonterminals and S is the start nonterminal):

S -> AB | a

A -> CD

B -> bAB |

C-> dSd | c

D -> cCD |

a) Determine each of the sets:

i) FIRST(AB)

ii) FIRST(CD)

iii) FOLLOW(S)

iv) FOLLOW(A)

v) FOLLOW(B)

vi. FOLLOW(C)

vii. FOLLOW(D)

For each element z belonging to a set FOLLOW(X) (X {S,A,B,C,D}) give a derivation starting from S where z occurs directly after X. (Similar sample derivations are not required for FIRST-sets.)

b) Does the grammar allow use of recursive-descent parsing? Justify your answer using your answers from part a.