CSE 401 Compilers Class (Fall '99)

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

Assignments / #3


Due Wednesday, 10/20/99

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

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

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

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


cse401-webmaster@cs.washington.edu (Last modified: 10/15/99)