CS 412/413
Introduction to Compilers
Spring 2002

Homework 3: Semantic Analysis and IR Generation

due: Monday, March 11, in class

1. For each of the following IC statements or expressions, state whether it is well-typed in some type context and if so, what its type is. If it is well-typed, give a type context in which it has a type and provide the corresponding typing derivation. If it is not well-typed in any type context, show why. 
   
   a. lengthof(new int[2]) + 2 
b. int a = 2 + (return 2);
c. while (x < lengthof "abc" /\ y == true) x = y; 
d. (x == L) \/ (("foo" + L) == "fool") 
e. f(s)[lengthof s] = x + 2



2. Consider the following language consisting of boolean expressions:
   
   E -> E or E | E and E | not E | E => E | E <=> E | (E) | id

In the above productions, => is the implication operator, <=>  is the equivalence operator, and id is the terminal representing identifiers. 
   
   a) Write a syntax-directed definition which translates these boolean expressions into equivalent boolean expressions consisting only of 'and' and 'not' operators.
b) Write the translation to low-level intermediate representation for each of these above productions. Each translation rule must define [E, L1, L2], which is the low-level  IR code for E which branches to L1 if E evaluates to true and to L2 if E evaluates to false.
   


3. Consider the a simple language whose statements S, expressions E, and types T are defined by the following grammar:

E -> E + E  |  E * E  |  id  | num 
S -> T id  | id = E | S , S  | if (E) S | while (E) S 
T -> int | bool

Here, id represents identifiers and num represents integer numbers. Suppose we want to extend this language with support for pointers. For this, we would add the following productions:

E -> deref E | addressof E 
S -> deref E = E
T -> pointer(T)

For an pointer expression E, deref E returns the value of the location where E points to. The addressof E expression returns the address of its operand E. The statement deref E1 = E2 is a store statement: it updates the location where E1 points to. The type pointer(T) is the pointer type which describe addresses to locations of type T.

a) Write the type-checking inference rules for the expressions and statements in this language;
b) Write the translation to low-level intermediate representation for the store statement deref E = E and for expressions deref E and addressof E.