CS 426 — Class Notes
Fall 2025
The entire set of lecture notes for the semester are included below. Slides for topics that have not been covered yet are the versions used last year, and may describe slightly different assignments. If any slides are updated, we will mark them with the date and time they were uploaded, and notify you via the newsgroup, generally at least the day before class.
Note that these slides are organized by topic, not by lecture. Because we spend unpredictable amounts of time on questions and answers in classes, I do not try to predict exactly how much each lecture will cover, nor do I try to finish a topic on lecture boundaries.
- Overview of CS 426
-
Sources You Can Use to Review Scanning and Parsing
- Cooper and Torczon, Chapters 2 and 3, or Aho, Lam, Sethi and Ullman, Chapters 3 and 4.
- Lexical Analysis or Scanning
- Context Free Grammars and Ambiguity
- Bottom-up Parsing
- Additional Material on LR parsing
- Review of LR parsing
- A simple exercise in using a parse table to perform a bottom-up parse.
- A solution to the exercise for input string id – id
- Some notes on canonical LR(1) table construction
-
Intermediate Representations.
Also read the paper “XIL and YIL: The Intermediate Languages of TOBEY” on the Papers page. -
Runtime Environments.
Also see the 2-page handout on the Sparc V9 stack frame. -
Intermediate Code Generation.
Also read the paper “An Overview of the PL.8 compiler” on the Papers page. - Optimization Basics
- Dataflow Analysis
-
Global Optimizations.
Also read the paper “Constant Propagation With Conditional Branches” on the Papers page. - Register Allocation
- Instruction Scheduling