This course is about compiler construction. Topics include

Final Exam: Wednesday April 23rd/9-11:30 AM/MC4020
Lectures:  Mondays and Fridays/10:00-11:20 AM/RCH-103 (Class Schedule)


Instructor Vijay Ganesh
Office Hours: By Appointment (DC 2530)
Leo Passos
Wenzhu Man
Office Hours: Thursdays 1 - 2:30 PM (DC  2544)
Office Hours: Wednesdays 2 - 3:30 PM (DC 2553)
Lab Instructor
Mohamed Hassan
Present during the lab hours.

Lecture Schedule

Lectures Slides and Outline
Detailed Lecture Description, Notes and References
Monday Jan 6, 2014 (Theory Lecture)
Topics Covered:
  • Course outline
  • Computability and complexity basics
  • What is a compiler? Why you need it?
  • Stages of compilation
Friday Jan 10, 2014 (Lab Lecture)
Topics covered:
  • Lab logistics
  • Basics of regular expressions
Monday Jan 13, 2014 (Theory Lecture)
Topics covered:
  • Regular expressions and non-deterministic finite automata (NFA)
  • Lexical analysis and implementation of lexical analysis
Friday Jan 17, 2014 (Lab Lecture)
Topics Covered:
  • Context-free grammars, Extended Backus-Naur Form (EBNF)
  • Parsing
  • Regular expression to NFAs to DFAs conversion
  • Lab #2
Sat Jan 18, 2014

Mon Jan 20, 2014
  • First, Follow, Predict Sets (Lecture #7)
Topics Covered:
  • Predictive parsers
  • Computing First, Follow sets
  • (Professor Rayside lecture notes will be provided soon)
Fri Jan 24, 2014
  • 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)
Mon Jan 27, 2014
  • 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
Fri Jan 31, 2014
  • 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
Mon Feb 3, 2014
Topics Covered:
  • Basics of semantic analysis
  • Scope: dynamic and static
  • Types: dynamic and static.
  • Typing rules. Type inference and checking.
Fri Feb 7, 2014
Topics Covered:
  • Type systems: inference rules
  • Abstract syntax trees (ASTs)
Mon Feb 10, 2014
Topics Covered:
  • Layout of binaries (machine code)
  • Activation records
  • Code segment, data, stack and heap
Fri Feb 14, 2014
  • 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,...)
Fri Feb 14, 2014 (review lectures)
Topics Covered:
  • Regular languages
  • Regular expressions
  • Pumping lemma
Mon Mar 3, 2014
Topics Covered:
Fri Mar 7, 2014   (review lectures)
Topics Covered:
  • Context-free languages/grammars, and their properties
  • Regular closure
  • Bottom-up parsing, Shift-reduce parsers
Mon Mar 10, 2014
Topics Covered:
  • Code generation
  • MIPS assembly
  • Stack-based machine
  • Code generation for maintaining activation records
  • Code generation for object-oriented languages
Fri Mar 14, 2014
Topics Covered:
  • Local optimizations
  • Constant folding, Copy propagation, algebraic simplification, dead code elimination,...
Mon Mar 17, 2014
Topics Covered:
  • Global constant propagation (forward analysis)
  • Global liveness analysis (backward analysis)
Fri Mar 21, 2014
  • 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,...)
Mon Mar 24, 2014
Topics Covered:
  • Quick overview of memory hierarchy
  • Register allocation problem
  • Graph k-coloring problem
  • Spilling
Fri Mar 28, 2014
Topics Covered:
  • Why we need automatic memory management (or garbage collection)
  • Mark and sweep
  • Stop and copy
  • Reference counting
Mon Mar 31, 2014
  • First sample question set
Topics Covered:
  • Questions on regular languages, regular expressions, context-free languages
Fri April 4, 2014
  • Second sample question set
Topics Covered:
  • Questions on CFGs, parsers, global optimizations, register allocation, ASLR
Wed Apr 16, 2014
  • Third sample question set
Topics Covered:
  • Liveness analysis, register allocation, new questions from previously covered topics

Acknowledgements: The course material is primarily based on the textbook "Crafing a Compiler" and books by Professor Derek Rayside. The lecture material is based on the slides by Professor Alex Aiken of Stanford University and Professor Costa Busch of LSU with their permission. Occasionally, I may use other appropriate papers/books, which will be appropriately acknowledged.