CS 444/644 - Compiler Construction (Winter 2021)
Acknowledgement: The Joos-related parts of the course are adapted by
permission from Michael Schwartzbach's dOvs course at Aarhus University.
- Mondays and Wednesdays, 1:00 -- 2:20
on Learn live-streamed on Youtube and recorded on Youtube and on a Univeristy of Waterloo server. Links to the live stream and the recordings can be found on Piazza and on Learn. The lectures will be recorded so you may view them at a time of your convenience, but I encourage you to attend them during the live time slot if possible, since this allows you to interact and ask questions during the lecture. Additional questions about lecture material will be answered on Piazza.
- Ondřej Lhoták (olhotak), DC 2520, Office hours: Wednesdays 2:30 -- 3:30 or e-mail for appointment, on Teams
- Teaching Assistants:
- Xiang Fang, Michael Thode, James You (firstname.lastname@example.org)
- Web page:
- Handbook description:
- 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. The goal of the course is to acquaint
students with software tools and techniques which are applicable both
to compilers and the implementation of system utility routines, command
- Topics covered:
scanning, parsing, abstract syntax trees, scoping and name resolution, type checking, static analysis, runtime organization, code generation.
Gosling, J., Joy, B., Steele, G., Bracha, G., The Java Language Specification, Second Edition, Prentice Hall, 2000.
Paper copies can be purchased from
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:
- 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
|- public Marmoset tests: ||65% |
|- secret Marmoset tests: ||20% |
|- written reports: ||15% |
|Above CS 444 Marking Scheme, scaled: ||80% |
|Literature Survey: ||20% |
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.
The above assignment marks total 65% of your final mark. An additional 20%
will be assigned to secret tests which will be run after
the Assignment 5 deadline.
- Assignment 0: Choosing a group (0%) due Monday, January 18, 2021 at 11:59 pm
- Assignment 1: Scanning, Parsing, Weeding (17%) due
Thursday, February 11Wednesday, February 24, 2021 at 11:59 pm
- Assignment 2: Name Resolution (12%) due
Monday, March 1Wednesday, March 3, 2021 at 11:59 pm
- Assignment 3: Type Checking (12%) due
Wednesday, March 10Friday, March 12, 2021 at 11:59 pm
- Assignment 4: Static Analysis (8%) due Monday, March 22, 2021 at 11:59 pm
- Assignment 5: Code Generation (16%) document due Wednesday, April 14, 2021 at 11:59 pm, implementation due Sunday, April 18, 2021 at 11:59 pm
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.
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, Wednesday, April 14, 2021.
Submitting an additional solution for an assignment can never reduce your mark.
- 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%
In order to maintain a culture of academic
integrity, members of the University of Waterloo community are expected
to promote honesty, trust, fairness, respect and responsibility.
Check the Office of
Academic Integrity's website for more information.
A student who believes that a decision affecting some
aspect of his/her university life has been unfair or unreasonable may
have grounds for initiating a grievance. Read
Policy 70 — Student Petitions and Grievances, Section 4.
When in doubt please be certain to contact the department's administrative
assistant who will provide further assistance.
A student is expected to know what constitutes academic
integrity, to avoid committing academic offenses, and to take
responsibility for his/her actions.
Check the Office of
Academic Integrity's website for more information.
A student who is unsure whether an
action constitutes an offense, or who needs help in learning how to
avoid offenses (e.g., plagiarism, cheating) or about "rules" for group
work/collaboration should seek guidance from the course professor,
academic advisor, or the Undergraduate Associate Dean. For information on
categories of offenses and types of penalties, students should refer to
Policy 71 — Student Discipline. For typical penalties, check
Guidelines for the Assessment of Penalties.
A decision made or a penalty imposed under Policy 70, Student Petitions
and Grievances (other than a petition) or Policy 71, Student Discipline may
be appealed if there is a ground. A student who believes he/she has a
ground for an appeal should refer to
Policy 72 — Student Appeals.
Note for students with disabilities
located in Needles
Hall, Room 1401, collaborates with all academic departments to arrange
appropriate accommodations for students with disabilities without compromising
the academic integrity of the curriculum. If you require academic
accommodations to lessen the impact of your disability, please register with
AccessAbility Services at the beginning of each academic term.