COMP 3353 Compiler Construction, Winter 2007

General Information


The prerequisite for this class is either a passing grade for COMP 3351 or permission from the instructor.

The project for the class is a compiler that translates MiniJava to MIPS implemented in Java. During the project, MiniJava is translated in multiple steps to MIPS, each step targeting an intermediate language with well-defined semantics. For testing, interpreters are provided for each of the intermediate languages.

Lecture Hours and Location

The lectures will be held Tuesdays and Thursdays from 4pm to 6pm in JGH 316.

Office Hours

Christian Grothoff - JGH 214
Tuesday, Wednesday, Thursday 2-3:30pm and by appointment.

Textbook and Syllabus

"Modern compiler implementation in Java", by Andrew W. Appel, Cambridge University Press, 2002. This will be the main textbook for the class covering most of the material.
"Version Control with Subversion", on-line book (no need to buy a copy). You must know how to use subversion as a developer (not as an administrator) in order to submit your assignments. Use this book as a reference if you encounter problems. Basic knowledge of chapters 1-3 should be sufficient.

Specific topics that will be covered:

Assignments and Grading

There will be larger individual programming assignments that must be turned in for grading by a certain deadline.
Students are encouraged to discuss the materials and projects together. However, all programs must be done individually. Academic dishonesty includes, but is not limited to: plagiarism, cheating in exams, unauthorized collaboration and falsifying academic records. Violation of any of these may result in a grade penalty on assignments, an "F" in the course, dismissal from an academic unit, revocation of admission, suspension from the University as well as being roasted over a slow fire.
Generally, all assignments are due before class on the date specified with the assignment. Exceptions to this rule (allowing later submission) may be announced in class.

The different kinds of assignments are weighted as follows:

Programming assignments55 Pts
Midterm15 Pts
Final30 Pts

Theoretically you could get a total of 100 Pts. Grades will be given as follows:

A> 85 Pts
B> 70 Pts
C> 55 Pts
D≥ 40 Pts
F< 40 Pts


You will need various applications for the class, all of which are freely available for various operating systems. Personally, I'm using Debian GNU/Linux unstable. If you have any problems installing the software, you can always use the department's solaris machines which have all of the necessary software installed. Copy the provided bashrc into your home directory (under .bashrc) in order to set the paths correctly (only works if you use bash). Here is a list of the software programs that you will need (possibly incomplete):

Java 5.0
I recommend using the Sun JDK; earlier Java versions (including gcj) should also work, but you may have to use an older version of JTB
Pick a version that works with your Java installation. You should also write a shell script to invoke JTB (something along the lines of java -classpath jtb.jar EDU.purdue.jtb.JTB "$@")
JavaCC 4.0
Again, other versions may work just fine.
Any version should do.

Submission of Assignments

Each student will get access to a subversion repository. Assignments must be committed to that repository by the respective deadline. Students are encouraged to use the repository for version control while still working on the assignment. Only the last version commited before the deadline will be used for grading.
In order to access your subversion repository, you must first request an account. For this, you first need to generate an encrypted password. On any GNU/Linux or UNIX machine (or even a Microsoft system with Apache) enter

    $ htpasswd -nb $USER PASSWORD
where PASSWORD is your desired password. You will not be able to change the password later. Send the output of the command to to request an account. Once your account has been created, you should do an initial check out:
    $ svn checkout$USER
    $ cd $USER
You should then proceed to create a directory for the first project and commit it:
    $ mkdir P1
    $ svn add P1
    $ svn commit -m "comment"
Afterwards, you can add the files to submit just like you added the directory. Make sure to commit the final version with all files (hint: svn status) before the deadline. It is also a good idea to do a seperate checkout and verify that the result works.


This is a preliminary schedule. Feedback is welcome.

Class 1: Introduction

Material from the textbook
Chapter 1
Useful links
Subversion, bashrc
  1. Hello World! (due: Class 5, 1 Pt), P1/

Class 2: Lexical analysis

Material from the textbook
Chapter 2

Class 3: Parsing and EBNF

Material from the textbook
Chapter 3.1

Class 4: LL parsing

Material from the textbook
Chapters 3.2 and 3.4

Class 5: JavaCC and JTB

Material from the textbook
Chapter 4
Useful links
JTB, JavaCC, Visitor pattern
  1. Type checking of MiniJava (due: class 8, 12 pts)

Class 6: Semantic analysis

Material from the textbook
Chapter 5

Class 7: Activation records

Material from the textbook
Chapter 6

Class 8: Translation

Material from the textbook
Chapter 7
  1. MiniJava to Piglet (due: class 10, 12 pts)

Class 9: Simplification

Material from the textbook
Chapter 9

Class 10: Midterm

  1. Piglet to Spiglet (due: class 13, 12 pts)

Class 11: Liveness analysis

Material from the textbook
Chapter 10

Class 12: Register allocation

Material from the textbook
Chapter 11
Useful links
Iterated Register Coalescing

Class 12: Register allocation (Part 2)

Material from the textbook
Chapter 11
Useful links
Linear Scan Register Allocation, Optimal Bitwise Register Allocation using ILP
  1. Spiglet to Kanga (due: class 16, 12 pts)

Class 14: LR parsing

Material from the textbook
Chapters 3.3 and 3.5

Class 15: Type systems

Material from the textbook
Chapter 16

Class 16: Static Single Assignment Form (SSA)

Material from the textbook
Chapter 19
Useful links
A Simple Graph-Based Intermediate Representation, Efficiently Computing Static Single Assignment Form and the Control Dependence Graph
  1. Kanga to MIPS (due: class 19, 10 pts)

Class 17: Optimizations

Material from the textbook
Chapters 18, 20 and 21

Class 18: Control-flow analysis

Material from the textbook
Chapter 17

Class 19: Continuation Passing Style (CPS)

Useful links
Continuation-Passing, Closure-Passing Style

Class 20: Final Exam


Grades will be e-mailed to the e-mail address given with the request for creating the subversion account. For how to interpret the e-mailed grades please contact the TA.

Christian Grothoff
Last modified: Sat Apr 21 18:24:48 MDT 2007