This course is about compiler construction. Topics include

• Basics (Lexical Analysis and Parsing): What is a Compiler? Stages of Compilation. Lexical Analysis. Symbol Tables. Parsing
  
• Formal Languages: Regular Languages, Context-free Grammars,...
• Different Categories of Programming Languages: Imperative, Declarative,...
  
• Type Checking: What is typing? Why is it useful? Different forms of Typing
• Compiler Optimizations and Code Generation: Static analysis for optimization
  
• Runtime Support
  

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

Staff

Instructor	Vijay Ganesh	Office Hours: By Appointment (DC 2530)
TAs	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

Date	Lectures Slides and Outline	Detailed Lecture Description, Notes and References
Monday Jan 6, 2014 (Theory Lecture)	Course outline	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)	Lab #1: Chapters 0 and 1 of the Lab Manual Lecture #1-#2 slides (Courtesy Jon Eyolfson)	Topics covered: Lab logistics Basics of regular expressions
Monday Jan 13, 2014 (Theory Lecture)	Lecture #3 (Lexical Analysis) Lecture #4 (Implementation of Lexical Analysis)	Topics covered: Regular expressions and non-deterministic finite automata (NFA) Lexical analysis and implementation of lexical analysis
Friday Jan 17, 2014 (Lab Lecture)	Lecture #4 continued (NFA-DFA, RE-DFA) Lecture #5 (Parsers) Lecture #6 (Recursive-descent parsers) Lab #2: Chapter 2 of the Lab Manual	Topics Covered: Context-free grammars, Extended Backus-Naur Form (EBNF) Parsing Regular expression to NFAs to DFAs conversion Lab #2
Sat Jan 18, 2014 (assignment)	Assignment on regular expressions and DFAs
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	Semantic analysis (Lecture #11)	Topics Covered: Basics of semantic analysis Scope: dynamic and static Types: dynamic and static. Typing rules. Type inference and checking.
Fri Feb 7, 2014	Semantic analysis part 2 (Lecture #12)	Topics Covered: Type systems: inference rules Abstract syntax trees (ASTs)
Mon Feb 10, 2014	Runtime environment (Lecture #13)	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)	Regular languages review (Lecture #15)	Topics Covered: Regular languages Regular expressions Pumping lemma
Mon Mar 3, 2014	Lab 6 & 7 (Lecture #16)	Topics Covered: Java Parboiled Parsing Expression Grammars Paper on Parsing Expression Grammars Lab 6 & 7 (Visitor vs. Interpreter Design Pattern)
Fri Mar 7, 2014   (review lectures)	Context-free languages/grammar review (Lecture #17) Bottom-up parser review (Lecture #18)	Topics Covered: Context-free languages/grammars, and their properties Regular closure Bottom-up parsing, Shift-reduce parsers
Mon Mar 10, 2014	Code generation (Lecture #19)	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	Local code optimization (Lecture #20)	Topics Covered: Local optimizations Constant folding, Copy propagation, algebraic simplification, dead code elimination,...
Mon Mar 17, 2014	Global analysis and code optimization (Lecture #21)	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	Register allocation (Lecture #22)	Topics Covered: Quick overview of memory hierarchy Register allocation problem Graph k-coloring problem Spilling
Fri Mar 28, 2014	Memory management (Lecture #23)	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.