CMP 2

From LRDE

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




Lecture 1: Friday 2007-11-23 (4 hours): Introduction to the Project, Development Tools (%roland%)

  1. The Tiger Project.
    1. Ressources (http://www.lrde.epita.fr/~akim/ccmp/).
      1. Assignments (http://www.lrde.epita.fr/~akim/ccmp/assignments.html).
      2. Appel's books.
      3. Tiger Compiler Reference Manual (http://www.lrde.epita.fr/~akim/ccmp/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. Width of a compiler pipe (line, function, compilation unit).
    8. Compilers handling multiple input (sources languages) and multiple outputs (target assembly languages/processors).
      1. The case of GCC.
      2. Factoring the compiler components: intermediate representation(s).
      3. Front-end and back-ends.
    9. The Tiger Compiler pipe (annotated with tools and steps).
      1. Front-end: TC-0 - TC-6 (mandatory part).
      2. Back-end: TC-7 - TC-9 (optional part).
    10. 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.

  1. A first glance at Abstract Syntax Trees. See the lecture notes:

ast.pdf and ast-handout-4.pdf, pages 1 to 13.

Lecture 2: Friday 2007-12-07 (4 hours): Scanner and Abstract Syntax (%roland%)

  1. Scanner. See the lecture notes, scanner.pdf and

scanner-handout-4.pdf.

  1. Abstract Syntax. See the lecture notes, ast.pdf and

ast-handout-4.pdf (sections 1 and 2).

Lecture 3: Monday 2007-12-10 (4 hours): Abstract Syntax, cont. (%roland%)

  1. Abstract Syntax (cont.). See the lecture notes, ast.pdf and

ast-handout-4.pdf (sections 3 and 4).

  1. Short overview of the TC-1 tarball.

Lecture 4: Thursday 2007-12-13 (2 hours): More on AST Visitors (%roland%)

  1. More on Visitors.
    1. Visitor (reminder).
    2. DefaultVisitor.
    3. Handling the constness of the visited tree: ConstVisitor and DefaultConstVisitor.
    4. Factoring Visitors implementation w.r.t. this constness: select_const, GenVisitor<Const> (and GenDefaultVisitor<Const>); first example of a C++ template metaprogramming technique.
  2. Implementations of polymorphic method calls (dynamic dispatch).
    1. The C++ approach: virtual tables.
    2. The SmartEiffel (and Tiger) approach: close-world assertion and comprehensive dispatch based on tests (if / switch).
  3. Tiger and Panther (subset of Tiger w/o object constructs).
    1. The path from "AST + bindings + types" to HIR: translation, TC-5 (reminder).
    2. Two flavor of the language: with object constructs (Tiger) and without (Panther); options --object-*.
    3. Handling object constructs before the translation: object desugaring (Tiger -> Panther).
    4. The need for two Visitor hierarchies before the translation.
      1. Using inheritance to factor...
      2. ...but a naive approach doesn't work.
      3. Adding dummy methods for non-object Visitors.
      4. Factoring using a mixin-based approach: NonObjectVisitor.
      5. Handling the constness: NonObjectConstVisitor and GenObjectConstVisitor<Const>.

Lecture 5: Thursday 2007-12-20 (4 hours): Names, identifiers and bindings (%roland%)

Lecture 6: Friday 2007-12-21 (4 hours): 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. Examples of type rules: addition of 2 integers, if-then-else, if-then, addition of 3 integers, comparison of two variables, etc.
    2. Type inference
      1. (a_ ? _b : _c_) > 0
      2. (a_ ? _b : f_ (_b)) > 0
      3. (a_ ? _b : f_ (_c)) > 0
  2. Some details on the implementation of types and type-checking within the Tiger Compiler.
    1. Hierarchy of types (src/type/)
      1. src/type/README.
      2. Implementing atomic types: singletons.
      3. Resolving aliased types: Named and actual().
    2. Insight of some visit methods from the TypeChecker.


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


Lecture 1: Monday 2008-02-11 (2 hours): Intermediate languages, part 1 (%roland%)

Lecture 2: Monday 2008-02-25 (2 hours): Intermediate languages, part 2 (%roland%)

Lecture 3: Monday 2008-03-10 (2 hours): TC-5, Canonization (TC-6) (%roland%)

Lecture 4: Wednesday 2008-04-23 (2 hours): RISC, MIPS, Instruction Selection (TC-7) (%roland%)

Lecture 5: Monday 2008-04-28 (2 hours): Liveness Analysis (LC-8), Register Allocation, part 1 (TC-9) (%roland%)

Lecture 6: Thursday 2008-05-15 (2 hours, shared with TYLA): Register Allocation, part2 (TC-9), Subprograms (%roland%)


-- %roland% - 16 May 2008

Retrieved from "https://www.lrde.epita.fr/index.php?title=Courses/CcmpLogIng2010&oldid=8209"