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

Due: Monday, May 19, by 11:00 pm. Turn in your project using the assignment dropbox .

Overview

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

• Create 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.
• Using these symbol tables, 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 is selected from a value with a reference type, then that name is defined as a 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).
  6. If a method in a subclass overrides one in any of its superclasses, the overriding method has the same parameter list as the original method, and the result type of the method is the same as the result type of the original one, or a subclass if the original result type is a reference type.
  7. It may be a good idea to check for cycles in the inheritance graph, but we are not making this check mandatory
  Feel free to add additional checks, but you should try to get this much done. It may be possible to do some of these checks on the fly while building symbol tables and type information, or it may require an additional visitor pass.
• 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. These should include, at minimum, the line number at which the error was discovered and a short message describing the message. It's fine to halt after a single error message.
• It will probably be useful to you to provide a mechanism to print the contents of the symbol tables. It will make debugging easier if you can see all of the identifiers declared in the program, their types, and other important information.

Details and Suggestions

• It's probably easiest to collect the type information in multiple passes 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. Each pass will require its own Visitor implementation.
• You may add appropriate fields in some or all AST nodes to store type and other information as necessary.
• DO NOT use the AST Type subclasses to represent semantic types. These represent the textual realization of types, and are conceptually different from the more abstract types we need to represent here. In particular, you may want to add methods to your type classes that would not be appropriate to add to the AST nodes.
• 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 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 tool is to augment the AST print visitor from the last assignment so it also prints type information where appropriate.  This isn't required, but it might save some debugging time.

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.

Here are a few examples of tests that will be run against your typechecker:

• Should fail
• Should pass
• Should pass

What to Turn In

• Submit an archive file containing only a directory named "minijava" (all lowercase) -- the root directory of your project. If you are developing for Linux, this should be a .tar file. If you are developing for Windows, it should be a .zip file. (Note the small change in turnin format from previous assignments). This should include two shell scripts:
• build.sh/build.cmd: When called, this should do whatever compilation steps are needed. Most likely, this will just call ant build.
• check.sh/check.cmd: This should take a MiniJava program on stdin and exit with a 0 error code if and only if the program passed all semantic checks (and passed scanning and parsing). If it fails, it should print the error message(s) to stderr.
• Please include a README.txt file containing the names, UW netID, and CSE netID, of all group members, as well as a short description of any challenges you faced in this part of the project, or anything else you would like the grader to know.
• Please run ant clean (or equivalent) before turning in your code to avoid turning in all your build artifacts. Similarly, please avoid turning in your entire .git folder, or the equivalent for whatever VCS you're using.
• If you are using Linux, your code should build and run on the Linux lab machines, or attu. Under Windows, it should run on Windows 7 with Java 1.7 and Ant 1.9
• Your group should turn in only a single copy.
• A small number of points will be assigned simply for following the turn-in instructions.