This is an introductory course on compiler construction. Topics include formal languages (regular and context-free), categories of programming languages, lexical analysis and parsing, type checking, static analysis, compiler optimizations, code generation, memory organization and runtime support.

Staff:

Instructor Vijay Ganesh
 Office Hours: By Appointment (DC 2530)
TAs
 Nomair Naeem (nanaeem@uwaterloo.ca)
Riyad Parvez (riyad.parvez@gmail.com)
Reza Babaee (rbabaeec@uwaterloo.ca)
 Office Hours: Tuesdays 12-1:00 PM (DC 3548)
Office Hours: Fridays 12-1:30 PM (DC 2634)
Office Hours: Tuesdays 1-2:30 PM (E5 4111)
Lab Instructor
 Tiuley Alguindigue (talguind@uwaterloo.ca)
 Present during the lab hours. See Class Schedule for lab hours.

Lectures:  Mondays/Fridays from 10:00 to 11:20 AM in QNC 1502
Labs: Tue/Wed/Thursdays in E2 2363
Date
 Lectures Slides and Outline
 Detailed Lecture Description, Notes and References
Monday May 5
 Topics Covered:
  • Course outline
  • What is a compiler? Why you need it?
  • Stages of compilation
  • Computability and complexity basics
Friday May 9
 Topics covered:
  • Basics of formal language theory and computability
  • Turing machines, halting problem, undecidability
Monday May 12
Tuesday May 13

 Topics covered:
  • Regular languages, non-deterministic finite automata (NFA) and regular expressions
  • Context-free languages, context-free grammars
Friday May 16

 Topics Covered:
  • Context-free grammars, Extended Backus-Naur Form (EBNF)
  • Parsing
  • Regular expression to NFAs to DFAs conversion
  • Lab #2
Monday
  • First, Follow, Predict Sets (Lecture #7)
 Topics Covered:
  • Predictive parsers
  • Computing First, Follow sets
  • (Professor Rayside lecture notes will be provided soon)
Friday
  • Predict Sets, LL(1) parsers (Lecture #7)
  • Lab #3: 3a. parse tree vs AST vs subclass hierarchy. 3b. equals() vs isomorphic() vs equivalent()
 Topics Covered:
  • LL(1) parsers
  • Computing First, Follow, Predict sets
  • (Professor Rayside lecture notes will be provided soon)
Monday
  • Revisiting Ambiguity in Context-free Grammars (Lecture #8)
  • Introduction to Bottom-up Parsing (Lecture #9)
 Topics Covered:
  • Ambiguity, precedence, associativity
  • Bottom-up parsing, LR, LALR
Friday
  • Bottom-up parsers continued (Lecture #10)
  • Lab #4: Simplifier for the language F
 Topics Covered:
  • Handles, shift-reduce parsers, shift-reduce, reduce-reduce conflicts
  • How to check equivalence of Boolean formulas using SAT solvers
Monday

 Topics Covered:
  • Basics of semantic analysis
  • Scope: dynamic and static
  • Types: dynamic and static.
  • Typing rules. Type inference and checking.
Friday

 Topics Covered:
  • Type systems: inference rules
  • Abstract syntax trees (ASTs)
Monday

 Topics Covered:
  • Layout of binaries (machine code)
  • Activation records
  • Code segment, data, stack and heap
Friday
  • Memory layout, unsafe programming languages and computer security (Lecture #14)
 Topics Covered:
  • Revisiting memory layout
  • Buffer overflows
  • Control-hijack attacks (stack-smashing, ret-2-libc,...)
  • Defense mechanisms (ASLR,...)
Friday
(review lectures)
 Topics Covered:
  • Regular languages
  • Regular expressions
  • Pumping lemma
Monday
 Topics Covered:
Friday
(review lectures)
 Topics Covered:
  • Context-free languages/grammars, and their properties
  • Regular closure
  • Bottom-up parsing, Shift-reduce parsers
Monday
 Topics Covered:
  • Code generation
  • MIPS assembly
  • Stack-based machine
  • Code generation for maintaining activation records
  • Code generation for object-oriented languages
Friday
 Topics Covered:
  • Local optimizations
  • Constant folding, Copy propagation, algebraic simplification, dead code elimination,...
Monday
 Topics Covered:
  • Global constant propagation (forward analysis)
  • Global liveness analysis (backward analysis)
Friday
  • Memory layout, control-hijack attacks and computer security review (Lecture #14)
 Topics Covered:
  • Revisiting memory layout
  • Buffer overflows
  • Control-hijack attacks (stack-smashing, ret-2-libc,...)
  • Defense mechanisms (ASLR,...)
Monday
 Topics Covered:
  • Quick overview of memory hierarchy
  • Register allocation problem
  • Graph k-coloring problem
  • Spilling
Friday
 Topics Covered:
  • Why we need automatic memory management (or garbage collection)
  • Mark and sweep
  • Stop and copy
  • Reference counting

Acknowledgements: The lecture material are modifications of slides by Professor Alex Aiken of Stanford University and Professor Costa Busch of LSU with their permission. The lab material is based on a lab book written by Professor Derek Rayside of Waterloo. Occasionally, I may use other appropriate papers/books, with appropriate acknowledgements and links.