CSE 401: Compilers

Assignments / #3

Due Wednesday, 4/22/98

Starting with HW#4 (to be distributed early next week), you'll be free to work in groups of 2 or 3 on the programming project portions of assignments. If you haven't formed a group yet, please do so ASAP. Then, one member of each group should send me the names and unix login names of your group members BY WEDNESDAY. I need to have the lab set up some unix accounting stuff so you can share files, so I need groups fixed SOON. (Although I think it's beneficial, you are not required to join a group. If you prefer to work alone, also please send me email by Wednesday to let me know.)
In the this problem, follow the algorithms in the book literally; don't "optimize" the results - that's more error-prone (and makes it harder to grade).
- Text, 4.3(a)
- Eliminate left recursion from this grammar using the method from section 4.3.
- Construct a parse tree for the same sentence as in 4.3(a) for the modified grammar.
- Compute the FIRST and FOLLOW sets (Section 4.4) for this grammar.
- Build the LL(1) parsing table for this grammar (Algorithm 4.4).
Compute the FIRST and FOLLOW sets for the PL/0 original BNF. Please list these sets in the same order as given on the original BNF page.
Extend the BNF description of the PL/0 syntactic structure to include the new language features, and hand in your revised description (a sheet of paper). (You'll be given the solution set grammar on the turn-in day, so don't start implementing the AST or the parsing code until you get it.)
In summary, the new language features are:
- if/then/else
- for loops
- break statements
- boolean types
- and/or operators
- constant expressions
- arrays & array indexing
- call by reference
- functions & function calls with results.
See the project description for full details.

401admin@cs.washington.edu (Last modified: 04/28/98)