Langages de programmation et compilation 2020-2021

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)
  Dans la limite de 22 places, et donc en alternance (voir moodle)
• TDs le jeudi ou le vendredi, de 10h45 à 12h15 en salles INFO 3 et 4 NIR avec Basile Clément
  
• Évaluation : un examen + un projet

Cours

• Cours 1 (25 septembre 2020): mise à niveau OCaml
  • transparents
  • code OCaml de la démo : wall.ml
  • Il y a un polycopié spécifique pour ce premier cours. (Version à l'italienne si vous souhaitez l'imprimer.)

• Cours 2 (2 octobre 2020): 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 3 (9 octobre 2020): syntaxe abstraite / sémantique / interprètes
  • transparents

• Cours 4 (16 octobre 2020): analyse lexicale
  • transparents
  • exemple ocamllex : caml2html.mll

• Cours 5 (23 octobre 2020): analyse syntaxique 1/2
  • transparents

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

• Cours 6 (6 novembre 2020): analyse syntaxique 2/2
  • transparents
  • le fichier arith_expr.mll utilisé au début du cours

• Cours 7 (13 novembre 2020): typage
  • transparents

• Cours 8 (20 novembre 2020): mode de passage des paramètres
  • transparents

• Cours 9 (27 novembre 2020): compilation des langages fonctionnels
  • transparents

• Cours 10 (4 décembre 2019): compilation des langages objets
  • transparents

• Cours 11 (11 décembre 2020): compilateur optimisant, partie 1
  • transparents

• Cours 12 (18 décembre 2020): compilateur optimisant, partie 2
  • transparents

• Cours 13 (8 janvier 2021): allocation mémoire
  • transparents

TD

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

Séances :

• TD 1 (25 sep/1 oct) : Mise à niveau OCaml
• TD 2 (2/8 oct) : Assembleur x86-64
• TD 3 (9/15 oct) : Interprète mini-Python
• TD 4 (16/22 oct) : Construction d'automates déterministes à partir d'expressions régulières
• TD 5 (23 oct/5 nov) : Analyse syntaxique d'un petit langage
• pas de TD les 29-30 octobre (vacances Toussaint)
• TD 6 (6/12 nov) : Analyse descendante
• TD 7 (13/19 nov) : Algorithme W
• TD 8 (20/26 nov) : Aide au projet
• TD 9 (27 nov/3 déc) : Aide au projet
• TD 10 (4/10 déc) : Production de code
• TD 11 (11/17 déc) : Coloriage de graphe
• TD 12 (18 déc/7 jan) : Aide au projet
• TD 13 (8/14 jan) : GC stop & copy

Projet

Sujet (version 2 - 19 octobre 2020)

Quelques tests sont fournis (les télécharger : tests-19-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).

Un module OCaml est fourni pour construire du code x86-64 : x86_64.ml / x86_64.mli / documentation / télécharger.
Libre à vous de le compléter si besoin.

Le projet est à rendre en deux fois :

• partie 1 (analyse syntaxique et typage uniquement) pour le dimanche 6 décembre 18:00 ;
• partie 2 (projet complet, avec production de code) pour le dimanche 17 janvier 18:00.

Il est conseillé de procéder construction par construction (que ce soit pour le typage ou pour la production de code), dans cet ordre : affichage, arithmétique, variables globales, instructions (if, for, while), fonctions, structures.

Le rapport rendu avec le projet doit notamment aider à la compréhension du code du projet.

Il n'y a pas de soutenance de projet.

Examen

Les notes de cours manuscrites ou reprographiées sont les seuls documents autorisés.

Archives : janvier 2021 (corrigé) / janvier 2020 (corrigé) / janvier 2019 (corrigé) / janvier 2018 (corrigé) / janvier 2017 (corrigé) / janvier 2016 (corrigé) / janvier 2015 (corrigé) / janvier 2014 (corrigé) / janvier 2013 (corrigé) / janvier 2012 (corrigé) / janvier 2011 (corrigé) / janvier 2010 (corrigé) / janvier 2009 (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 godbolt.org permet de comparer facilement le code assembleur produit par de nombreux compilateurs

• 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
  • un petit polycopié de mise à niveau OCaml (et une version à l'italienne pour économiser du papier en cas d'impression)

• Menhir, un outil d'analyse syntaxique (manuel)
  On peut l'installer avec opam.

• 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
• 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
  2	Assembly	Bryant & O'Hallaron 3
  3	Semantics	Pierce 3-4-5
  4	Typing	Pierce 8-9-10 et 22
  5	Lexical analysis	Dragon 3
  6-7	Syntactic analysis	Dragon 4
  11	Memory allocation	Bryant & O'Hallaron 9