Type checking in compilers [closed]

Question

I'm currently trying to create a TypeChecker that will successfully type check a MiniJava program. I've been working on it, staring at it, for the past 10 hours, but I have no idea even where to begin. I have given up getting the project done in time, but I want to still learn how it's done. We are given complete parser for MiniJava and a set of classes used for traversing the Abstract Syntax Tree as well as two different default Visitors, DepthFirstVisitor and GJDepthFirst. We are supposed to extend these visitors to get the project done.

I understand the VERY basic concept of what needs to get done: we need to catch errors in the code that the parser couldn't catch. We need to run through the code in 2 passes. The first pass is building the symbol table (?) and the 2nd, to use the symbol table to check. Is this correct? But then I have no idea where or how to begin to implement this in code.

I realize this isn't really a question.......but any kind of guidance or help will be greatly appreciated. I have a few friends in my class who are in the exact same boat as me.

Thank you!

Answer 1

Since your language is Java-like, you can do a simple type propagation instead of a more generic type inference. First, you have to define a new AST, with each expression annotated with its type. Then, perform a depth-first (for expressions) / breadth-first (for block statements) transform from your old AST into the new one, applying simple rules for each node:

• Every variable is annotated by its type, and since you've been going breadth-first over your blocks you must have all the variable types fixed by the moment a variable is referenced. This applies to class fields, method arguments and locally scoped variables.
• Every literal yields a default type (string is a string, integer number is, say, a 32bit integer, floating point number is double, etc.)
• Binary arithmetic operations would insert implicit casts based on some ranking rules (pick up any, it does not really matter)
• Ternary operator checks if first argument is boolean and two other arguments are of the same type
• A method call is the most complicated thing here: you have to get the first possible overloaded method with argument types to which you can cast all your arguments implicitly. It's up to you what to do if there are conflicts.
• and so on...

Statements cannot be annotated with types, but you'll have to check their expression arguments types and possibly do implicit casting. Also you can infer var or auto types at this stage (please note, it is not a "type inference", just a special case of type propagation).