CS 4120: Introduction to Compilers
Fall 2011

Programming Assignment 2: Syntactic Analysis

due: Monday, September 19

In this assignment you will implement a parser for the Xi programming language (this will include devising a grammar to describe the language's syntax). The end result will be a program that reads a Xi source file and produces a pretty-printed version of the AST representing the program.

Your parser must implement the interface edu.cornell.cs.cs4120.xi.parser.Parser. We also ask that you provide an implementation of the interface edu.cornell.cs.cs4120.testing.ParserFactory, which constructs an instance of your parser. Your factory class must be public and have a no-argument constructor.

Your parser must be implemented using an LALR(1) parser generator, such as CUP for Java. If you are using some language other than Java, consult the course staff for the appropriate parser generator to use.

You must also supply a driver—a class with a main method—that we can run. Your program should accept as the sole argument the filename of a 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:

As with PA1, 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 names of your ParserFactory implementation and your driver class.

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

Building on PA1

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

If we discovered a problem with your lexer, 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 PA1 implementation indeed fails these tests), fix the bug. Discuss these tests in your overview document, and explain briefly what the problem was.

A note on JFlex and CUP

The authors of JFlex have provided good support for CUP compatible lexers. As such, if you used JFlex for PA1, we don't require that your parser communicate with your JFlex-generated lexer through the Lexer interface. Instead, you can modify your JFlex specification to generate a lexer that your CUP-generated parser is able to understand without an adapter. This likely requires some minor changes, but the heart of your lexer will be the same. If you do exercise this option, make sure to delete any extraneous source files.

Provided code

Much like last time, all the code that you need for this assignment is packaged in cs4120-pa2.jar, with source in cs4120-pa2.zip. We are including a few tools that you may find useful:

In addition, we are providing you with a stub CUP specification from which to begin.

Advice on AST design

We have provided an interface AbstractSyntaxNode that your AST classes must implement. It requires each node to provide a label for itself and the references to its children. This interface gives us a way to inspect the structure of your AST without constraining your creativity. You need to develop your own accessor methods for individual AST node types.

Submission instructions

Submit the following: