Informations générales

Le cours se déroule le vendredi de 10h30 à 12h30 en amphi 6C sous la responsabilité de Yann Régis-Gianas. Les travaux dirigés sont sous la responsabilité de Thibaut Balabonski le lundi de 16h à 18h en salle 478F et 548C, de Matthias Puech le mercredi de 10h30 à 12h30 en 470E et 548C et de Mihaela Sighireanu le jeudi de 9h à 11h en salle 470E et 554C.

Vous devez vous inscrire sur la mailing-liste suivante.

Projet

Voici la partie 1 du sujet du projet. (Dernière mise à jour : 19-04-2012, version 66) Voici la partie 2 du sujet du projet. (Dernière mise à jour : 14-05-2012, version 85)

Vous pouvez soumettre la première partie de votre projet dès aujourd'hui et jusqu'au 23 avril 2012 à 23h59. Il suffit de suivre les instructions que vous trouverez sur la page web de soumission.

Cours 1 : Introduction à la compilation

Dans ce premier cours, nous avons défini informellement les notions de langage, de sémantique, de modèle de calcul, de machine abstraite, de machine virtuelle, d'interprétation et de compilation. Cela nous a permis en particulier d'expliciter la spécification des compilateurs. Enfin, nous avons défini ce que sont les boucles d'interaction.

Nous avons aussi présenté l'architecture classique des compilateurs. Elle s'appuie sur une décomposition en passes de compilation. Les passes de la partie "avant" du compilateur (analyse lexicale, analyse syntaxique, analyse sémantique) servent à traduire le code source en une représentation structurée d'un programme bien formé. La partie "arrière" du compilateur sert à traduire ce programme en un programme exécutable par une machine spécifique.

