Homework:

1. Write grammars for:

a. a n b 2n

b. ab n a :n is multiple of 3

c. a n b a n+1

d . C proc def: id ( param_list )

where a param_list is 0 or more declarations of form id ;

2 . Consider the grammar:

1,2: S -- > aAbB | Bc

3,4: A -- > aAa | a

5,6,7,8: B -- > Bb | Ab | cC | AC

9: C -- > c

a. Find the FIRST and FOLLOW sets for S, A, B, C

b. This grammar is not suitable for recursive descent. Why not?

c. Rewrite productions 3 & 4 to eliminate the common prefix problem.

3 . Consider the grammar:

1. S -- > AcB

2,3. A -- > Aa | caa

4,5. B -- > bB |

a. Find the FIRST and FOLLOW sets for S,A,B.

b. Eliminate the left recursion.

c. Now, is the grammar suitable for recursive descent?

4 . Consider the grammar:

1,2. S -- > ( L ) | a

3,4 L -- > L , S | S

a. Calculate FIRST and FOLLOW for the grammar as written

b. Eliminate the left recursion. Calculate FIRST & FOLLOW for the new grammar.

c. Build the LL(1) tables from yo ur grammar . Are there any conflicts? Is the grammar LL(1)?

5. Given the grammar

S - - > aS | SB | d

B - - > Bb | c

Show that this gram mar is ambiguous by exhibiting two different parse tree s for the derivation of the string aadccb.

6. For the following grammar

A -- > aQ

Q - - > bQ |

W hat are

(a) FIRST(Q)

(b) FOLLOW(Q)

7. F ind the FIRST and FOLLOW sets for the grammar

S - - > ABC

A - - > a | Cb |

B - - > c | dA |

C - - > e | f

8. Suppose we expand our expression grammar to include assignment statements:

S - - > i := E

E - - > TQ

Q - - > +TQ | - TQ |

T - - > FR

R - - > *FR | /FR |

F - - > ( E ) | i

Construct a predictive - parsing table for this grammar.