UofT ECE 467 (2022 Fall) - Home
The website and starter code is being pre-emptively updated!
I don't know if I'll be teaching the course again, but if I wait until next year I'll forget feedback I've received.
Note that more test cases have been added (if you pull the new starter code); those are for the (potential) future!
Welcome to the homepage for ECE 467 being offered at UofT in the 2022 Fall semester.
Lectures begin on Tuesday, September 13.
Tutorials and labs begin on Friday, September 16.
Update (2022 September 27): the labs being every other week starting on September 16 doesn’t match the schedule on Acorn.
We will have lab on September 30 and October 7.
From October 7, the TAs will be holding lab sessions every other week for the rest of the semester (so after October 7 is October 21).
Pre-recorded lecture videos are available here.
They are not necessary to watch for this course.
The lecture videos are made as my own practice before the in-person lectures.
In general, they should not be considered a replacement for the in-person lectures.
If you miss/will be missing a class, you should contact me so we can sync up.
Lecture Schedule
- September 13
- Course information and introduction (video).
- Regular languages and regular expressions (video, slides).
- Non-deterministic finite automata (chapters 3.6.1, 3.7.4) (video, slides).
- Deterministic finite automata (chapters 3.6.4, 3.7.1) (video, slides).
- Correction to video: for any regular language, a minimal DFA exists and is unique up to relabeling of the states.
(There may still be multiple DFAs for a regular language, just as there may be multiple NFAs for a regular language.)
- September 20
- Context-free grammars (chapter 4.2) (video, slides).
- Top-down parsing: recursive descent parsing (chapters 4.3.3, 4.4.1) (video, slides).
- FIRST and FOLLOW sets (chapters 4.4.2) (video, slides).
- September 27
- Top-down parsing: LL(1) (chapter 4.4.3 - 4.4.4) (video, slides)
- Bottom-up parsing: shift-reduce parsers and LR(0) automaton (chapters 4.5, 4.6.2 - 4.6.3) (video, slides).
- October 4
- Miscellaneous comments: parse trees and parsing lookahead (chapter 4.2.4) (video, slides).
- Bottom-up parsing: SLR parsing tables and the LR(1) parsing algorithm (chapters 4.6.3 - 4.6.4) (video, slides).
- Q/A for Midterm 1.
- October 11
- Midterm 1 (in lecture) covering up to and including content on October 4.
- October 18
- Bottom-up parsing: LR(1) and LALR(1) parsing tables (chapters 4.7.1 - 4.7.4) (video, slides).
- Correction to video/slides: state 0 in the LR(1) state diagram is missing two items:
L -> . * R, $ and L -> . id, $ which should have been added from R -> . L, $.
We previously added L -> . * R, = and L -> . id, =, but whereas we were done in the LR(0) case, with LR(1) items they are different because of the lookahead.
- Not tested but for your interest: Other parsers: GLL, GLR, parser-combinators, and PEG parsing (external) (no video).
- Some interesting/useful links:
- October 25
- Intermediate Representation (miscellaneous) (video, slides)
- Introduction to data-flow analysis: reaching definitions, live variables, available expressions, busy expressions (chapter 9.2) (video, slides)
- Foundations of data-flow analysis, and Constant propagation (chapters 9.3 - 9.4) (video, slides)
- Corrections to video/slides:
- The meet of the top and bottom value (if it exists) in a lattice should be the bottom value, by the definition/properties of a lattice.
- Note that the textbook says for the transfer function, given
x = y + z, if any of y or z are not a constant (bottom), then x is not a constant.
I said if any of y or z are undefined (top), then x is top.
I believe defining the transfer function this way is ok, in that it doesn’t violate the monotonicity requirement.
- The initialization of the boundary conditions, namely
OUT[entry] for forwards analysis and IN[exit] for backwards analysis, cannot be arbitrary.
A proper value must be chosen depending on the semantics of the analysis.
The OUT (for forwards analysis) and IN (for backwards analysis) values for all other nodes in the CFG may be initialized arbitrarily,
but initializing them to the top value in the lattice gives the best solution.
- November 1
- November 8: Reading break.
- November 15
- Review for Midterm 2 (no video).
- November 22
- November 29
- Interpreters and bytecode: a look into Java (external) (video, slides).
- Garbage collection: tracing/mark-and-sweep algorithm (chapters 7.5 - 7.6) (video, slides).
- Correction: in the general procedure for a “stop the world” GC (beginning with
signal_stop_and_wait()), the first for-loop, which adds the roots to the unscanned list, should also mark each root.
- Garbage collection: short-pause/concurrent algorithms (chapters 7.7 - 7.8) (video, slides).
- Garbage collection: miscellaneous comments (external) (video, slides).
- December 6
- Computability theory (external) (video, slides).
- An argument for a strong (static) type system, including: type theory, template/generic metaprogramming, and lifetime analysis in Rust (external) (no video) (write-up).
- Undefined behaviour in C/C++ (external) (no video).
Mark Breakdown and Deadlines
Important dates are also in the Querqus calendar.
You can view them under the course syllabus or export them as an iCal feed.
- Labs: 25%
- Lab 1: 3% due September 30 (23:59) (2 weeks)
- Lab 2: 6% due October 21 (23:59) (3 weeks)
- Lab 3: 6% due November 4 (23:59) (2 weeks)
- Lab 4: 10% due December 2 (23:59) (4 weeks)
- The final day for me to submit grades is 1 week after the final exam.
You do not need to explicitly ask for an extension, but try to submit it via the terminal by December 21 23:59.
If you submit it later than that, send me an email to make sure it is received.
- Exams: 75%
- Midterm 1: 20% October 11 (in lecture starting 15:10, 2 hours) (pdf, solutions)
- The midterm covers up to and including the lecture on October 4, equivalent to video 10, i.e. including the LR(1) parsing algorithm and SLR parsing tables, but not LR(1) or LALR(1) parsing tables.
- You are allowed a single double-sided, printed or handwritten aid sheet.
- I recommend having (at least) the following procedures on your aid sheet:
- NFA from regular expressions;
- DFA from NFA;
- NULLABLE, FIRST, and FOLLOW functions;
- create an LL(1) parsing table;
- create the LR(0) states/flowchart diagram; and
- fill out an LR(1) parsing table for LR(0) and SLR.
- Additionally, you should know how to do a proof by contradiction. (Silly) example:
- Assume that eliminating left recursion is on the test and the instructor is not evil.
- Then the procedure for eliminating left recursion should be on the recommended list of items for the aid sheet.
- But the procedure for eliminating left recursion is not on the recommended list of items for the aid sheet.
- By contradiction, the assumption is false; it is not true that eliminating left recursion is on the test and the instructor is not evil.
- Equivalently, eliminating left recursion is not on the test or the instructor is evil (De Morgan’s law).
- Equivalently, if the instructor is not evil, then eliminating left recursion is not on the test (conditional disjunction).
- Midterm 2: 20% November 18 (in HA 403 from 13:10 - 15:00) (pdf, solutions)
- The midterm covers the lectures from October 18 to November 1 inclusive.
- You are allowed a single double-sided, printed or handwritten aid sheet.
- I recommend having (at least) the following procedures on your aid sheet:
- create the canonical LR(1) states/flowchart diagram (closure, goto, and compute states, FIRST of a sequence of symbols);
- merge canonical LR(1) states to LALR(1) states;
- fill out an LR(1) parsing table for canonical LR(1) and LALR(1);
- examples of data-flow analysis problems; and
- examples of “normal” code and its corresponding SSA form.
- What will be provided:
- forwards/backwards, meet, transfer functions (including gen and kill), and initialization of data-flow analyses;
- pseudocode for iterative data-flow analysis;
- definitions of lattices, partial orders, and monotonicity; and
- functions/procedures for converting code to SSA form.
- What you should additionally know:
- reasoning about control-flow graphs (e.g. drawing a CFG for pseudocode);
- carrying out iterative data-flow analysis;
- reasoning about semilattices, partial orders, monotonic functions, product lattices, and the general data-flow analysis framework; and
- reasoning about SSA form (e.g. understanding what the phi function is).
- Exercises for midterm 2.
- Correction to lecture: gen for available expressions is the expression of the statement unless the statement reassigns one of the operands of the expression.
- Final: 35% December 19 (in BA 2195 from 9:30 - 12:00) (pdf, solutions)
- You are allowed a single double-sided, printed or handwritten aid sheet.
- In general, any material covered in lectures is testable. The following are just guidelines to focus on.
- Things you should understand (not provided):
- how lexers (regular expressions/NFAs/DFAs) compare to parsers (context-free grammars);
- how to write a grammar, and produce a derivation for an input string;
- LR(1) parsing algorithm;
- reasoning about SSA form (e.g. understanding what the phi function is);
- reasoning about the domain, meet, and transfer functions for a data-flow analysis in the general, iterative algorithm framework;
- properties of a meet operator;
- definition of a partial order on a lattice;
- properties of a partial order relation;
- meet over paths vs. maximal fixed point solutions to data-flow analysis;
- atomic access orderings;
- semantics of a stack-based interpreter;
- general idea of GC;
- GC pseudocode not provided;
- why barriers are necessary for concurrent GC, and how each barrier works;
- concurrency vs. parallelism;
- tri-colour abstraction for GC;
- turing machines;
- lab 4.
- You do not need to know or write down:
- NFA construction algorithm;
- DFA from NFA;
- NULLABLE, FIRST, FOLLOW, left-factoring, creating an LL(1) parsing table or the LL(1) parsing algorithm, creating the parsing tables for any of the LR family of parsers;
- the exact definitions of the specific data-flow analyses we learned (will be provided where relevant);
- algorithm for generating IR in SSA form from an AST;
- type theory, template/generics metaprogramming, or rust topics from the last lecture;
- undefined behaviour topics from the last lecture.
- Exercises for the final exam.
In some sense, labs 2 and 3 are a single lab spanning 5 weeks; it’s just broken up to help you pace yourself.
3 weeks are given for lab 2 so you have more flexibility, but it would be recommended to finish it earlier to start on lab 3.
Tutorial Notes
Discussion Board
Piazza is available for questions and discussions: https://piazza.com/utoronto.ca/fall2022/ece467.
Announcements will be made on Querqus.
Textbook
We will be using Compilers: Principles, Techniques, and Tools by Alfred V. Aho (a UofT graduate!), Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman (fondly referred to as the “Dragon Book”).
- Instructor: Adrian (adrian dot chiu at the standard University of Toronto student email domain).
- Office hours: Monday 15:00 - 16:00 in PT 371 (Note: PT 371 is shared office space. If the door is closed, peek inside PT 372.)
- Additional office hours by appointment (email)
- TAs: Ruibin, Rishi, Ao (emails in the course syllabus on Querqus).
Please do not hesitate to contact me by email (please include ECE 467 in the subject title).
As much as you are comfortable with, you are welcome to share with me any challenges you face with the course, whether it be directly related to the course, or external factors affecting your ability to participate in and complete the course.
I am always happy to try to help students who are themselves trying to learn.
I also want to make this course as positive as an experience as possible.
I am happy to give extensions, but only if students proactively reach out to me.
Prerequisites
While the lectures do not use any specific programming language,
familiarity with programming is assumed.
In particular, this is an ECE course, so at minimum the knowledge from ECE 244 and ECE 243 is expected.
It would be beneficial to have taken at least one 3rd year kernel course in software
(e.g. ECE 344 Operating Systems or ECE 345 Algorithms and Data Structures),
if you do not have additional programming experience outside of school.
The labs are in C++, but I would not say prior knowledge of C++ is necessary.
If you have the required understanding of programming fundamentals,
learning a specific language such as C++, even from scratch, should not be a problem, at least for the scope of these labs.
I am always happy to help whenever students are ready to learn.
Update: a C++ primer has been added, which hopefully smooths over the process of learning C++ for those without prior experience.
More importantly, I believe it to be an important skill to search for and read documentation for open source software,
especially for soon-to-be-graduating 4th year students.
In particular, it is a requirement for Lab 4 to read about LLVM on your own.
Again, I am always happy to provide guidance as long as students have put in the necessary effort to learn themselves.
While not required for Lab 1 and Lab 2, I believe it to be insightful to explore the online documentation for re2c and GNU Bison.
Minimal knowledge of git would also be helpful, for your own version control.
Past Exams
Past versions of the course are not particularly reflective of this iteration of the course
(even the most recent time it was offered, in 2020).
I do not particularly recommend studying these exams, but I have collected all the past exams I can as someone will inevitably ask for it.
I will try to make clear the expectations and prepare students for my exams directly.
Last updated: 2022-12-23 09:56:36 -0500.