CMP 2

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 (http://www.lrde.epita.fr/~akim/compil/)
      1. Assignments (http://www.lrde.epita.fr/~akim/compil/assignments.html)
      2. Appel's books
      3. Tiger Compiler Reference Manual (http://www.lrde.epita.fr/~akim/compil/tiger.html)
      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 3: 2007-03-13: Abstract Syntax (Roland)

• See the lecture notes, ast.pdf and ast-handout-4.pdf

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

scanner-handout-4.pdf

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

names-handout-4.pdf

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

names-handout-4.pdf

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. 1. An example: desugaring boolean operators (&= and =||)

1. 1. 1. in abstract syntax
      2. in concrete syntax
   2. How it works: TWEASTS (Text With Embedded Abstract Syntax Trees, ast::Tweast), metavariables (ast::MetavarMap), and their use from the parser.
   3. 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
2. 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. 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. 1. Type inference
      1. (a_ ? _b : _c_) > 0
      2. (a_ ? _b : f_ (_b)) > 0
      3. (a_ ? _b : f_ (_c)) > 0
2. 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/)

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

• Intermediate languages. See the lecture notes, intermediate.pdf and intermediate-handout-4.pdf (pages 1 to 48)

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

• Intermediate languages. See the lecture notes, intermediate.pdf and intermediate-handout-4.pdf (pages 49 to 82)

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

• Intermediate languages. See the lecture notes, intermediate.pdf and intermediate-handout-4.pdf (from page 82 up to the end)

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

• Subprograms. See the lecture notes, subprograms.pdf and subprograms-handout-4.pdf
• The RISC architecture and the MIPS R2000 assembly language. See the lecture notes, instr-selection.pdf and instr-selection-handout-4.pdf (first half)

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

• Instruction selection. See the lecture notes, instr-selection.pdf and instr-selection-handout-4.pdf (second half)
• Samples of MonoBURG inputs from the Leopard Compiler.
• Liveness analysis. See the lecture notes, liveness.pdf and liveness-handout-4.pdf

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

• Register allocation. See the lecture notes, regalloc.pdf and regalloc-handout-4.pdf