Assignments / #3

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

Due Wednesday, 10/21/98

  1. If you haven't formed a group yet, please do so as soon as possible. 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.

    You are not absolutely required to join a group, but it is strongly encouraged. Communicating with a partner will help you both learn more, probably with less effort. If you feel you must work alone, also please send me email by Wednesday to let me know, and explain why.

  2. 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).

  3. 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.

  4. 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 AST or the 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") are best enforced by the grammar and which are best enforced during semantic analysis (or later).

    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.