UMBC CMSC431, Compiler Design Principles, Fall 2009

Homework Assignments

Homework 1, Due Thursday 10/08

Show your work for these problems.

1. Exercise 3.7.1, part b, page 166.

2. Exercise 3.7.2, part b, page 166.
   Note: Show the contents of the set S after line 4 of Algorithm 3.22 for each iteration of the loop.

3. Exercise 3.7.3, part d, page 166.

4. Exercise 3.9.2, part d, page 186.
   Note: Show the values of nullable, firstpos, lastpos for each node in the syntax tree and show the values of followpos for each position in the syntax tree.

5. Exercise 3.9.4, part b, page 186.

Homework 2, Due Thursday 10/22

1. Exercise 4.2.2, part b, pages 206–207.

2. Exercise 4.3.1, part c, page 216.

3. Exercise 4.3.3, page 217.

4. Exercise 4.4.3, page 231.

5. [Adapted from Modern Compiler Design by Grune et al, Wiley 2000.]
   Compute FIRST and FOLLOW for each nonterminal in the grammar below:

   S  →  A B C
   A  →  a A  |  C
   B  →  b  |  ε
   C  →  c
   

   Then, show the parse table produced by Algorithm 4.31 (page 224).

Homework 3, Due Thursday 11/05

1. Exercise 4.6.2, page 258.

2. Exercise 4.6.3, page 258.

3. Exercise 4.6.5, page 258.

4. Exercise 4.6.6, page 258.

Homework 4, Due Thursday 11/19

1. Exercise 4.7.1, page 277.

2. Exercise 4.7.4, page 278.

3. Exercise 4.7.5, page 278.

Homework 5, Due Thursday 12/10

1. Exercise 9.1.1, parts a – e, page 596.

2. Exercise 9.1.4, page 596.

3. Exercise 9.2.3, page 615.