Introduction to Compilers

Spring 2002

**due: **Monday, March 11, in class

- 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

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

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