CS 4120: Introduction to Compilers
Fall 2011

Programming Assignment 3: Semantic Analysis

due: Monday, October 3

In this assignment you will implement a type checker for the Xi programming language. Given an AST of a syntactically valid Xi program, the typechecker will see if it makes sense according to the static semantics of the language. If there are any type errors it should produce descriptive error messages. If there are not, it should annotate the AST with information computed during its work, and also construct symbol tables describing all variables. We have provided a formalization of the Xi type system to help you get started.

The new functionality must be invoked from your driver, which as in the previous assignment must provide a main method that we can run which will invoke all phases of your compiler thus far. Your program should accept as the sole argument the filename of an Xi source file. For example:

$ java netid.Driver source.xi

You are free to add other options and arguments, but the command above must work.

Your program should behave as follows:

• If there is an error within the source (whether syntactic or semantic), your program should indicate this by printing to standard output (System.out) an error message that includes the position of the error. Your semantic error messages should be as helpful as possible.
• If the source is a syntactically and semantically valid Xi, your program should print to standard output its AST decorated with type information for every expression node (and any other information computed by static analysis that you find useful), as well as its symbol tables at the end of every block statement (including function and procedure bodies).

As for the previous assignment, we ask that you submit an overview document describing your work. So we can use your code, include in the metadata section the fully-qualified class name of your driver class.

The requirements for source control and package nomenclature are the same as in previous assignment. You are expected to use SVN or a similar source control system with the permission of course staff.

Building on PA2

You will be using your parser from PA2. Part of your task for this assignment is to fix any problems that you had in PA2.

As before, If we discovered a problem with your submission, for this assignment you must devise one or more test cases that clearly expose the bug. After you have done this (and confirmed that your PA2 implementation indeed fails these tests), fix the bug. Discuss these tests in your overview document, and explain briefly what the problem was.

Advice on typechecker design

The type information you compute will be useful in code generation, not just for catching errors. Similarly symbol tables are useful when allocating memory for local variables. Therefore, try to preserve information you will need in later phases.

Submission instructions

Submit the following:

• Your overview document.
• Your source code, compressed into a *.zip or *.tar.gz archive. Please ensure that the directory structure of your source files is maintained within the archive so that your source can be compiled upon extraction. If your code depends on any third-party libraries, please include compilation instructions in your overview document. Please do not include any non-source files or directories such as .classpath, .project, .svn, etc.
• Any test code or test files that you used to test your program. Include these in a tests/ directory within your source archive. Be sure to mention these in your overview document and to describe your testing strategy.
• If you are using a lexer generator, please include the lexer input file (e.g., *.flex) as well as the generated code.
• Include your parser generator input file (e.g., *.cup) as well as the generated code.