Type Checking Tiger

Due 3/23/99

For this assignment you need to write a module that type checkes a tiger program given its abstract syntax tree. You may do so by either adding typechecking methods to the Absyn classes themselfs (as I did for my toy language), or by writing a function that uses "instanceof" to determine how to type check specific kinds of expressions. An example of how to do it this way can be found in Absyn.Print - the pretty printer for Abysn trees.

For the Symbol table, you can either use a stack of stacks as I have, or use Appel's supplied code and suggestions (at your own risk). Appel uses a hash table. You should consider using a hash table anyway.

To represent the types of Tiger (unlike my toy language where types are just strings, tiger types can be complex), use Appel's tiger/chap5/Types package, which defines a class hierarchy for type expressions. I suggest you consider using my additions to that package (FUNC.java and tlist.java). These define a list of types, and the type for functions, so that you can associate a Type object with function symbols in tiger.

For this assignment, I'll allow you to keep a GLOBAL list of type names (or "type id's"). This global list will be the "type-side" equivalent of the symbol table, except you need not respect scope. Every time a tiger type declaration such as "type intarry = array of int" is encountered, you can just simply add "intarry" (as a Name Type) into your global list.



Another important part of this assignment is to check for errors that were overlooked in the parsing phase of the compiler. Specifically, you need to catch expressions such as "ID [exp] of exp" where "ID" is not a "type-id" - ie., something that does not appear in your global list of type names. Another important error to catch here include passing a wrong number of parameters to a function. Your type checker should return helpful messages concerning types. Since tiger has only two built-in types (int and string), you do not need to worry about overloading. Don't worry about mutually recursive types (unless you want to).

Here are the new classes for my toy language. It includes classses for the symbol tables, as well as abstract classes that includes type checking methods.

A few other things to keep in mind: In Tiger there's no distinction (syntactically) between statements and expressions. Statements should have type "void". Be careful: don't return "null" - return a VOID Type! Read chapter 5 selectively to understand the typing rules of Tiger. Note espeically the material on page 117.