CSE 401,  Sp '04:  Assignment #2, Due in class Wed., 4/14/04
 CSE Home About Us Search Contact Info

### Individual homework

#1 should be done and turned in individually, not as a group.

1. 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).
1. Text, 4.3(a)
2. Eliminate left recursion from this grammar using the method from section 4.3.
3. Construct a parse tree for the same sentence as in 4.3(a) for the modified grammar.
4. Compute the FIRST and FOLLOW sets (Section 4.4) for the modified grammar.
5. Build the LL(1) parsing table for the modified grammar (Algorithm 4.4).
6. Is the modified grammar LL(1)? Why or why not?

### Project

If you have formed a group, the following may be done by your group; turn in only one solution per group.

1. For the PL/0 original BNF,
• Compute the FIRST set for the right hand side of each rule. Please list these sets in the same order as given on the original BNF page.
• Compute the FOLLOW set for each variable (left hand side). Again, please list in order.
• Is the grammer LL(1)? Why or why not? If not, outline one place in the base compiler where it deviates from strict adherence to the base grammar in order to avoid non-LL(1)-ness and sketch how it works.
Notes: (i) A rule like A -> B | C has two right hand sides. (ii) The use of square brackets and curley braces in rules is not strictly allowed in a context-free grammer, but in the given PL/0 grammar it generally doesn't effect the FIRST/FOLLOW sets. One exception is a rule like A -> { B ; }, where FIRST(A) equals FIRST(B) plus epsilon, perhaps plus ";", and similarly for FOLLOW.

2. 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 a solution set grammar on the turn-in day, so don't start implementing the most complex parts of the AST or parsing code until you get it.)

You will need to give some thought to which language features (e.g., "variables must be declared", or "break may occur only in a loop", or "every for loop must have an end token") are best enforced by the grammar and which are best enforced during semantic analysis (or later). Write a few sentences to document these major design decisions, i.e., explain what you decided to do and sketch why. Turn this in with your revised BNF.

In summary, the new language features that affect syntax include some new statements like for loops, new Boolean types and operators, arrays, etc.; see the project description for full details.

 Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to cse401-webmaster at cs.washington.edu]