CS 426

---

Class Notes

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 and notify you via Piazza, generally at least the day before class. Print these out after 5pm the day before we start each new topic in 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. You can do this exercise with any input string you like, legal or illegal.
    • 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

• Register Allocation

• Instruction Scheduling

• Dataflow Analysis

• Global Optimizations.
  Also read the paper "Constant Propagation With Conditional Branches", on the Papers page.

---