In this lab we will write a type checker for our tiger compiler. The type checker is responsible for the following tasks:
- assigning types to expressions and declarations lacking them;
- checking types consistency.
For example, after running the typer, the expression
let var a := 3 var b := a in let var c := a + b in print_int(c) end end
will be typed as void and will be displayed as
function main(): int = ( let var a: int := 3 var b: int := a in let var c: int := (a + b) in print_int(c) end end; 0 )
Note that main always return an int: its return value is used by the operating system as the program exit code (0 meaning that everything worked fine – indeed if we reach the end of main, we had no error).
You will work in the same directory as the first part of lab 3. You do not need to retrieve and unpack an archive for this part.
You do not need to do any particular setup.
The type checker is a visitor similar to the binder. It must be
if needed, which will probably the case) in order to be picked up
by the automated grader.
You must add a
--type/-t command to the driver which will
run your AST tree through the type checker. Once you have added
this command like argument, the
--help output should look like:
$ src/driver/dtiger --help Options: -h [ --help ] describe arguments --dump-ast dump the parsed AST -b [ --bind ] run the binder on the parsed AST -t [ --type ] run the type checker on the parsed AST --trace-parser enable parser traces --trace-lexer enable lexer traces -v [ --verbose ] be verbose --input-file arg input Tiger file
The binder must be run before the type checker even if
the user does not explicitly give
--bind on the command line,
as it makes no sense to type check the tree if it has not been decorated.
Also, in order to see the results of the type checker, the dump of the AST (if requested) must take place after the type checker has run.
For interoperability purpose with later labs, the class of the type checker
TypeChecker and be declared in namespace
The type checker must perform the following operations:
StringLiteralnodes are given respectively the
Sequencenodes have the same type as their last expression if they have one, otherwise they are
IfThenElsenodes must have type-compatible branches, whose type become their type.
Letexpressions have the same type as their last expression if they have one, otherwise they are
VarDeclnodes without an explicit type (in the
type_namefield) take their type from their expression. This type cannot be
t_voidsince a variable is either an integer or a string.
VarDeclnodes with an explicit type given in the source must check that the expression (if any) is compatible with this type, which will become the type of the node.
BinaryOperatornodes must check that their arguments have types compatible with the operation and with each other, and set the resulting type.
Identifiernodes inherit the type of their declaration.
Assignnodes must check the validity of the assignment and be
WhileLoopnodes must have integer conditions and a body of type
t_void, and are themselves
ForLoopnodes must have integer bounds, an integral index, and a body of type
t_void, and are themselves
FunDeclnodes have either an explicit type (in the
type_namefield) which matches the type of their expression, or no explicit type in which case their expression and themselves must be
FunCallnodes inherit the type of their declaration. The type checker also ensures that number of arguments matches the number of parameters, and that they all have the right type.
Note that in some cases you might analyze a
FunDecl which has not yet been analyzed. It may happen in two
- you are calling a primitive function, and primitives are not located in the tree;
- you are calling a function defined after the current one in the same declarative block (mutually recursive functions).
In those cases, you might note that the target has not been analyzed
because its type is still
t_undef. When this happens, you should
recurse and analyze the declaration of your target.
It also mean that before analyzing a
FunDecl you must make sure
that it has not been analyzed yet, as it may have been analyzed
during the processing of a
FunCall in the second case described
above. In this case, the visit of the
FunDecl should not have
any effect since it has been done already.
Since by default the binder accepts anything without checking the types consistency, some type checker tests may appear to pass very early. This is due to the fact that some constructs are valid and will not be rejected. However, as you add more type checking, some tests that were passing may start to fail because you are rejecting valid constructs.
This part will not be tested automatically, but must be implemented if you want to be able to use your own code in the next lab.
You need to build yet another visitor, the escaper, which will run right
after the binder. Its role is, for every
VarDecl which escapes (this flag
has already been set by the binder), to add it to the current function
This is necessary so that when we build the frames for the functions, we can put the escaping variables in the frame structure (since they might be accessed from outside the function and need to be stored in memory), while other variables may be stored separately and put into registers as they will never be read or modified outside the function by nested functions.
So your work is simple:
- When visiting a
FunDeclnode, save the current function, set the current function to the one you are visiting, recurse, then restore the current function.
- When visiting a
VarDeclnode, if it escapes, add it to the list of escaping declarations for the current functions (and recurse into its expression if any).
- For every other node, recurse in case you encounter a
VarDeclsomewhere lower in the tree.
For interoperability purpose with later labs, the class of the escaper
Escaper and be declared in namespace