1. Write grammars for:

a. aⁿb²ⁿ

b. abⁿa :n is multiple of 3

c. aⁿ b aⁿ⁺¹

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 your grammar. Are there any conflicts? Is the grammar LL(1)?

---------------------------------------------------------------------------------------------

5. Given the grammar

S --> aS | SB | d

B --> Bb | c

Show that this grammar is ambiguous by exhibiting two different parse trees for the derivation of the string aadccb.

------------------------------------------------------------------------------------------------------------

6. For the following grammar

A --> aQ

Q --> bQ |

What are

(a) FIRST(Q)

(b) FOLLOW(Q)

----------------------------------------------------------------------------------------------------

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