CS 410: Introduction to Compiler Design

Fall 2008

Instructor: Philip W. L. Fong  <pwlfong AT cs DOT uregina DOT ca>
Marker: Ali Hmer  <hmer200a AT uregina DOT ca>
Lectures: Tuesday/Thursday  ;  1:00-2:15 PM  ;  Education Building 632
Final Exam: December 16, 2008 (Tuesday)  ;  2:00-5:00 PM  ;  Place TBA
Office Hours: Wednesday 2:00-5:00 PM  ;  CW 308.10
Course web page: http://www.cs.uregina.ca/~pwlfong/CS410
Mailing list: CS410 AT cs DOT uregina DOT ca


  1. The official prerequisites of this course is the following:

  2. Having taken CS 350: Programming Language Concepts from me may give you some advantage, but those who do not have this background will do just fine.

  3. You are assumed to know the basics of Java programming. If the assumption does not yet apply to you, it is time to catch up.

Marking Scheme

Assignments: 50%
Final Exam: 50%

Textbook and Reference


Andrew W. Appel. Modern Compiler Implementation in Java (2nd Edition). Cambridge University Press, 2002. Call Number: QA 76.73 J38 A65 2002. Mnemonic: [Appel].

This course will cover all the chapters in Part I.


Alfred V. Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools (2nd Edition). Addison Wesley, 2007. Call number: QA 76.76 C65 A37 2007. Mnemonic: [ALSU]. Remarks: This is not a required text. Consult this though if you are keen.

Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Addison Wesley, 1994. Call number: QA 76.64 D47 1995. Mnemonic: [GoF].

All the above books have been placed on reserved. Ask the library circulation desk if you would like to use them in the library.

Development Tools


All programming assignments are to be completed in the Java programming language. While numerous books on Java are available out there, the official Java Tutorial is a good starting point. You are expected to know the materials of the following chapters by the end of the second week of lectures:

The latest Java Development Kit (JDK) can be downloaded at Sun's Java website.

You are advised to stay with the elementary features of the Java language. Messing with things like generics, variable argument lists, generalized for loop, etc, will only confuse you to no end. My recommendation is that, even if you are using a more recent release of Java (e.g., 1.4 and 1.5), turn on the compilation flag "-source 1.3" to make sure you stay with the language features defined in JDK 1.3. When your assignments are marked, the marker will turn on this compiler flag, and thus you code will not compile if you use any advanced language features introduced after JDK 1.3. Be warned.


The parser generator sablecc will be used in this course for producing frontend code for the compiler project. We will be using the legacy version 2.18.2. Do NOT use the 3.0+ releases.

The best "manual" of SableCC (at least for 2.18.2) is the Master's thesis of Etienne Gagnon, the author of SableCC. (We use the mnemonic [Gagnon] to denote this thesis.) The full text can be accessed at the publications page of the Sable Research Group at McGill University. Chapter 3 is a must read. Branch off to other chapters as you see fit.

Type sablecc in the command line to print a brief usage summary. The -d flag is particularly useful in maintaining a rational directory structure for this course.


The compiler project generates assembly code for the MIPS32 architecture, for which SPIM is a simulator.

A brief introduction to MIPS assembly language programming and the SPIM simulator is given in Appendix A: Assemblers, Linkers, and the SPIM Simulator of the following book:

Patterson and Hennessy, Computer Organization and Design: The Hardware/Software Interface (3rd Edition), Morgan Kaufmann, 2004.

(We use the mnemonic [PH-A] to refer to this appendix.) The full text of this appendix and other SPIM documentation is freely accessible online at the SPIM web site.


The following is a tentative lecture plan. Associated with each lecture week is a reading assignment. You are expected to have completed the assigned readings before the lectures in that week.

1 Sep 2, 4 

Remarks: There is no class on Sep 4, Thursday, due to the University Celebration Day holiday.

Sect. 1.1-1.2
2 Sep 9, 11 Sect. 1.3, 2.1, 2.2 01
3 Sep 16, 18 Sect. 2.3-2.5, 3.1
4 Sep 23, Sep 25 Sect. 3.2-3.5 02
5 Sep 30, Oct 2 Ch. 4
6 Oct 7, 9 Ch. 5 03
7 Oct 14, 16 Ch. 6
8 Oct 21, 23 Ch. 7 04
9 Oct 28, 30 Ch. 8
10 Nov 4, 6 Ch. 9 05
11 Nov 11, 13

Remarks: There is no class on Nov 11, Tuesday, due to the Remembrance Day holiday.

Ch. 10
12 Nov 18, 20 Ch. 10 06
13 Nov 25, 27 Ch. 11
14 Dec 2, 4
  • Putting It All Together
  • Review
Ch. 12 07

Office Hours

3 hours of instructor office hours are allocated weekly.

Wednesday2:00-5:00 PMCW 308.10

Except during scheduled office hours, the instructor is available ONLY by appointment.

Assignments (50%)

In this course, you will build a compiler for a representative fragment of the Java programming language. The compiler project is structured into a sequence of assignments.

#Due DateAssignment ModuleWeight
1 Sep 11 (Mon) 01 2%
2 Sep 25 (Thu) 02 8%
3 Oct 9 (Thu) 03 8%
4 Oct 23 (Thu) 04 8%
5 Nov 6 (Thu) 05 8%
6 Nov 20 (Thu) 06 8%
7 Dec 4 (Thu) 07 8%

Unless otherwise specified, all assignments are due at the beginning of class.

Materials submitted after the due date/time will NOT be graded.

Consult the document CS 410: Assignment Guidelines for more details.

Final Exam (50%)

The final exam will focus on your understanding of the theoretical aspects of the course, especially on notations, algorithms and theorems.

Final December 16, 2008 (Tuesday) 2:00-5:00 PM TBA 50%

You need to pass the final exam (i.e., >= 50%) in order to pass the course. Failure to obtain a passing mark in the final exam will result in a final grade of no more than 40%.


Important announcements will be made on the course mailing list. You are responsible for checking your email account at least once every day.

The class mailing list is for making announcements and for students to discuss issues pertaining to the course. Do NOT post questions to the instructor and the marker using this mailing list. If you have administrative concerns (e.g., trying to arrange an appointment with the instructor or the marker, complaining about marking, etc), please email either the instructor or the marker. Please include the magic phrase "CS410:" in the subject field if you want the email to be replied promptly. Since sufficient office hours have been allocated, the instructor and the marker will NOT answer questions about course materials and assignments through email.

Except during scheduled office hours, the instructor is available ONLY by appointment.

Materials submitted after the due date/time will NOT be graded.

You need to pass the final exam (i.e., >= 50%) in order to pass the course. Failure to obtain a passing mark in the final exam will result in a final grade of no more than 40%.

Intellectual dishonesty, including cheating and plagiarism, will not be tolerated. For more information, consult the following sections of the university calendar:

$Id: index.html,v 1.24 2008/11/12 18:43:35 pwlfong Exp $

Valid XHTML 1.0!