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


Slides and/or Notes

  1. Introduction and First Content    Blog post on Cloudflare outage (see lecture notes)
  2. Building a Scanner, from a lab 1 perspective
  3. Building a Simple Parser, from a lab 1 perspective   (corrected)

  4. Lexical Analysis, I   Chapter 2 in EaC2e
  5. Lexical Analysis, II
    Ken Thompson, Regular Expression Search Algorithm, CACM, June 1968   DOI
    Michael Rabin and Dana Scott, "Finite Automata and Their Decision Problems," IBM Journal of Research and Development, 3(2), April 1959.    DOI
  6. Lexical Analysis, III    DFA Minimization
    Excerpt from EaC3e on Hopcroft's algorithm   skip this part in EaC2e
  7. Lexical Analysis, IV    Building a Scanner from a DFA
  8. Another way to approach Kleene's construction    (Regular Expression from NFA)

  9. Parsing, I    Chapter 3 in EaC2e
    Context-free grammars and Ambiguity
  10. Parsing, II    Top-down Parsing
  11. Parsing, III
  12. Parsing, IV
  13. Parsing, V    Bottom-up Parsing
  14. Parsing, VI

  15. Local Register Allocation, Part I   Programming Assignment 2
    Excerpt from Chapter 13 in EaC3e
  16. Local Register Allocation, Part II
  17. Lab 2, Tutorial 1
  18. Lab 2, Tutorial 2

  19. Topics to be covered on the first exam
  20. Another way to approach Kleene's construction    (Regular Expression from NFA) n
  21. Practice Midterm Exam

    You are responsible on the first exam for material above this line

  22. Parsing, VII    The Canonical LR(1) Table Construction
  23. Parsing, VIII

  24. Intermediate Representations, I    Chapter 5 in EaC2e
  25. Intermediate Representations, II

  26. Computing Inside the Parser, I    Chapter 4 in EaC2e
  27. Computing Inside the Parser, II
  28. Computing Inside the Parser, III    More complex examples, plus naming and storage layout
  29. Storage Layout

  30. The Memory Hierarchy    A break from compilers for some things you should know

  31. Assignment Statements and Array References    Chapter 7 in EaC2e
    Paper mentioned in class and lecture notes:   Robert Floyd, "An Algorithm for Coding Efficient Arithmetic Operations," CACM 4(1), January 1961, pages 42-51.)
    Papers on algebraic reassociation:    Briggs & Cooper;   Cooper, Eckhardt, & Kennedy;   Draft section on Tree-Height Balancing from EaC3e
  32. Boolean and Relational Expressions
  33. Implementing Control-Flow Constructs

  34. Local Instruction Scheduling    Programming Assignment 3
    Paper mentioned in the lecture: S.S. Muchnick and P.B. Gibbons "Efficient Instruction Scheduling for a Pipelined Architecture," in Proceedings of the SIGPLAN 1986 Symposium on Compiler Construction, pages 6-11.
  35. Tutorial 1    (Nov. 6, 2020)
  36. Tutorial 2

  37. Procedure and Function Calls    Chapter 6 in EaC2e
  38. Procedure and Function Calls, II    includes displays, access links, and dope vectors
  39. Runtime Support for OOLs    includes function dispatch
    Paper mentioned in the lecture: L.P. Deutsch and A.M Schiffman, "Efficient Implementation of the Smalltalk-80 System," ACM Symposium on Principles of Programming Languages (POPL), 1984, pages 297-302.
  40. Runtime Support for Sustainable Memory Reuse    sometimes called "Garbage Collection"
  41. Generating Code for String Operations    Not presented, but important

  42. Introduction to Optimization    Local Value Numbering Algorithm
  43. Superlocal Value Numbering    Extended Basic Blocks

  44. Practice Exam for the Second Exam
    You are responsible on the second exam for material above this line

  45. Instruction Selection, Preliminaries    Chapter 11 in EaC2e
  46. Instruction Selection via Peephole Optimization
  47. Instruction Selection via Tree-Pattern Matching
    Excerpt from Chapter 11, EaC3e

  48. Instruction Scheduling Beyond Basic Blocks    Chapter 12 in EaC2e

  49. Just-In-Time Compilers    Not in EaC
    Dynamo: A Transparent Dynamic Optimization System, Vasanth Bala, Evelyn Duesterwald, and Sanjeev Banerjia, PLDI 2000
    The Java HotSpot(TM) Server Compiler, Michael Paleczny, Christopher Vick, and Cliff Click, Proceedings of JVM '01
    The "ArsTechnica" review of Dynamo cited in lecture notes.

Additional Materials

  1. Information on the ILOC Virtual Machine and its Trace Facility
  2. The Software Stack
    What happens to code after compilation?
  3. 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.


Fall 2019 Syllabus

Comp 412 Home Last modified Friday, 06-Dec-2019 08:56:59 CST.