Semantic analysis

Description

I have provided a parser for a subset of tiger that includes

exp:
    lvalue
    nil
    int
    string
    exp + exp
    exp - exp
    exp * exp
    exp / exp
    lvalue := exp
    let declist in exps end

lvalue:
    id

declist:
    dec
    dec declist

dec: 
    type typeid = typeid
    var id : typeid := exp

exps:
    exp ; exps

Part 1

Your assignment is to write a set of mutually recursive functions that type check the abstract syntax tree generated by the parser. Chapter 5 of the textbook describes the functions. The sample code provides a few of the functions you should use.

Programs that typecheck correctly should return unit. Programs that fail should return an appropriate error message with ErrorMsg.error.

Example code

The example code is in the github repository. Look at the tiger/semant.sml file. I have already implemented typechecking IntExp, StringExp, and OpExp, following example code in the book. You have to implement everything else. Ask questions on piazza. This is a tough assignment, don't try to do it all at the end.

The following simple program sum.tig parses and passes semantic analysis:

5 + 3

Here's how to check it:

- CM.make "sources.cm";
[scanning sources.cm]
[New bindings added.]
val it = true : bool
- val sumprog = Parse.parse "sum.tig";
val sumprog = OpExp {left=IntExp 5,oper=PlusOp,pos=4,right=IntExp 3}
  : Absyn.exp
- Semant.transProg sumprog;
val it = () : unit

Here's a broken program with let (tiger/let.tig):

let
 type pos = int
 var a : pos := 5
 var b :string := "Hello"
in
 a + b
end

If you tried with your code from last assignment, this should lex and parse with no problems, producing a valid AST. We want the semantic analysis to throw an error, saying you can't add 5 and "Hello".

You can run the semantic analysis as follows:

- CM.make "sources.cm";

- Semant.transProg (Parse.parse "let.tig");
let.tig0.0:Can't typecheck this yet
val it = () : unit

When you complete your assignment, this should instead complain about not having an integer.

Examining ASTs

When your AST are big, it can be hard to see the resulting structure. I added the pretty printer to the project, so you can examine larger expressions.

- val bigtig = Parse.parse "big.tig";
val bigtig =
  OpExp
    {left=OpExp {left=IntExp #,oper=TimesOp,pos=2,right=IntExp #},oper=PlusOp,
     pos=2,right=OpExp {left=IntExp #,oper=TimesOp,pos=10,right=IntExp #}}
  : Absyn.exp

Notice pieces of the expression are missing, replaced with #. The pretty printer allows you to see the entire AST.

- PrintAbsyn.print (TextIO.stdOut, bigtig);
[autoloading]
[autoloading done]
OpExp(PlusOp,
 OpExp(TimesOp,
  IntExp(1),
  IntExp(2)),
 OpExp(TimesOp,
  IntExp(3),
  IntExp(4)))
val it = () : unit

Part 2

Add the rules for if/then/else expressions, function declarations and function calls and the remaining binops to the grammar as in the prior assignments, and generate the correct AST, then typecheck a program with functions and if expressions.