----------------------------------------------------------------------

CSE 401 Autumn 2001 (Henry)

[Home] [Admin] [Details] [Help] [Other]

Assignment 4 (LL parsing and EBNF)

($Revision: 1.5 $)

----------------------------------------------------------------------

Due Monday, October 29, 2001

  1. (Individually, no turn in) Read ASU sections 4.1-4.4, except pages 173-174 ("verifying the language generated by the grammar).

  2. (Individually, paper turn in)
    • ASU problem 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).

  3. (Individually, paper turn in) 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. Turn these first and follow sets in on one or more sheets of paper.

  4. (As a group, paper turn in) Extend the EBNF description of the original PL/0 syntactic structure to include the features of the extended PL/0 language. Hand in your revised description on one or more sheets of paper.

    You will be given the solution set grammar on the turn-in day, so don't start implementing the AST data structures or the parser until you get the standard grammar.)

    See also the project description.

  5. (As a group, no turn in) Select one of your group member's scanner implementation from the previous assignment, and commit to using that as the basis for the rest of the quarter.

  6. (As a group, no turn in) Correct any syntactic or semantic deficiencies that the reference compiler has found in your test cases. Extend the test cases as you see fit, based on our "fixes" to the description, your gradual enlightenment, and as you perceive your needs. This will be an ongoing job.

  7. (As a group, no turn in) Meet with your group for several hours, and do a code walk through (a group reading and discussion) of the declarations and implementation for the parser and AST classes in the basic PL/0 compiler. Keep in mind what you will have to change when you start to implement the parser for the extended PL/0 syntax for next week's assignment.

----------------------------------------------------------------------

401admin at cs.washington.edu