Languages and Compilation

Course Description

Lectures

• Lecture 1 (February 12, 2025) : Introduction to the course

• Lecture 2 (February 19, 2025) :
  • Abstract Syntax, Semantics, and Interpreters
  • Demo: While Language Interpreter in OCaml

• Lecture 3 (February 26, 2025) :
  • Lexical Analysis
  • 3 Demos of using OCamllex tool

• Lecture 4 (March 5, 2025) : Parsing, Part 1: CFGs, Top-Down Parsing

• Lecture 5 (March 12, 2025) : Parsing, Part 2: Bottom-Up Parsing - Menhir

• Lecture 6 (March 19, 2025) : Typing (TBD)

• Lecture 7 (March 26, 2025) : Assembly (TBD)

• Lecture 8 (April 2, 2025) : Evaluation Strategies and Parameter Passing Modes (TBD)

• Lecture 9 (April 9, 2025) : Compilation of Object-Oriented Languages (TBD)

• (April 16, 2025) : No lecture that week

• Lecture 10 (April 23, 2025) : Code Generation 1/3 (TBD)

• Lecture 11 (April 30, 2025) : Code Generation 2/3 (TBD)

• Lecture 12 (May 5/6, 2025) : Code Generation 2/3 (TBD)

• (May 14, 2025) : Preparation for exam

Lab Sessions

• Lab 1 (February 12, 2025) :

  • Installing OCaml (see also the chapter 1 in the book below)

  • read 1-60 pages the textbook on OCaml

  • Demo file (Playing a Music Score)
  • Brief Introduction to OCaml (by Jean-Christophe Filliâtre)

• Lab 2 (February 19, 2025) :
  • Handwritten exercises on big-step operational semantics
  • Solutions to handwritten exercises
  • Arith mini-language in OCaml

• Lab 3 (February 26, 2025) : Interpreter for Mini-Python ( Solutions )
• Lab 4 (March 5, 2025) :
• Handwritten exercises on CFG and LL(1) parser
• Solutions to handwritten exercises
• Implementing a Top-down Parser
• Implementing a Top-down Parser solutions
• Lab 5 (March 12, 2025) : Mini-Turtle

• Lab 6 (March 19, 2025) : Implementing a Typechecker for a fragment of C. (TBD)

• Lab 7 (March 26, 2025) : Assembly Language - MIPS code generation for a small language (TBD)
• Lab 8 (April 2, 2025) : Help with the projects

• Lab 9 (April 0, 2025) : Help with the projects

• No lab (April 16, 2025) : No lab that week

• Lab 10 (April 23, 2025) : TBD

• Lab 11 (April 30, 2025) : TBD

• Lab 12 (May 5/6, 2025) : help with projects

• Lab 11 (May 14, 2025) : preparation for exam

Ressources

Links useful for the course and the projects

• If you are going to use x86-64 assembler
  • the easier is to compile the generated assembly by C compiler, e.g. gcc
  • about x86-64 Andrew Tolmach page and in particular these notes
  • a pdf x86-64 Machine-Level Programming by Bryant & O'Hallaron
  • debugger gdb works on x86-64 (step by step execution, visualisation of registers, etc.) ; see tutorial
  • the online tool godbolt.org allows to compare easily the assembly code produced by various compilers

• OCaml : in addition to OCaml compiler, you will need ocamllex and menhir.
  • some suggestions for the OCaml environment
  • you will find useful info on ocaml.org
  • lexical analyzer generator ocamllex documentation
  • Menhir, parser more powerful than ocamlyacc (manual)

• Java : in addition to Java compiler,you will need JFlex and Cup.
  • JFlex, lexical analyzer generator (also known as scanner generator) for Java
  • Cup, LALR parser generator for Java

Reference sheets

• OCaml : language / stdlib / tools
• Emacs : general / Tuareg for OCaml

Bibliography for the course

• Alfred V. Aho, Monica S. Lam, Ravi Sethi et Jeffrey D. Ullman Modern Compilers: Principles, Techniques, and Tools.
• Benjamin C. Pierce Types and Programming Languages
• Randal E. Bryant et David R. O'Hallaron Computer Systems: A Programmer's Perspective