CSE 401 Compilers Class

Details / Midterm Solution


Here's my very terse outline of solutions to selected midterm problems:
  1. Clarity, simplicity, modularity.
  2. In addition to the above, efficiency:  DFA-based scanner is faster than CFL parser-based scanner for the same language.  Also, the grammar would be significantly more complicated; e.g., allowing whitespace everywhere.
  3. -- Context-free but not regular: balanced parens or other nested structures like begin/end blocks, nested loops, etc.  Not sufficient to say "recursion" - you needed to give an example like these where recursion gives something extra.

  4. -- Not context-free, but compile-time checkable: matching names to declarations, type checking.  (Checking for break only in loop, as in PL/0 could be done with CFG, but is awkward.)

  5. -- RE: "(B | \A)*", where A denotes the set of all allowable characters, B denotes A minus double quote and backslash, and ()|* are the usual meta-characters.

  6. -- DFA: kinda hard to draw in HTML; something like:
      >(1) --"--> (2) --"--> ((3))
    with an edge from 2 to 2 labeled B, and one from 2 to 4 labeled backslash, and from 4 back to 2 labeled A.

  7. (e)
     ast* procedure parseTprime() {
          if scanner->peek("^") {
              return parseT();
          } else if scanner->peek(")") {
              return nil; 
          } else abort();

  8. xi = xi for all i under both definitions.  In addition:
    -- Name equivalent: x1 = x2, x3 = x4;
    -- Structurally equivalent: x1 = x2 = x3 = x4 = x5.
  9. Abstract Syntax Tree:
           / \
          /   \
         i     .
              / \
             /   \
            ->    x
           /  \
          /    \
        barp    y
    Typecheck as usual traverses the tree, evaluating bottom up.  TC for "->" verifies that left subtree has type "pointer_to_struct", and that right child is an ID node whose string name is declared in the symbol table for that struct; result type is the type of that field, foo_t in this case.  TC for "." is similar: left subtree must be a struct type, right child must be a field name therein; result type int.  TC for "=" checks that left subtree is lvalue, and that right is of same type.


401admin@cs.washington.edu (Last modified: 05/27/98)