Retro school children University of Washington Department of Computer Science & Engineering
 CSE 401: Assignment 2, Due Friday 4/13/01
  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, 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 are:

    See the project description for full details.