CSE P 501 Project IV
Static Semantics, Type Checking & Symbol Tables

Due: Wednesday, Nov. 18, by 11:00 pm. Turn in your project using the assignment drop box (links on the project page).

Overview

Add static semantics checking to your compiler. In particular, you should do the following:

• Add global symbol table(s) storing information about classes and their members, and local symbol tables for each method to store information about parameters and local variables.
• Calculate and store type information for classes, class members, parameters, and variables.
• Calculate type information for expressions and other appropriate parts of the abstract syntax.
• Do some basic error checking to verify at least the following properties:
  1. Every name is properly declared.
  2. Components of expressions have appropriate types (e.g., + is only applied to values of type int, && is only applied to values of type boolean, the expression in parentheses in an if or while statement is boolean, etc.).
  3. If a method or field is selected from a value with a reference type, then that name is a method or field member of that type.
  4. Methods are called with the correct number of arguments.
  5. In assignment statements and method call parameter lists, the values being assigned have appropriate types (i.e., the value either has the same type as the variable or is a subclass of the variable's class).
  Feel free to add additional checks, but you should try to get this much done. It may be possible to do many of these checks on the fly while building symbol tables and type information.
• If your parser grammar accepts input that is not part of MiniJava (i.e., uses a covering grammar or otherwise parses constructs that are syntactically legal but have semantics errors), check that the program is actually legal. If you implemented extensions like casts, you should add appropriate error and type checking.
• Print suitable messages for errors detected. It's fine to supress useless error messages - for instance, feel free to complain only once about an undeclared variable instead of repeating the message each time the variable is used in the code.

Details and Suggestions

• It's probably easiest to collect the type information in a pass or two over the AST. Pass I should collect information about classes and fields (both data and methods), and build the global symbol tables. Pass II would then analyze method bodies, build the local symbol tables, and perform type and other error checking. You might find it more convenient to break this down into more passes each of which does fewer things, particularly for Pass I, where it can be easier to build a global symbol table of class names before processing individual classes to build class symbol tables with information about variables, methods, and their types.
• You should add appropriate fields in some or all AST nodes to store type and other information as necessary.
• Use the visitor pattern! This is where it pays off to have gone to the trouble to set up the visitor machinery. Provide new implementations of the Visitor interface for the various semantics checks.
• Take advantage of the standard library container classes and data structures in Java (or whatever implementation language you're using) to simplify your implementation. Class HashMap should be particularly useful for symbol tables. Use the List classes (ArrayList or LinkedList) for things like argument lists and field lists in classes. Don't reinvent any more wheels than necessary.
• It can be useful to include a few auxiliary methods that perform common operations on types. Possibilities include a method that returns true if two types are the same, and a method that returns true if a value of one type is assignable to another. Also possibly useful: a method that tries to add an entry to a symbol table and reports an error if the name is already declared, and another that looks up an identifier and reports an error if it is not found (and maybe adds it to the symbol table with an "undefined" type, which can be used to suppress additional, extraneous error messages about the same identifier).
• A useful debugging tool is to augment the toString() methods in appropriate AST nodes (if you have them) so they also print the type information associated with that node.  This isn't required, but it might save some debugging time.
• To generate code, the symbol table information will eventually have to be augmented to include offsets of parameters and local variables in method stack frames, and offsets of data fields in objects. This isn't required yet, because we're just beginning to talk about runtime representations, but if you have a chance to do some advance work on this part of the project now, it should save time later.

Testing

You should test your compiler on both correct MiniJava programs and on programs that contain various sorts of static semantics problems, including programs that are syntactically legal (i.e., accepted by the parser), but have static semantics errors.

What to Turn In

Turn in the following:

• Java (or other) source code for your the compiler, including code and data structures used to represent types and symbol tables.
• A README file explaining how to build and run your compiler, including a description of any required software or libraries if you're using your own project setup, along with any notes about extensions, additional checks performed, or other unusual or interesting things in this phase of your compiler. You should be sure to describe how much of the requested checking was actually implemented, and any major surprises (either good or bad) you encountered along the way.
• Files showing the contents of symbol tables for one or two sample programs. This must include the Factorial.java sample program from the MiniJava web site.
• A few files demonstrating the output produced by your compiler (if any) for both error-free and erroneous source programs.

If you are working with others, you should turn in only one copy per group with your names listed in the same order as usual.