COMP 412: Compiler Construction for Undergraduates
Keith Cooper
Zoran Budimlic
Department of Computer Science
Rice University
Houston, Texas, USA
Fall 2018: HRZ 212 on Monday, Wednesday, and Friday at 11:00am

Notes


Slides and/or Notes

  1. Overview of Course and Compilation
  2. Building a Scanner (from a lab 1 perspective)
  3. Building a Parser (from a lab 1 perspective)

  4. Lexical Analysis, I    Chapter 2 in the text
    Draft version of Chapter 2 from EaC2e
  5. Lexical Analysis, II    Thompson's Construction and the Subset Construction
  6. Lexical Analysis, III    DFA Minimization
  7. Lexical Analysis, IV    Implementing Scanners (and Scanner Generators)

  8. Parsing, I    Chapter 3 in EaC2e    Grammars, derivations, parse trees, ambiguity
  9. Parsing, II    Recursion, precedence, and associativity
  10. Parsing, III    General left recursion algorithm, FIRST, FOLLOW, LL(1), Left factoring

  11. Local Register Allocation Lab 2    Slides cover two lectures
    (see also the Projects page)

  12. Parsing, IV    FIRST, FOLLOW, LL(1) Parsing
  13. Parsing, V    Bottom-up Parsing, Shift-Reduce, The Magic of Handles
  14. Parsing, VI    Table-driven LR(1) parsers
  15. Parsing, VII    The Construction of the Canonical Collection of Sets of LR(1) Items
  16. Parsing, VIII    Second example of LR table construction, shrinking tables, and more

  17. Intermediate Representations    Chapter 5 in EaC2e    Slides cover two lectures

    Practice Exam for the Midterm

    Material above this line is covered on the midterm exam


    Material below this line is covered on the final exam

  18. Computing Inside the Parser    Excerpts from Chapter 4 in EaC2e    Introduction to syntax-directed translation
  19. Syntax-Directed Translation, II
  20. Translation Continued    Excerpts from Chapters 4, 5, and 7 in EaC2e    Code Shape
    Draft text on tree-height balancing algorithm    (tentative section 8.4.2
    Paper mentioned in class and lecture notes:   Robert Floyd, "An Algorithm for Coding Efficient Arithmetic Operations," CACM 4(1), January 1961, pages 42-51.)

  21. Name Spaces and Symbol Tables    Excerpts from Chapters 5 and 6 in EaC2e
  22. Name Spaces of OOLs and Storage Layout    two distinct subjects; confusing title

  23. The Processor's Memory Hierarchy    Not in EaC2e    Caches & Address Translation

  24. Handling Assignment    Back to Chapter 7
  25. Assignments, II
    Column mentioned in the lecture: Poul-Henning Kamp, "The Most Expensive One-byte Mistake", ACM Queue, July 25, 2011

  26. Instruction Scheduling (Lab 3)    Dependence graphs, greedy scheduling, memory conflicts
    Paper mentioned in lecture:    Gibbons and Muchnick's classic paper (1986) "Efficient Instruction Scheduling for a Pipelined Architecture," in Proceedings of the SIGPLAN 1986 Symposium on Compiler Construction

  27. Translating Control-Flow Structures    Back to Chapter 7    Boolean and Relational Values, Conditionals, Loops, Case Statements

  28. Function and Procedure Calls    Chapter 6 in EaC2e    Linkage Conventions, Activation Records
  29. Function and Procedure Calls, II

  30. Runtime Support for Algol-like Languages    Static Coordinates, Access Links, Displays    Distribution of Grades for Midterm Exam
  31. Runtime Support for Object-Oriented Languages

  32. Local Value Numbering    Chapter 8 in EaC2e    redundancy elimination, scope of optimization

  33. Instruction Selection: Introduction    Chapter 11 in EaC2e    code generation definitions, peephole optimization & matching
  34. Instruction Selection via Peephole Matching

  35. Instruction Scheduling Beyond Basic Blocks    Chapter 12 in EaC2e    Superlocal Scheduling, Superblock cloning; Trace Scheduling

  36. Global Register Allocation    Chapter 13 in EaC2e    Graph coloring, live analysis, copy propagation / coalescing    Slides cover two lectures

  37. Just-in-time Compilers    not in EaC2e

  38. Practice final exam is available

Additional Materials

  1. Lab 2 Tutorial 1
  2. Lab 2 Tutorial 2
  3. Lab 3 Tutorial 1
  4. Lab 3 Tutorial 2
  5. Information on the ILOC Virtual Machine and its Trace Facility
  6. The Software Stack
    What happens to code after compilation?
  7. Notes on Sustainable Memory Use in Java    (i.e., garbage collection)
    It is hard to understand your Java lab's performance without understanding garbage collection and its impact on running times.

Syllabus

Fall 2018 Syllabus


Comp 412 Home Last modified Friday, 30-Nov-2018 10:47:45 CST.