CS 444/644 - Compiler Construction (Winter 2026)

General

Lectures:: Tuesdays and Thursdays, 10:00 -- 11:20 RCH 112
Instructor:: Ondřej Lhoták (olhotak), DC 2520, Office hours: Thursdays 11:30 -- 12:30 or e-mail for appointment
Teaching Assistants:: Harris Lau, Daisy Li
Web page:: http://www.student.cs.uwaterloo.ca/~cs444
Piazza:: https://piazza.com/uwaterloo.ca/winter2026/cs444
Course Outline:: https://outline.uwaterloo.ca/viewer/view/n7esje
Handbook description:: http://www.cs.uwaterloo.ca/undergrad/handbook/courses/cDescr/CS444.shtml
Final Exam:: TBA
Course Description and Objectives:: The objective of the course is to provide a thorough understanding of the basic structure of compilers for Java-like languages. A major part of the course consists of the implementation of a compiler for a simplified Java-like language.
Topics covered:: scanning, parsing, abstract syntax trees, scoping and name resolution, type checking, static analysis, runtime organization, code generation.

Acknowledgement: The Joos-related parts of the course are adapted by permission from Michael Schwartzbach's dOvs course at Aarhus University.

Web Resources

Gosling, J., Joy, B., Steele, G., Bracha, G., The Java Language Specification, Second Edition, Prentice Hall, 2000.
Each edition of the Java Language Specification specifies a different version of the Java language. The Joos language that we will compile in this course is a subset of the version of Java specified in the Second Edition. You may also find the First Edition useful because it contains an LALR(1) grammar for Java.
The Joos Languages
Parsing handout from CS 241
A LALR(1) DFA example
An SLR(1)/LR(1)/LALR(1) parse table generator:
An example of an Abstract Syntax Tree (AST) design: The Eclipse AST for Java
Assembly Language Resources:

Recommended References

Fischer, C., Cytron, R., LeBlanc, R., Crafting a Compiler
(An older edition focused on C is: Fischer, C., LeBlanc, R., Crafting a Compiler with C)
Appel, A., Modern Compiler Implementation in Java (or C, or ML)
Louden, K., Compiler Construction: Principles and Practice
Aho, A., Lam, M., Sethi, R., Ullman, J., Compilers: Principles, Techniques, & Tools

Evaluation

CS 444

Course Project:	75%
- online Marmoset tests:	60%
- written reports:	15%
Final Exam:	25%

You must achieve 50% or more on the final exam in order to pass the course. If you do not meet this minimum requirement then your final grade for the course will be at most your final exam mark.

CS 644

Above CS 444 Marking Scheme, scaled:	80%
Literature Survey:	20%

Course Project

The overall project for the course is to write a compiler from Joos 1W, a fairly large subset of Java, to i386 assembly language (the Netwide Assembler dialect). The project will be done in groups of three. The project will be broken up into several assignments with fixed due dates. The assignments must be submitted to the Marmoset on-line submission and testing system. For each assignment, you will submit both your code and a written report (for assignments 1, 4, and 5) to Marmoset. Marks for your code will be reported to you by Marmoset, and your marked written reports will be returned to you by e-mail.

Assignment 0: Choosing a group (0%) due Wednesday, January 14, 2026 at 11:59 pm
Assignment 1: Scanning, Parsing, Weeding, AST Building (13%) due Monday, February 9, 2026 at 11:59 pm
Assignment 2: Name Resolution (9%) due Friday, February 27, 2026 at 11:59 pm
Assignment 3: Type Checking (9%) due Friday, March 6, 2026 at 11:59 pm
Assignment 4: Static Analysis (6%) due Friday, March 13, 2026 at 11:59 pm
Assignment 5: Code Generation (13%) due Monday, April 6, 2026 at 11:59 pm

The above assignment marks total 50% of your final mark. An additional 10% will be assigned to secret tests which will be run after the Assignment 5 deadline.

Students enrolled in CS 644 are required to complete a literature survey on a topic related to compiler construction.

Resources available in the `linux.student.cs` environment.

