CS 444/644 - Compiler Construction (Winter 2016)
Acknowledgement: The Joos-related parts of the course are adapted by
permission from Michael Schwartzbach's dOvs course at the University
- Tuesdays and Thursdays, 2:30 -- 3:50 MC 4040
Ondřej Lhoták (olhotak), DC 2520, Nomair Naeem (nanaeem), DC 3111, Office hours: e-mail for appointment
- Teaching Assistants:
- Marianna Rapoport, Ming-Ho Yee (firstname.lastname@example.org)
- Web page:
- Handbook description:
- Final Exam:
- Monday, April 11, 2016, 7:30 PM -- 10:00 PM, PAC 12
- 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
You must achieve 50% or more on 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.
|Course Project: ||75% |
|- online Marmoset tests: ||60% |
|- written reports: ||15% |
|Final Exam: ||25% |
|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 50% of your final mark. An additional 10%
will be assigned to secret tests which will be run after
the assignment 5 deadline.
- Assignment 0: Choosing a group (0%) due Tuesday, January 12, 2016 at 11:59 pm
- Assignment 1: Scanning, Parsing, Weeding, AST Building (13%) due Friday, February 5, 2016 at 11:59 pm
- Assignment 2: Name Resolution (9%) due Wednesday, March 2, 2016 at 11:59 pm
- Assignment 3: Type Checking (9%) due Friday, March 11, 2016 at 11:59 pm
- Assignment 4: Static Analysis (6%) due Friday, March 18, 2016 at 11:59 pm
- Assignment 5: Code Generation (13%) due Friday, April 1, 2016 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 is in effect: (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, Friday, April 1, 2016.
Submitting an additional solution for an assignment can never reduce your mark.
- Group gets 90% marks on a January 10th 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 10th 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.
All members of the UW community are expected to hold to the highest standard
of academic integrity in their studies, teaching, and research.
This site explains why academic integrity is important and how students
can avoid academic misconduct. It also identifies resources available on
campus for students and faculty to help achieve academic integrity in — and
out — of the classroom.
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. 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.
Avoiding Academic Offenses
Most students are unaware of the line between acceptable and
unacceptable academic behaviour, especially when discussing assignments
with classmates and using the work of other students. For information
on commonly misunderstood academic offenses and how to avoid them,
students should refer to the
Faculty of Mathematics Cheating and Student
Academic Discipline Policy.
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
(formerly the Office for Persons with Disabilities or OPD),
located in Needles Hall, Room 1132,
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 the OPD at the
beginning of each academic term.