Lab 3 (second part) - Type checker

In this lab we will write a type checker for our tiger compiler. The type checker is responsible for the following tasks:

For example, after running the typer, the expression

let var a := 3
    var b := a
  let var c := a + b in print_int(c) end

will be typed as void and will be displayed as

function main(): int =
      var a: int := 3
      var b: int := a
        var c: int := (a + b)


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.

Adding the type checker file and command-line argument

The type checker is a visitor similar to the binder. It must be located in src/ast/type_checker.hh (and src/ast/ 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
  -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 must be TypeChecker and be declared in namespace ast::type_checker.

Implementing the type checker

The type checker must perform the following operations:

Note that in some cases you might analyze a FunCall targeting a FunDecl which has not yet been analyzed. It may happen in two cases:

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

Note on automated test results

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.

Optional: implementing the escaper

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 get_escaping_decls() vector.

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:

For interoperability purpose with later labs, the class of the escaper must be Escaper and be declared in namespace ast::escaper.