CS 412/413
Introduction to Compilers and Translators
Spring 2000
Cornell University

Homework 3: Semantic Analysis and Intermediate Code

due: Friday, February 25, in class

  1. Suppose you wanted to compute the number of nodes in an abstract syntax tree. Show how this functionality can be implemented straightforwardly in the visitor methodology of Lecture 8 by defining a simple subclass of NodeVisitor and adding one method to the Node class that is the superclass of all AST node classes.
  2. Iota static semantics
    1. The rule for a sequence starting with a variable declaration takes the following form when there is no initialization expression. Why does the first premise contain T1 instead of T?

      A ` id : T    : T1
      A + {id : T}` (S2; ...; Sn) : Tn
      A ` (id : T; S2; ...; Sn) : Tn

    2. Environments are constructed in the static semantics by an binary operation A + A' that is undefined if the second environment (A') duplicates any entries from the first (A). Why is this? Give an example of some code that is not allowed by the given semantics, but would be if the second environment overrode the first.

    3. Suppose we extended the static semantics with the following rule:

      A ` E  : none
      A ` E  : T

      Give an example of an expression or statement that is well-typed using the extended semantics but is not under the given semantics, and draw its proof tree. Is this static semantics sound -- that is, can this example result in a run-time type error? Argue briefly.

  3. Suppose Iota were extended with tuple types of the following form. A tuple type is written as a sequence of types in parentheses. For example, the declaration x:(int, bool, string) creates a variable x containing a 3-tuple. The elements of a tuple are immutable and cannot be changed, although x could be assigned to an entirely new value of this tuple type. The individual elements of the tuple can be accessed in a manner similar to array elements. For example, the
    expression x[0] has type int, x[1] has type bool, and x[2] has type string. Tuples are unlike arrays in that the index expression must be a constant, and the elements cannot be assigned to.
    1. Show how to extend the static semantics of Iota to include tuple types and the tuple element access expression x[n].
    2. Draw the proof tree for the judgment { a: (int, int) } ` a[0] + a[1] : int
    3. Syntactically, the tuple element access expression looks like an array element access expression. Will this create problems for type checking? Explain briefly.
    4. Can tuples be allocated on the stack? Explain.
  4. Appel, 7.2 (a, c, d, e, i, j)