CIS 461/561 Fall 2002

Introduction to Compilers

Course Project

Project Schedule

The coding project for the course is to build a compiler for the Tiger language described in Appendix A of Appel's book. This project is worth approximately 50% of your grade. The project is broken into several phases. You may choose to work on the project phases in teams of two or three, or you may work entirely on your own. If do a project phase as a team, each team member will receive the same grade on that phase. By the end of the course we will have implemented a real, working compiler. This is an ambitious schedule and it is important to keep up as each phase builds upon the previous.

Grading of the project will be mostly automatic, i.e., running it on test cases. As time permits, I will also try to evaluate your code by a cursory examination of it.

Tools and resources used for the project are described below.

Description	Topic	Due
Phase 1	Lexical analyzer for Tiger language	9 AM Tuesday, October 15, 2002
Phase 2	Syntax parser for Tiger language	9 AM Tuesday, October 29, 2002
Phase 3	Building the abstract syntax tree for Tiger	9 AM Thursday, November 7, 2002
Phase 4	Perform semantic analysis on Tiger programs	9 AM Thursday, November 21, 2002
Final Phase	Tiger compiler	5 PM Friday, December 6, 2002

All assignments must be turned in electronically. Instructions on doing this will be provided. Assignments will not be accepted after the due time indicated above.

Resources and Tools

We will [almost] maintain consistency with the textbook by using the tools described there:

• JFlex lexical analyzer generator (Java equivalent of AT&T Lex or Gnu Flex for C)
• CUP parser generator (Java equivalent of AT&T Yacc or Gnu Bison for C)
• Jasmin Java assembler interface

You can find these tools in /cs/classes/cis461/tools on the departmental Unix machines. If you want to use them from here, set up your CLASSPATH appropriately. Or, you might prefer to obtain the full packages and install them on your own machine.

The code skeletons and samples provided by the textbook author are in the /cs/classes/cis461/tiger directory on the departmental unix machines.

Alternative tools you might consider for other projects:

• for C and C++: Flex and Bison are the current best high-performance tools for LALR(1) parser construction. Flex by itself is a good tool for knocking out a simple transducer that doesn't require the full power of a parser, but is either too complex for Awk/Perl/Sed/ et al. or requires higher performance than a scripting language can provide.

• for C and C++: ANTLR: An LL(k) parser generator. We'll talk about the tradeoffs between LALR(1) and LL(k) parsers in class -- basically, the LALR(1) parsing grammar will be closer to the abstract syntax (particularly for expressions), but the LL(k) grammar will allow you to sprinkle actions more liberally through the parsing.

• for Java: the original JavaCC and its descendant Metamata Parse are LL(k) parser generators (influenced to some degree by ANTLR). In addition, they integrate the lexical analysis generator (you write one grammar file with both regular expressions for lexical analysis and productions for the context-free grammar). Moreover, they accept a variant of BNF with some handy extensions, some of which can be used to compensate the usual problems of LL parsing. It is unclear (to me, at least) whether on balance it would be better to use JavaCC or JLex + CUP --- each approach has its advantages and shortcomings.
  Apparently ANTLR can also generate Java code - see http://www.antlr.org.

• ML, Ada, ... : There are variants of Lex and Yacc for just about any major programming language you can think of, with the possible exception of scripting languages which have their own built-in pattern matching facilities.