Langages de programmation et compilation 2025-2026

Cours donné aux élèves de première année à l'École Normale Supérieure.

• Cours le vendredi de 8:30 à 10:30 en salle E. Noether (ex U ou V)
  (voir moodle)
• TDs le jeudi (15h30 à 17h00) ou le vendredi (10h45 à 12h15) en salle INFO 3 NIR avec Samuel Vivien
  
• Évaluation : un examen + un projet

Cours

• Cours 1 (26 septembre 2025) : aperçu de la compilation / assembleur x86-64
  • transparents
  • à propos du problème des N-reines :
    • le code C / le code x86-64
    • de la lecture : Henry S. Warren Hacker's Delight (à la bibliothèque)

• Cours 2 (3 octobre 2025) : syntaxe abstraite / sémantique / interprètes
  • transparents

• Cours 3 (10 octobre 2025) : analyse lexicale
  • transparents
  • exemple ocamllex : caml2html.mll

• Cours 4 (17 octobre 2025) : analyse syntaxique 1/2
  • transparents

• Cours 5 (24 octobre 2025) : analyse syntaxique 2/2
  • transparents
  • le fichier arith_expr.mll utilisé au début du cours

• pas de cours le vendredi 31 octobre (vacances Toussaint)

• Cours 6 (7 novembre 2025) : typage
  • transparents

• Cours 7 (14 novembre 2025) : mode de passage des paramètres
• Cours 8 (21 novembre 2025) : compilation des langages fonctionnels
• Cours 9 (28 novembre 2025) : compilation des langages objets
• Cours 10 (5 décembre 2025) : compilateur optimisant, partie 1
• Cours 11 (12 décembre 2025) : compilateur optimisant, partie 2
• Cours 12 (19 décembre 2025) : allocation mémoire

TD

• groupe 1 le vendredi 10h45 - 12h15
• groupe 2 le jeudi (de la semaine suivante) 15h30 - 16h45

Séances :

• TD 1 (26 sep/2 oct) : Assembleur x86-64
• TD 2 (3/9 oct) : Interprète mini-Python
• TD 3 (10/16 oct) : Construction d'automates déterministes à partir d'expressions régulières
• TD 4 (17/23 oct) : Analyse syntaxique d'un petit langage
• TD 5 (24 oct/6 nov) : Analyse descendante
• pas de TD les 30 et 31 octobre (vacances Toussaint)
• TD 6 (7/13 nov) : Algorithme W
• TD 7 (14/20 nov)
• TD 8 (21/27 nov)
• TD 9 (28 nov/4 déc)
• TD 10 (5/11 déc)
• TD 11 (12/18 déc)
• TD 12 (19 déc/8 jan)

Projet

Sujet (version 1 - 22 octobre 2025)

Quelques tests sont fournis (les télécharger : tests-22-oct.tar.gz). Ce script shell peut être utilisé pour automatiser les tests, avec la syntaxe ./test -n binaire-compilo où n vaut 1 (tests parseur), 2 (tests typage) ou 3 (tests production de code).

Examen

Archives : janvier 2025 (corrigé) / janvier 2024 (corrigé) / janvier 2023 (corrigé) / janvier 2022 (corrigé) / janvier 2021 (corrigé) / janvier 2020 (corrigé)

Liens / Bibliographie

Outils

• Assembleur x86-64
  • des ressources (en anglais) sur cette page d'Andrew Tolmach et en particulier ces notes
  • le fascicule x86-64 Machine-Level Programming de Bryant et O'Hallaron (en anglais)
  • le debugger Nemiver fonctionne sur du code x86-64 (exécution pas à pas, visualisation des registres, etc.)
  • le site Compiler Explorer permet de comparer facilement le code assembleur produit par de nombreux compilateurs

• Pour jouer avec d'autres architectures :
  • MIPS : simulateurs MARS et SPIM (doc)
  • RISC-V : simulateur/debugger Arrakis (doc)

• OCaml :
  • vous trouverez de nombreuses ressources sur ocaml.org
  • pour travailler à l'ENS ou sur vos machines, voici quelques suggestions d'environnement de travail OCaml
  • en français : un petit polycopié de mise à niveau OCaml (et une version à l'italienne pour économiser du papier en cas d'impression), en complément du cours et du TP de la semaine de formation intensive
  • en anglais : le livre Learn Programming with OCaml

• Menhir, un outil d'analyse syntaxique LR pour OCaml (qu'on peut l'installer avec opam)
  • manuel
  • Cairn, un outil pour visualiser l'analyse LR réalisée par Menhir

• pour les débutants : une brève introduction au terminal GNU/Linux et une brève documentation des commandes les plus utiles

Cartes de référence

• OCaml : langage / bibliothèque / outils / opam (merci à OCamlPro)
• Emacs : général / mode Tuareg pour OCaml

Ouvrages en rapport avec le cours

• Alfred V. Aho, Monica S. Lam, Ravi Sethi et Jeffrey D. Ullman Modern Compilers: Principles, Techniques, and Tools.
  Dit « le dragon ». Traduit en français (Compilateurs : principes, techniques et outils).
• Benjamin C. Pierce Types and Programming Languages
• Randal E. Bryant et David R. O'Hallaron Computer Systems: A Programmer's Perspective

For foreign students not yet fluent in French

• A tiny French-English dictionary
• a rough correspondence between the lectures and chapters from the books above (which are in English):

  	Lecture	Chapters
  1	Assembly	Bryant & O'Hallaron 3
  2	Semantics	Pierce 3-4-5
  3	Lexical analysis	Dragon 3
  4-5	Syntactic analysis	Dragon 4
  6	Typing	Pierce 8-9-10 et 22
  12	Memory allocation	Bryant & O'Hallaron 9