Honors Compilers
HW 2 - due Tues. Mar. 24

Syntax Analysis

1.  Describe the language generated by the following grammar and
show that it is ambigious:

S -> AB | DC
A -> aA | a
B -> bBc | bc
C -> cC | c
D -> aDb | ab

2.  In class we defined the set of nonterminals in a CF grammar P that 
derive the empty string with the following specification: 

min s: s contains {x: x->rhs in P | {y: y in rhs} subset s}

Use our fixed point theory, and the dominated convergence theorem in
particular to derive a simple algorithm to compute this specification.
Show how to improve your algorithm so that it runs in linear time with
respect to the grammar size.  Show your analysis.

3.  Problem 13 in WM

4.  Problem 19 in WM

5.  Problem 20 in WM

6.  Problem 21 in WM

7.  Problem 22 in WM

8.  Problem 23 in WM

9.  Problem 24 in WM

10.  Problem 25 in WM