Nous avons enfin programmé une boucle interactive pour un langage très simple d'expressions arithmétiques avec sommation. Vous trouverez une version commentée de ce programme en suivant ce lien. J'ai rajouté une passe de compilation vers une machine virtuelle à pile, utilisable au sein de la boucle interactive. (Une preuve de plus que le fait d'interpréter ou de compiler un programme est orthogonal à sa définition en mode batch ou interactif.)

Vous pouvez télécharger les transparents du cours.

Travaux pratiques 1 : Analyse lexicale

Cette séance de travaux pratiques a pour objectif de vous initier à l'utilisation de l'outil ocamllex, un programme qui génère le code Ocaml réalisant l'analyseur lexical d'une spécification donnée en entrée.

La documentation d'ocamllex se trouve ici. Vous pouvez accéder à la documentation du module Lexing via cette URL ou plus simplement en tapant man Lexing dans votre terminal.

Voici la feuille d'exercices. Le fichier du premier exercice cat.mll. Pour tester ce dernier, vous pouvez utiliser cette entrée par exemple. [Correction]

Voici une feuille d'exercices supplémentaires. [Correction]

Cours 2 : Analyse lexicale et syntaxique

Cette séance, nous avons rappelé les définitions et notions utiles à l'analyse syntaxique: les terminaux et de non terminaux, les grammaires, la relation de dérivation, la définition du langage engendré par une grammaire, le graphe de production, la dérivation gauche et droite et enfin la définition de l'ambiguité d'une grammaire. Pour présenter ces définitions sous un jour nouveau, nous les avons programmées en OCaml. (Voir le fichier suivant.)

À partir de ces définitions, il a été facile de donner une spécification à un analyseur syntaxique. Après avoir rapidement rappelé la classification des grammaires de Chomsky, et introduit la notation de Backus Naur (BNF) pour les grammaires hors contexte, nous avons aussi donné une spécification aux générateurs d'analyseurs syntaxiques que vous utiliserez pour votre projet. Nous avons remarqué qu'il y a deux façons de supprimer une ambiguïté dans une grammaire : a priori en transformant la grammaire en une grammaire équivalente non ambigüe, a posteriori en donner des critères (priorité, associativité) pour choisir un arbre de production plutôt qu'un autre.

D'un point de vue pratique, nous avons remarqué que l'arbre de production issu de la reconnaissance d'une entrée par un analyseur syntaxique n'était pas exactement l'arbre de syntaxe abstraite dont nous avons besoin pour les phases suivantes de la compilation. Cela nous a amené à définir une notion de valeur sémantique associée aux symboles de la grammaire et produites à chaque application d'une règle de production de la grammaire.

L'ensemble de ces définitions nous a permis de comprendre un exemple de spécification de grammaire écrite pour le générateur d'analyseur syntaxique Menhir. Nous avons expliqué le processus d'utilisation de cet outil: à partir d'une spécification de grammaire, Menhir produit un analyseur syntaxique et une liste des conflits (expliqués) de la grammaire. En rajoutant des indications de priorité et d'associativité dans la spécification, on peut supprimer ces conflits. L'exemple de spécification Menhir est ici.

Vous pouvez télécharger les transparents du cours.

Cours 3 : Analyse descendante

Dans ce cours, nous avons abordé la famille des analyseurs syntaxiques dits "descendants" parce qu'ils essaient de reconstruire l'arbre de production d'un mot (possiblement) dérivé par une grammaire en partant de la racine de l'arbre vers ses feuilles.

Le premier algorithme que nous avons étudié est celui de Unger. C'est un algorithme d'analyse syntaxique qui procède à une recherche de l'arbre de production en énumérant pour une partie droite d'une règle donnée dont les symboles de production sont [S0; S1; ..; sN] toutes les façons de découper le mot analysé en N parties Pi telles que pour tout i, "Si" produise "Pi".

Si on l'implémente naïvement, cet algorithme est de complexité exponentielle et ne terminent pas sur les grammaires avec règles epsilon et boucles. À l'aide d'une mémoire servant à stocker les analyses en cours et les analyses dont on connaît déjà la réponse, on peut rendre cet algorithme polynomial et supprimer les cas de non terminaison sur les grammaires avec boucles et règles epsilon. Le procédé qui consiste à transformer une fonction récursive en une fonction récursive avec mémoire est appelée mémoïsation et est une technique très utile de programmation.

Nous avons implémenté cet algorithme en Caml, vous trouverez la version commentée de ce code ici. Si vous souhaitez approfondir votre compréhension de cet algorithme, je vous conseille de lire la partie correspondante (page 82) dans le livre (en ligne) de Jacobs et Grune. Vous pouvez aussi regarder ce travail de master sur une implémentation optimisée de Unger.

L'algorithme de Unger se pose beaucoup de questions. Beaucoup de ces questions peuvent être rejetées par une simple observation de la forme de la règle et de celle de l'entrée considérée. Par exemple, la taille minimale de mot produit par une règle peut être calculée une fois pour toute et utilisée pour rejeter toutes les entrées dont la longueur est moindre que cette taille minimale. Une autre idée consiste à déterminer si le premier terminal de l'entrée est adns l'ensemble des premiers terminaux des mots dérivables par le membre droit d'une règle. En cas de réponse négative, on peut rejeter cette règle.

Un autre défaut de l'algorithme de Unger est qu'il travaille sur la totalité de l'entrée. Or, si cette entrée est très grande et qu'elle ne tient en mémoire, cette hypothèse ne pas réaliste.

Pour ces raisons, nous avons ensuite abordé les analyses qui lisent l'entrée de gauche à droite et déduisent un ensemble de prédictions sur la suite de l'entrée qui impliqueraient l'existence d'un arbre de production. Parce qu'ils lisent l'entrée de gauche à droite, ces algorithmes ne considèrent que les arbres de production gauche.

À l'aide d'un automate à pile non déterministe avec transitions instantanées que l'on déduit immédiatement de la grammaire hors-contexte, on peut construire un algorithme prédictif lisant l'entrée de gauche à droite à condition que la grammaire ne soit pas récursive à gauche. Nous avons vu comment réécrire une grammaire avec récursion à gauche en une grammaire équivalente sans récursion à gauche.

Un automate à pile non déterministe n'est pas un modèle de calcul efficace car plusieurs prédictions doivent être considérées après avoir analysé un préfixe de l'entrée. C'est une situation logique puisque les grammaires peuvent être ambigues.

On peut restreindre les grammaires traitées aux grammaires LL(k), c'est-à-dire les grammaires pour lesquelles il suffit de regarder les k premiers terminaux de l'entrée pour déterminer une unique prédiction servant à analyser la suite de l'entrée. Nous avons vu comment construire une table pour les grammaires LL(1) qui n'ont pas de règle epsilon. Cette construction s'appuie sur le calcul d'une fonction FIRST qui associe à chaque non terminal N l'ensemble des terminaux qui peuvent apparaître au début des mots qui dérivent de N.

Les règles epsilon posent problème : la fonction FIRST telle que nous l'avions définie n'est plus suffisante pour déterminer les premiers symboles apparaissant dans un mot dérivé d'un non terminal particulier. Il faut ajuster cette définition en prenant en compte les symboles dit annulables ou effaçables, c'est-à-dire ceux pouvant produire le mot vide. Pour un tel non terminal N, il est nécessaire de considérer l'ensemble des terminaux qui peuvent suivre N dans une dérivation où celui-ci produit le mot vide. Nous avons généralisé la définition de FIRST pour cela.

Les règles epsilon posent aussi problème quand on veut construire une table d'analyse LL. En effet, comment savoir si on doit reconnaître un non terminal N parce qu'il a produit le mot vide dans le mot à analyser? Il faut mettre les règles de la forme "N → ε" dans les cases de coordonnées (N, a) pour "a" un terminal pouvant suivre N. Pour construire cette table efficacement, on précalcule la fonction FOLLOW qui associe à un non terminal N l'ensemble des terminaux qui peuvent le suivre.

Vous pouvez télécharger les transparents du cours.

Travaux dirigés 2 : Analyse syntaxique descendante

Dans cette séance de travaux dirigés, vous allez construire et interpréter des tables d'analyse syntaxique pour des grammaires LL(1).

Voici la feuille d'exercices. [Correction]

Cours 4 : Analyse syntaxique ascendante.

Cette partie du cours se focalise maintenant sur les algorithmes d'analyse ascendante. Nous suivons la même progression que pour les algorithmes d'analyse descendante: un algorithme ascendant non directionnel (CKY), puis un algorithme directionnel (Earley) et enfin, un algorithme directionnel et déterministe (LR).

L'algorithme CYK a été présenté rapidement. Il s'agit de construire une table dont la ligne i contient un partitionnement de l'entrée en mots de taille "i" et les non-terminaux qui ont pu dériver ces mots. L'idée de cet algorithme est de réutiliser la ligne (i - 1) pour calculer la ligne i. La seule difficulté de l'algorithme provient des règles unitaires et epsilon qui forcent à un calcul de point fixe pour chacune des lignes car une part du contenu de celles-ci est alors définie récursivement. La complexité de cet algorithme est O(n^(k + 1)) où k est la longueur maximale des membres droits des règles de la grammaire. En transformant la grammaire hors contexte considérée en une grammaire équivalente en forme de Chomsky, l'algorithme devient cubique.

Nous avons ensuite porté notre attention sur les analyses ascendantes directionnelles. Comme dans le cas descendant, un automate à pile non déterministe peut simuler l'ensemble des façons de reconnaître un mot de façon ascendante. En effet, il suffit de stocker dans la pile de l'automate les sous-arbres construits à un moment "t" de l'algorithme et de procéder à deux formes différentes de transactions sur cet automate:

Transition de type "décalage" (shift) : elle consiste à prendre le terminal de tête de l'entrée si celle-ci n'est pas vide et à le pousser au sommet de la pile sous la forme d'un arbre réduit à une feuille.
Transition de type "réduction" (reduce) : elle consiste à dépiler un certain nombre d'arbres du sommet de la pile et à appliquer une règle de la grammaire pour en déduire un nouvel arbre à pousser au sommet de la pile.

On peut montrer que pour une grammaire G et un mot d'entrée w, un tel automate à pile non déterministe a une configuration finale d'acceptation du mot w (c'est-à-dire une configuration où tout le mot a été consommé et la pile est formée d'un unique arbre de production dont la racine est le symbole d'entrée de la grammaire) si et seulement si le mot w est dans le langage engendré par G.

Cette dernière propriété fournit immédiatement un algorithme d'analyse syntaxique: il suffit d'explorer l'espace des configurations de l'automate à la recherche d'une configuration finale! Cette espace peut être parcouru dans plusieurs directions: en profondeur ou en largeur. Nous avons utilisé la bibliothèque générique de recherche ( implémentation | interface ) de Jean-Christophe Filliâtre pour implémenter cet algorithme en OCaml. Vous en trouverez une version commentée ici .

Encore une fois, nous avons remarqué qu'une recherche non dirigée part dans des directions non pertinentes dont on pourrait montrer l'inocuité à l'aide de critères très simples comme par exemple le symbole suivant de l'entrée. Nous avons alors commencé à étudier l'algorithme de Earley qui maintient un ensemble d'analyses en cours de façon parallèle et exploite l'information donnée par le prochain symbole de l'entrée pour court-circuiter certaines de ces analyses rapidement.

Vous pouvez télécharger les transparents du cours.

Travaux dirigés 4 : Analyse ascendante généraliste

Dans ce sujet, on applique l'algorithme CYK. On revient aussi sur la mise en forme normale de Chomsky.

Le sujet. [Correction]

Cours 5 : Analyse syntaxique ascendante (deuxième partie).

Afin d'obtenir un algorithme d'analyse ascendante de complexité linéaire, nous avons cherché à construire un algorithme s'appuyant sur un automate à pile, à réduction et à décalage, déterministe.

Nous avons "recyclé" les états d'analyse de l'algorithme de Earley pour décrire un automate fini non déterministe avec transitions instantanées qui correspond à une grammaire hors-contexte. L'automate fini déterministe associé, si il contient uniquement des états finals contenant au plus un état d'analyse à réduire et des états avec des transitions sortantes ne contenant que des états d'analyse en cours, est appelé automate LR(0). Nous avons vu comment interprété cet automate pour reconnaître un mot de la grammaire.

Les automates LR(0) ne sont pas très expressifs : certains de leurs conflits peuvent être résolus par une simple observation du prochain symbole de l'entrée. En faisant figurer dans l'état d'analyse l'ensemble des terminaux qui peuvent suivre le non terminal à reconnaître, on augmente très nettement la classe des langages reconnaissables. Ceci conduit à la définition des automates LR(1) : ils sont obtenus d'une façon similaire aux automates LR(0) mais en propagant l'information supplémentaire du symbole attendu après l'analyse.

Les automates LR(1) sont cependant trop gourmand en espace mémoire. Nous avons vu qu'une compression des états de ces automates est envisageable en pratique: tous les états possédant les mêmes états d'analyse peuvent être fusionnés sans changer le langage reconnu pour un grand nombre de grammaire. Un tel automate est appelé LALR(1) et nous avons appris à les construire "à la volée", sans passer par l'automate LR(1). Nous avons aussi remarqué que dans certains cas, cette compression introduit des conflits qui n'étaient pas présents dans l'automate LR(1).

Vous pouvez télécharger les transparents.

Travaux dirigés 5 : Menhir

L'objectif de cette séance est de vous familiariser avec la syntaxe des spécifications de grammaire de Menhir. Vous apprendrez à résoudre des conflits LR par le jeu des priorités entre règles de production ou à l'aide de transformations de grammaire.

Le sujet et le code de départ. [Correction]

Cours 6 : Analyse syntaxique en pratique.

Ce dernier cours d'analyse syntaxique s'est focalisé sur la suppression des conflits, en particulier dans le cas des automates LR(1) produits par Menhir.

Vous pouvez télécharger les transparents.

Travaux dirigés 6 : LR

L'objectif de cette séance est de rentrer dans les détails de construction des automates LR.

Le sujet et le [Correction]

Cours 7 : Syntaxe

Dans ce cours, nous avons défini la notion de syntaxe abstraite, en opposition à la notion de syntaxe concrète. Ainsi, une syntaxe abstraite est un ensemble d'arbres de syntaxe abstraite que l'on peut définir à l'aide d'une grammaire d'arbres, ou de façon équivalente, à l'aide d'un type somme en Caml. Les arbres de syntaxe abstraites sont aussi appelés des termes.

L'intérêt des termes se trouve dans leur structure: on peut très facilement définir une fonction par induction sur la forme des termes. Dit autrement, on peut définir une fonction "f" sur les termes par cas sur la forme du terme "t" fourni et utilisant les évaluations de cette fonction "f" sur les sous-termes du terme "t".

La sémantique opérationnelle d'un langage de programmation, c'est-à-dire la spécification mathématique de l'évaluation de ces programmes, se définit naturellement à l'aide d'une fonction définie par induction sur les arbres de syntaxe abstraite de ce langage.

Nous avons vu deux familles de sémantique opérationnelle: celles dites à petits pas et celles dites à grands pas. Les sémantiques à petits pas sont en général plus précises que les sémantiques à grands pas mais ces dernières sont souvent plus simples à écrire et sont plus utiles pour l'écriture d'interprètes.

Une sémantique à petits pas décrit toutes les étapes du calcul à l'aide d'étapes de réécriture du terme en un "terme plus proche du résultat", que l'on appelle son réduit. Nous avons défini une sémantique à petits pas pour les expressions arithmétiques à l'aide d'un système de règles d'inférence définissant le jugement "t se réduit en une étape de calcul en t'". Deux types de règles sont alors apparues: les règles dites de réduction et les règles dites de passage au contexte. Nous avons implémenté cette même sémantique à l'aide d'une fonction O'Caml. Vous pouvez en télécharger le code source.

Une sémantique à grands pas décrit la relation entre un terme et sa valeur finale. À la différence des sémantiques à petits pas, une sémantique à grands pas peut laisser de côté certains détails de l'évaluation, comme par exemple l'ordre d'évaluation des sous-expressions. En effet, dans une sémantique à petits pas, pour évaluer "e1 + e2", il faut préciser si "e1" ou "e2" doit être le premier à être réduit en un entier. Dans une sémantique à grands pas, on dit que si "e1" s'évalue en "n1" et "e2" s'évalue en "n2" alors "e1 + e2" s'évalue en "n1 + n2". L'ordre n'est pas nécessaire spécifié. Nous avons implémenté la sémantique à grands pas des expressions arithmétiques en O'Caml. Vous pouvez télécharger le code source.

Pour terminer, nous avons commencé à étudier une première extension du langage des expressions arithmétiques à l'aide de variables. Pour définir la sémantique à petits pas du langage résultant, nous avons dû formaliser la notion de substitution d'une variable libre par un terme. Nous avons remarqué qu'il fallait être vigilant quand on définit la notion de substitution car une définition naïve peut substituer de façon incorrecte des variables liées portant le même nom que la variable libre à substituer. Vous pouvez télécharger le code source de l'interprète de cette sémantique à petits pas.

Enfin, voici les transparents de la séance.

Cours 8 : Liaison de noms

Nous avons tout d'abord défini une analyse statique permettant de garantir que les noms de variable apparaissant dans une sous-expression étaient bien définis plus haut. Pour cela, il a été utile d'introduire une notion d'environnement de nommage qui maitient la liste des variables bien définies en tout point du programme. Nous avons donné une définition formelle, à l'aide de règles d'inférence, au jugement spécifiant notre analyse statique.

Dans un second temps, nous avons défini un modèle de calcul plus efficace que les expressions pour évaluer nos programmes : une machine virtuelle à piles. En effet, le code s'y présente de façon linéaire, ce qui rend possible un parcours des instructions à l'aide d'un simple compteur, ce qui est plus efficace que le parcours réalisé par la fonction récursive de notre interprète, qui utilise un pile. Notre machine utilise deux piles : une pour maintenir la valeur des variables définies en un point donné du programme, et l'autre pour maintenir les valeurs intermédiaires. Cette machine a un jeu d'instructions servant à faire évoluer ces deux piles. Nous avons donné une spécification à ces instructions à l'aide d'une sémantique opérationnelle à petits pas.

Pour terminer, nous avons introduit une fonction de compilation de notre langage d'expressions arithmétiques avec variables à du code pour notre machine virtuelle. Cette fonction de compilation transforme les expressions arithmétiques de la notion infixe, qui nécessite une pile pour être interprétée, à la notation postfixe qui n'en a pas besoin pour être interprétée (mais il faut toujours une pile pour stocker les résultats intermédiaires des calculs!).

Voici les transparents de la séance.

Travaux dirigés 7 : Sémantique

L'objectif de cette séance est d'étudier la sémantique opérationnelle d'un langage impératif jouet.

Le sujet [Correction]

Cours 9 : Langage du premier ordre

Dans cette séance, nous avons introduit des mécanismes qui modifient le flot de contrôle : les branchements conditionnels et les appels de fonctions (de seconde classe).

Pour donner une sémantique au branchement conditionnel, nous utilisons des booléens, produits par des opérateurs de comparaison. Ces booléens ne doivent pas être confondus avec des entiers, sinon, l'évaluation se bloque. Pour cette raison, un algorithme de typage classifie les valeurs pour s'assurer de façon statique, c'est-à-dire avant l'évaluation du programme à proprement parler, que l'on ne mélangera pas booléens et entiers.

Nous avons ensuite compilé notre langage d'expressions arithmétiques avec variables et expressions conditionnelles vers une machine virtuelle. Cette machine ne peut désormais plus représenter le code comme une séquence unique d'instructions : il faut pouvoir déplacer l'unité de calcul de façon arbitraire dans le code machine. C'est pour cela que nous avons introduit une notion d'étiquette permettant de nommer certains points du code et une instruction de saut conditionnel permettant d'y sauter en fonction de la valeur du sommet de la pile des résultats intermédiaires. Une instruction de saut inconditionnel permet de se déplacer de façon similaire en un point du programme, mais cette fois, systématiquement. Nous avons écrit la fonction de compilation des expressions vers les programmes de cette machine.

Nous avons ensuite évalué l'intérêt du rajout d'une expression de saut (goto) dans le langage source. Cela nous a amené à nous remémorer une vieille discussion à ce sujet et qui a donné lieu à la création de la programmation structurée. Lisez donc ces papiers qui font partie de l'histoire de l'informatique:

Goto statement considered harmful Edgar Dijkstra.
Structured Programming with go to statements Donald E. Knuth.

Nous avons ensuite introduit le concept de fonction de seconde classe : des briques logicielles qui permettent d'introduire des abstractions dans les programmes en autorisant le programmeur à se créer ses propres primitives de calcul. Nous avons donné une sémantique à grands pas aux appels de fonction et étendu l'algorithme de typage pour qu'il nous garantisse que l'évaluation des appels de fonction se déroulent correctement dans un programme bien typé.

Voici les transparents de la séance.

Cours 10 : Expérimentations autour des fonctions

Lors de cette séance, nous avons regardé de plus près le mécanisme d'appel de fonction (de seconde classe) en étudiant la façon dont on peut le compiler (ou pas) vers notre machine virtuelle.

Nous sommes tombés sur un problème : à la fin du code machine d'une fonction, comment savoir où continuer le calcul? En effet, cette continuation du calcul varie en fonction de l'appelant! En d'autres termes, on ne peut pas savoir à l'avance en quel point du programme la fonction "f" dont on compile le code va être appelée.

Une solution à ce problème consiste à pousser sur la pile une adresse de retour, autrement dit une représentation dynamique de la continuation du calcul, vers laquelle le code de la fonction devra sauter une fois qu'il aura terminé son travail. Dans ce schéma, avant d'appeler une fonction, l'appelant doit prendre soin de pousser sur la pile l'adresse du code correspondant à l'instruction qui suit l'appel de fonction. Il aura alors la garantie que le contrôle reviendra en ce point une fois la fonction (et ses propres sous-appels de fonctions) terminée.

Nous avons ensuite optimisé notre machine virtuelle et notre compilation pour obtenir une implémentation proche de la réalité des protocoles d'appels de fonctions de langages tels que C ou Java.

Nous avons terminé cette séance en remarquant que le mécanisme d'appel de fonction de seconde classe ne convient pas à l'implémentation des fonctions de première classe, ou plus généralement des objets, tels qu'on les trouve dans les langages d'ordre supérieur comme OCaml ou Java.

Voici les transparents de la séance.

Cours 11 : Les fonctions de première classe

Lors de cette séance, nous avons fait un tour des techniques de représentation des fonctions comme des valeurs de première classe, c'est-à-dire comme des données manipulables par les calculs. Deux approches ont été présentées : les S-Expressions de LISP et les fermetures, des paires formées d'un pointeur de code et d'un environnement d'évaluation contenant tout ce qui est nécessaire au code pointé pour s'évaluer correctement. Nous avons modélisé et implémenté un interprète à grands pas pour le λ-calcul en appel par valeurs en utilisant des fermetures.

Voici les transparents de la séance.

Références