Test cases used by Marmoset to test your assignment submissions can be found in /u/cs444/pub/assignment_testcases. Use these testcases to test your solutions and before submitting to Marmoset.
For this course, a minimalist version of the Java standard library is provided. The library versions for each assignment can be found in the linux.student.cs environment in the directory /u/cs444/pub/stdlib/. On assignment 2 and later assignments, Marmoset will include all files in this library on the joosc command line for every test, in addition to other source file(s) specific to that test. The following versioning scheme is used to make it possible to correct errors and/or to extend the library for future assignments (although we aim to minimize the number of changes that will be required). The 3 in the directory name refers to Assignment 3, and the 0 is the first version of the library. Any corrections to the Assignment 3 version of the library will appear in the directories 3.1, 3.2, etc., and the version of the library for Assignment 4 will appear in the directory 4.0. Currently all the stdlib versions are the same.

Group Work Marking Policy

When working in a group, disagreements sometimes arise. One of the objectives of this course is for you to resolve such disagreements with sufficient, constructive, and frank communication within the group. Therefore, when disagreements arise, discuss them within the group before asking the instructor to intervene. If the group fails to reach a resolution, the group as a whole should arrange a meeting with the instructor. The instructor's role is primarily to mediate the discussion within the group, rather than to intervene in the disagreement.

Problems are easier to resolve if handled early. When a problem arises, try to resolve it as soon as possible. Do not leave it until the end of the course.

At the end of the course, the following policies will be used to distribute marks among the group members:

Normally, each member of the group will be given an equal mark. You should therefore strive to ensure that each group member makes an approximately equal contribution to the project.
The group may propose a different distribution of the marks, provided all group members consent to the distribution. Such a proposal must be made to the instructor within three days after the due date of the last assignment. The marks will be distributed in such a way that the mean of the marks equals the original group mark and no individual project mark exceeds 100%.
If agreement cannot be reached, a member of the group must contact the instructor within three days of the due date of the last assignment. The instructor will ask each group member to submit a written statement detailing the contributions of each group member, the nature of the conflict, and the steps that were taken by the group to resolve the conflict. Failure to submit the statement within three days of being asked to do so will result in a mark of zero for that group member. Based on the statements, the instructor will make a final decision about the mark distribution. Note that the instructor will generally not deviate from the equal distribution of marks unless convinced that the group took sufficient and timely steps to resolve the conflict internally.

Late Policy

The written report for each assignment must be submitted by the assignment deadline. Reports submitted after the deadline will not be marked and will receive a mark of zero. If you cannot finish an assignment by the deadline, submit what you have by the deadline, and explain any unfinished parts in your report.

For code submissions, the following late policy applies: (0.5 * best-on-time) + (0.5 * best-overall), where

best-on-time: is the best submission within the assignment deadline
best-overall: is the best overall submission up until 11:59pm, Monday, April 6, 2026.

Examples:

Group gets 90% marks on a January 20th submission of Assignment 1 and there is no submission after the deadline.
Mark: (0.5 * 90%) + (0.5 * 90%) = 90%
Group gets 50% marks on a January 20th submission of Assignment 1 and 90% on a February 20th re-submission of Assignment 1.
Mark: (0.5 * 50%) + (0.5 * 90%) = 70%
Group gets 90% marks on a February 20th submission of Assignment 1.
Mark: (0.5 * 0%) + (0.5 * 90%) = 45%

Submitting an additional solution for an assignment can never reduce your mark.

Short-term Absence Policy

If any member of a group declares a Short-term Absence in Quest that covers the due date of an assignment, the due date can be extended for the entire group.
The group member who is declaring an absence must notify the course staff of the declared absence by filling out the Short Term Absence Extension Request form within 24 hours of the original assignment due time. Failure to do so will result in the absence declaration not being considered and the original deadline remaining in effect. Once the form is submitted, the deadline extension (if eligible) is permanent and cannot be revoked. The link to the form is available via Piazza.
A short-term absence covering a due date of April 5 or 6, 2026 will be accommodated by a 96-hour extension. A short-term absence covering any other due date will be accommodated by a 48-hour extension.