CS 4120: Introduction to Compilers
Fall 2013

Programming Assignment 3: Semantic Analysis

due: Monday, October 7

In this assignment you will implement a type checker for the Cubex programming language.


Your submission has to have two parts:

The type-checker

As in the previous assignments, this program should take a file name as an argument, read that file, check it and print results to the standard output. The possible results are:

What is a typing error?

A program has a typing error if it cannot be validated using the rules of section 2 of the language specification.

What features have to be included?

In this assignment, the full language specification is applicable. This means that you will need to build upon your implementation of desugaring full Cubex into core Cubex in order to do all the validations, and might have to add parts of the desugaring that you left out in the previous assignment, in particular methods implemented in interfaces. How you represent those internally is up to you.


This assignment will be graded in a staged mode, which means that you can concentrate on some parts of the assignment and leave others out with a predictable loss of points. Our tests will be organized in the following stages, meaning that programs only consist of the things in that stage and the preceding ones:

  1. Statements
  2. Non-generic functions
  3. Generic functions
  4. Non-Generic classes without inheritance
  5. Generic classes without inheritance
  6. Generic classes with single interface inheritance
  7. Generic classes with single interface inheritance + interface method implementations
  8. Generic classes with class inheritance
  9. Generic classes with multiple interface inheritance

Note: Any stage (including stage 1) may contain code related to Iterable, which you have to handle to the fullest extent.

80% of the tests will test programs in stages 1-3.

10% of the tests will test programs in stages 4 and 5.

10% of the tests will test programs in stages 6-9.

How to submit

You have to include the complete source code in the jar-file, including inputs for any lexer/parser generators you might use. You will need a manifest file (MANIFEST.MF) that sets the classpath. Your manifest file should look like this:

Manifest-Version: 1.0
Class-Path: . antlr-4.1-complete.jar
Main-Class: [your-class-name-here]

The following code snippet does this packaging for you (provided TypeChecker is your main class; .g4 is the file extension for ANTLR files).

jar cvfm TypeChecker.jar MANIFEST.MF *.class *.java *.g4

The text file

Finally, we ask that you submit a small text file (.txt) that contains the following information:

Advice on typechecker design and division of work

The type information you compute will be useful in code generation, not just for catching errors. Therefore, try to preserve information you will need in later phases.

A good way of splitting the work among the members of the group might be along those lines:

In order for this to work, you need clearly defined interfaces for the different parts of your program. We also recommend pair-programming at least for the more critical parts of the assignment.

Source control

We recommend that you use some kind of source control. Be aware that your repositories should not be publicly viewable on the web. GitHub offers private repositories for students.


You should thoroughly test your solutions before turning them in. We provided some basic test examples for you to play with, but keep in mind that we will test your submissions with more complex examples, too. The way a test works is that after running

java -jar TypeChecker.jar tc_test1.in > validation1.out

the content of validation1.out should be equal to tc_test1.out .