This page contains the log of the topics of the Compiler Construction Course 1 and Compiler Construction Course 2 for class EPITA 2009 (i.e., from February 2007 to July 2007). The topic was started with the Formal Languages Lecture; see the ThlLog2009.

Week 1: 2007-02-27: Introduction to the Project, Development Tools (Roland, Akim)

  1. The Tiger Project
    1. Ressources (
      1. Assignments (
      2. Appel's books
      3. Tiger Compiler Reference Manual (
      4. epita.cours.compile
    2. Goals (C++, OO, DP, Management, Several Iterations, Testing, Documenting, Maintaining, Fixing, Understanding Computers, English)
    3. Non goals (Compiler Construction)
    4. Rules of the Game
      1. No copy between groups
      2. Tests are part of the project (test cases and frameworks should not be exchanged)
      3. Fixing mistakes earlier is better
      4. Work between groups is encouraged as long as they don't cheat
    5. Tests
      1. Tests matter
      2. Rules
        1. A bug => a test
        2. A suspicious behavior => one or several tests to isolate it
        3. Don't throw away tests!
        4. Don't exchange tests! (bis repetita)
    6. C Compilation model (cpp, cc1, as, ld)
    7. The Tiger Compiler pipe (annoted with tools and steps)
      1. Front-end: TC-0 - TC-6 (mandatory part)
      2. Back-end: TC-7 - TC-9 (optional part)
      3. Width of a compiler pipe (line, function, compilation unit)
    8. Misc: students should overcome Make, Makefiles and seperate compilation, etc.
  2. Development Tools (See the lecture notes:

dev-tools.pdf and dev-tools-handout-4.pdf)

Week 2: 2007-03-06: History of Programming Languages, Early Computers (Akim)

Week 3: 2007-03-13: Abstract Syntax (Roland)

(Week 4: 2007-03-20: Canceled)

Week 5: 2007-03-27: Leopard, OOP (intro), Misc. on LC-2, Scanner (late course), Names and Bindings (Roland)

  1. Introducing Leopard
    1. Renaming of the language and the project
    2. New features: object-oriented programming
      1. New elements of (concrete) syntax
      2. New nodes of the abstract syntax
      3. A bit of object semantics
      4. Examples
  2. LC-2: Miscellaneous
    1. Why, DefaultVisitor
    2. std::ios_base::xalloc, lib/misc/indent.{hh,cc}, misc::xalloc
  3. Scanner (late course). See the lecture notes, scanner.pdf and


  1. Symbols, Identifiers and Bindings. See the lecture notes, names.pdf and


Week 6: 2007-04-03: Names (cont.), Q&A on LC-2, AST transformations in concrete syntax, Object-Oriented Programming (Roland)

  1. Symbols, Identifiers and Bindings (cont.). See the lecture notes, names.pdf and


  1. (Questions and) Anwers on LC-2
    1. C++ traits
    2. lib/misc/select-const.hh, and its use in ast::GenVisitor and ast::GenDefaultVisitor
    3. DefaultVisitor::decs_visit
    4. misc/indent.{hh,cc}
  2. Removing the syntactic sugar in concrete syntax
    1. Why it matters
    1. An example: desugaring boolean operators (&= and =||)
      1. in abstract syntax
      2. in concrete syntax
    1. How it works: TWEASTS (Text With Embedded Abstract Syntax Trees, ast::Tweast), metavariables (ast::MetavarMap), and their use from the parser.
    2. More desugaring
      1. astclone::Cloner
      2. related features in the Leopard Compiler (modules desugar and inline)
      3. a (quick) example: turning for loops into while loops
  1. Object-Oriented Programming. See the lecture notes, object.pdf

and object-handout-4.pdf

Week 7: 2007-04-10: Type-checking (Roland)

  1. Types. See the lecture notes, type-checking.pdf

and type-checking-handout-4.pdf

  1. Sequent Calculus
    1. In English: "If alpha is of type Int in the context Gamma and beta is of type Int in the context Gamma,

then alpha + beta is of type Int in the context Gamma."

    1. Using symbols (where ||- ("tee" or "turnstile") is the symbol meaning "yields" or "proves"):

 %TABLE{tableborder="0" tablerules="rows" cellpadding="3" cellspacing="3" databg="none"}%

Γ |- α : Int    Γ |- α : Int
Γ |- α + β : Int
    1. Type inference
      1. (a_ ? _b : _c_) > 0
      2. (a_ ? _b : f_ (_b)) > 0
      3. (a_ ? _b : f_ (_c)) > 0
  1. Questions and Anwers on LC-4
    1. solving forward references and mutual recurrences: the dual-visit scheme (visitDecHeader, visitDecBody)
    2. Hierarchy of types (src/types/)

Warning: Display title "CMP 2" overrides earlier display title "CMP 1".

Week 1: 2007-05-03: Intermediate languages, part 1 (Roland)

Week 2: 2007-05-10: Intermediate languages, part 2 (Roland)

Week 3: 2007-05-15: LC-5, Canonization (LC-6) (Roland)

Week 4: 2007-05-24: RISC and MIPS (Roland)

Week 5: 2007-06-07: Instruction selection (LC-7) and liveness analysis (LC-8) (Roland)

Week 6: 2007-06-14: Register allocation (Roland)