Uni-Logo

Compiler Construction Exercises

The compiler project will follow the setup of the compiler construction course at UCLA which is taught by Jens Palsberg. On their course homepage, you will find grammar specifications, interpreters and example files for each step of the project. Beware: We will use a slightly different MiniJava grammar (and a different parser generator)!

Registration for Participation

Submission Guidelines

  • Submissions consist of an executable Jar file with source inside and a report with the description of the implementation.
  • Submit your solution to the subversion repository. Your solution will consist of one folder (e.g. exercise1) for each exercise sheet which includes the project and the report.
  • Your solution will contain of a pdf file (e.g. report1.pdf) with a description. The description must be limited to two page per exercise. Submitting more than two pages will lead to reduction in points.
  • The description may be either in German or in English. Clear and understandable style is required.
  • You are strongly encouraged to test your solution with the provided test cases.
  • Provide your source code with comments to understand the intention.
  • Late submissions will not be accepted.

Subversion Repository

Template

You have to use the LNCS proceedings template for your homework.

Literature and Webpages

Homework policy

Programming is a creative process. Individuals must reach their own understanding of problems and discover paths to their solutions. During this time, discussions with friends and colleagues are encouraged, and they must be acknowledged when you submit your written work. When the time comes to write code, however, such discussions are no longer appropriate. Each program must be entirely your own work!

Do not, under any circumstances, permit any other student to see any part of your program, and do not permit yourself to see any part of another student's program. In particular, you may not test or debug another student's code, nor may you have another student test or debug your code. If you can't get code to work, consult the teaching assistant!

You may look in the library (including the internet, etc.) for ideas on how to solve homework problems, just as you may discuss problems with your classmates. All sources must be acknowledged.

The standard penalty for violating these rules on one part of one assignment is to receive a zero for the entire assignment. In case of repeated violations you will not be able to finish this course successfully.

Homework solutions must be neat and well organized. This includes commenting of code as well as following code conventions.

The above policies were adapted from policies used by Norman Ramsey at Purdue University in Spring 1996.

Tool Chain

Java, Eclipse

We assume you have a recent JDK (a Java 6 JDK is recommended for Eclipse 4.2) and an Eclipse >= 4.2 (Juno).

SableCC

SableCC is a parser generator for Java. From a grammar specification, it generates Java classes for syntax tree nodes, a parser, a lexer and skeletons for the Visitor pattern.

The stock version 3.6 of SableCC uses plain side-effect-only visitors (where a visitor's per-node methods can only communicate by changing the state of the visitor). We have extended SableCC to generate alternative visitor classes where per-node methods get one extra parameter and a return type, helping you write stateless visitors. You can use either kind of visitor classes. Furthermore, it has support for line number and position information in nodes not just in tokens.

Ant and the Standard Project Templates

Ant is a build tool for Java (not the latest greatest, but solid and boring). The Standard Project Templates use it to generate the parser, compile the parser together with your hand-written code, check your code for style compliance, and to build a submission-ready executable JAR file.

The Standard Project Templates contain the Ant build script build.xml and some example code. They expect you to keep your grammar files in grammar/ and your hand-written source code in src/.

A Standard Project Template is also an Eclipse project, so you should be able to import it into Eclipse using "Import/ General/ Existing Projects into Workspace". Do not use "Import/General/Archive File", that does the wrong thing.

You will get a specialized template for each exercise sheet. From exercise 2 on sheet 1 the corresponding Standard Project Template will support test driven development. Please read the strategy for test-driven development of grammars.

Installing Libraries

The Standard Project Templates assume that the Library Package is installed.

How to install the Library Package on a computer:

  1. Download the Library Package. Unzip it to some convenient directory.
  2. Create the file compiler-construction.properties from the template. Fill in the directory into which you unpacked the Library Package. Put it into your home directory, which is /home/USERNAME on Linux machines and /Users/USERNAME on Macs. If you'd rather use Windows, then your "home directory" is the value of user.home.

Download

Building and Running

This section assumes that you have installed everything so far.

Eclipse Ant view

So you've imported your project and changed its name. You can interact with the Ant build file using the Ant view of Eclipse. Open the Ant view ("Window/Views/Ant"). There is a plus-button there. Use it to add the build.xml of your project to the Ant view. The Ant view should now contain a tree of Ant targets.

Building

If you're using Eclipse, double-click on one of the Ant targets. In particular, target compile compiles your grammar and your code. On the command line, just say ant compile to compile.

Submitting

Submissions consist of an executable Jar file with source inside. The Ant target jar generates one (after checking your code style).

Checkstyle Complaints

Before building a Jar file, the jar target checks if your code complies with the Coding Rules. It uses CheckStyle. Take the complaints seriously and fix all of them before submitting.

Debugging the Build

The Ant target printenv will print some of the important configuration variables to stdout. If you ask for setup help, be sure to include its output. If build.xml does not even get as far as printing its settings, use printenv.xml instead.

Coding Rules

We apply the Sun Code Conventions for the Java Programming language. However, we're only picky about some of them: documentation.

Please document what your classes are supposed to achieve, what your methods are supposed to achieve, what you think their parameters mean, whether parameters and return may be null, and so on.

The Standard Project Templates use CheckStyle to check for the following documentation criteria. If CheckStyle complains, the build process refuses to create a submission Jar.

  • Every class has Javadoc
  • Every method has Javadoc
  • Every member variable has Javadoc

Test-driven Parser Development

From exercise 2 on sheet 1 the corresponding Standard Project Templates help you do your development in a test-driven way.

What the test suite does

The template contains a JUnit test FileParsingTest, which makes sure it runs once for each file in the directories testdata/ok and testdata/error. Each ok file is expected to be accepted by your parser. Each error file is expected to be rejected by your parser. For each failing expectation, you get a JUnit failure.

Running tests

Once you have generated the parser, right-click on the project, choose "Run As/JUnit test". That will cause Eclipse to execute all JUnit tests in the project, i.e. the FileParsingTest. You will then see a JUnit view with a tree. The tree contains green nodes for passing tests, blue nodes for failing tests and red nodes for unexpected run-time errors.

Growing a grammar one piece at a time

Start with a grammar which can only recognize programs consisting of an empty main class. Run the test suite and keep debugging your grammar until the initial test suite goes green.

Then, until you're done,

  1. pick a rule from the grammar which is already reachable from the grammar you have covered (in the beginning e.g. VarDecl, rather not ParamList, which only makes sense once you can parse methods)
  2. write one or more valid MiniJava programs which use the feature, and put them into testdata/ok.
  3. create damaged versions of your new test cases which are in an interesting way syntactically invalid, and put them into testdata/error.
  4. check that all of the new "testdata/ok" tests fail. If other tests fail, fix that problem first. If new tests don't fail, that's a bad sign, too.
  5. extend your grammar
  6. fix your grammar until all tests are green

If you have MiniJava programs which you don't expect to parse until later, you can stash them away in testdata/ok-future.