Ce petit compilateur a été écrit par François Pottier pour le cours de compilation. Il s'agit d'un compilateur d'un langage impératif simple, baptisé Pseudo-Pascal, vers l'assembleur MIPS. Il est écrit en Objective Caml.
Le code source complet du petit compilateur est disponible au téléchargement sur la page principale du cours. Ici, il s'agit simplement d'étudier le code en ligne. Ce code est divisé en un assez grand nombre de modules, groupés en plusieurs parties correspondant grosso modo aux différentes phases du compilateur. Ces modules sont décrits ci-dessous. Chaque module est accompagné d'un commentaire et d'une estimation de son intérêt pédagogique (aucun, faible, moyen, élevé).
Le code est coloré pour en augmenter la lisibilité. De plus, lorsque vous passez votre souris au-dessus d'une variable, son type apparaît!
| nom de l'interface | nom de l'implémentation | intérêt pédagogique | commentaire |
|---|---|---|---|
| Structures de données et utilitaires | |||
| myMap.mli | myMap.ml | faible | Ce module inclut le contenu du module Map de la librairie standard et lui ajoute quelques fonctionalités supplémentaires. Il pourrait disparaître à terme si ces fonctionalités sont ajoutées à la librairie standard. |
| integer.mli | integer.ml | faible | Ce module donne aux opérations sur les entiers 32 bits les noms standard habituellement utilisés pour les opérations sur les entiers 31 ou 63 bits d'Objective Caml. Il définit également quelques opérations supplémentaires. |
| misc.mli | misc.ml | faible | Ce module définit quelques opérations sur les listes. |
| stringSet.mli | stringSet.ml | faible | Ce module définit des ensembles dont les éléments sont des chaînes de caractères. |
| stringMap.mli | stringMap.ml | faible | Ce module définit des tables dont les clefs sont des chaînes de caractères. |
| setMap.mli | setMap.ml | faible | Ce module définit quelques opérations spécifiques sur les tables dont les données sont des ensembles. Ces tables peuvent être utilisées pour représenter des relations ou des graphes. |
| prioritySet.mli | prioritySet.ml | faible | Ce module définit des ensembles dont chaque élément est doté d'une priorité entière, et permet d'accéder efficacement à un élément de priorité minimale. |
| unionFind.mli | unionFind.ml | moyen | Ce module définit une représentation efficace pour des classes d'équivalence dotées d'un élément distingué et d'une opération de fusion de deux classes. Il s'agit d'un algorithme classique dû à Tarjan. Il n'est employé ici, de façon un peu anecdotique, que dans le module Branch. |
| print.mli | print.ml | aucun | Ce module définit des utilitaires d'affichage. |
| atomSig.mli | moyen | Ce module spécifie une série d'opérations sur les atomes, ensembles d'atomes, et tables dont les clefs sont des atomes. Ces opérations sont implémentées par le module Atom. Les atomes sont utilisés pour représenter les pseudo-registres et les labels des graphes de flot de contrôle. | |
| atom.mli | atom.ml | faible | Ce module implémente les opérations sur les atomes spécifiées par AtomSig. |
| option.mli | option.ml | faible | Ce module propose quelques opérations courantes sur les options. |
| settings.mli | settings.ml | aucun | Ce module prend en compte les instructions fournies sur la ligne de commande du compilateur. |
| location.mli | location.ml | aucun | Ce module fournit un type qui combine une valeur arbitraire et une position issue du fichier source. |
| error.mli | error.ml | aucun | Ce module fournit quelques fonctions de signalement d'erreurs. |
| f | |||
| Le processeur MIPS | |||
| MIPS.mli | MIPS.ml | élevé | Ce module définit les registres physiques du processeur MIPS ainsi que leur utilisation conventionnelle. |
| MIPSOps.mli | élevé | Ce module définit les opérateurs du processeur MIPS. | |
| printOps.mli | printOps.ml | aucun | Ce module fournit des fonctions d'affichage des opérateurs du processeur MIPS. |
| interpretMIPS.mli | interpretMIPS.ml | faible | Ce module fournit un interprète pour les opérateurs du processeur MIPS. |
| f | |||
| L'analyse lexicale, syntaxique, et le typage | |||
| primitive.mli | élevé | Ce module définit les opérations primitives du langage Pseudo-Pascal. | |
| printPrimitive.mli | printPrimitive.ml | aucun | Ce module fournit des fonctions d'affichage des opérations primitives du langage Pseudo-Pascal. |
| LPP.mli | élevé | Ce module définit la syntaxe abstraite du langage LPP. Il s'agit d'une version de Pseudo-Pascal où les arbres de syntaxe abstraite sont décorés par des positions issues du fichier source. | |
| parser.mly | élevé | Ce module définit la liste des lexèmes produits par l'analyseur lexical, et contient la définition de la grammaire du langage Pseudo-Pascal. Il est utilisé pour engendrer l'analyseur syntaxique. Celui-ci produit des arbres de syntaxe abstraite exprimés dans le langage LPP. | |
| lexer.mll | faible | Ce module contient la définition de l'analyseur lexical. | |
| typechecking.mli | typechecking.ml | moyen | Ce module contient un vérificateur de types très simple pour Pseudo-Pascal. Il exige en fait un programme exprimé dans le langage LPP et utilise les positions qui décorent les arbres de syntaxe abstraite pour indiquer la position des erreurs de typage dans le fichier source. |
| f | |||
| Le langage PP | |||
| PP.mli | élevé | Ce module définit la syntaxe abstraite du langage PP. | |
| lpp2pp.mli | lpp2pp.ml | aucun | Ce module traduit LPP vers PP en effaçant les positions issues du fichier source. |
| printPP.mli | printPP.ml | faible | Ce module fournit un afficheur pour Pseudo-Pascal. La façon dont des parenthèses sont insérées pour garantir l'absence d'ambiguïté peut être intéressante. |
| interpretPP.mli | interpretPP.ml | élevé | Ce module fournit un interprète pour Pseudo-Pascal. |
| f | |||
| Le langage UPP | |||
| UPP.mli | élevé | Ce module définit la syntaxe abstraite du langage UPP. | |
| upp2upp.mli | upp2upp.ml | élevé | Ce module transforme les opérateurs de PP en ceux de UPP (qui sont les opérateurs du processeur MIPS) et applique une série de règles de réécriture de UPP vers lui-même pour optimiser l'emploi de ces opérateurs. Ce module contient donc l'essentiel du code de sélection d'instructions. |
| pp2upp.mli | pp2upp.ml | élevé | Ce module traduit PP vers UPP. La traduction consiste à supprimer les informations de typage, distinguer variables locales et globales, remplacer les opérations sur les tableaux par des opérations plus élémentaires d'accès à la mémoire, initialiser les variables locales de chaque procédure ou fonction à zéro, et enfin, à l'aide du module Upp2upp, remplacer les opérateurs de PP par ceux du processeur MIPS. |
| printUPP.mli | printUPP.ml | aucun | Ce module fournit un afficheur pour UPP. |
| interpretUPP.mli | interpretUPP.ml | aucun | Ce module fournit un interprète pour UPP. |
| f | |||
| Le langage RTL | |||
| RTL.mli | élevé | Ce module définit la syntaxe abstraite du langage RTL. | |
| register.mli | register.ml | aucun | Ce module est une version renommée du module Atom. Il définit le type abstrait des pseudo-registres. |
| label.mli | label.ml | aucun | Ce module est une version renommée du module Atom. Il définit le type abstrait des labels de graphe de flot de contrôle. |
| upp2rtlI.mli | upp2rtlI.ml | élevé | Ce module contient la partie centrale de la traduction de UPP vers RTL. La traduction consiste principalement à déstructurer expressions, conditions et instructions arborescentes pour les remplacer par un simple graphe de flot de contrôle dont chaque sommet porte une instruction élémentaire. La traduction fait également apparaître les pseudo-registres en remplacement des variables locales. |
| upp2rtl.mli | upp2rtl.ml | élevé | Ce module contient la partie périphérique de la traduction de UPP vers RTL. |
| cse.mli | cse.ml | élevé | Ce module effectue l'élimination des sous-expressions communes. Il s'agit d'une transformation de RTL vers lui-même, qui consiste à supprimer certaines instructions dont le résultat est déjà disponible dans un pseudo-registre parce qu'il a été calculé précédemment. |
| printCFG.mli | printCFG.ml | aucun | Ce module fournit un afficheur pour les graphes de flot de contrôle. |
| printRTL.mli | printRTL.ml | aucun | Ce module fournit un afficheur pour RTL. |
| interpretRTL.mli | interpretRTL.ml | aucun | Ce module fournit un interprète pour RTL. |
| f | |||
| Le langage ERTL | |||
| ERTL.mli | élevé | Ce module définit la syntaxe abstraite du langage ERTL. | |
| rtl2ertlI.mli | rtl2ertlI.ml | élevé | Ce module effectue la partie centrale de la traduction de RTL vers ERTL. Cette traduction explicite la convention d'appel en engendrant des instructions de déplacement explicites entre pseudo-registres, d'une part, et registres physiques ou emplacements de pile, d'autre part. |
| rtl2ertl.mli | rtl2ertl.ml | moyen | Ce module effectue la partie externe de la traduction de RTL vers ERTL. |
| Fix.mli | Fix.ml | élevé | Ce module fournit un algorithme générique de calcul de la plus petite solution d'un système d'équations monotones. Il est utilisé par l'analyse de durée de vie. |
| liveness.mli | liveness.ml | élevé | Ce module fournit une analyse de durée de vie. Cette analyse permet d'éliminer les instructions pures dont le résultat n'est pas utilisé. Elle permet également d'obtenir les informations nécessaires à la construction d'un graphe d'interférences. |
| printERTL.mli | printERTL.ml | aucun | Ce module fournit un afficheur pour ERTL. |
| interpretERTL.mli | interpretERTL.ml | aucun | Ce module fournit un interprète pour ERTL. |
| f | |||
| L'allocation de registres | |||
| interference.mli | interference.ml | faible | Ce module fournit une structure de données relativement efficace pour représenter les graphes d'interférences. |
| zero.mli | zero.ml | élevé | Ce module effectue une analyse extrêmement simple dont l'objectif est de permettre un bon emploi du registre spécial $zero. |
| build.mli | build.ml | élevé | Ce module utilise les informations fournies par l'analyse de durée de vie pour construire un graphe d'interférences. |
| uses.mli | uses.ml | moyen | Ce module compte combien de fois chaque pseudo-registre est employé. Cette information est utilisée pour diriger certains choix lors de l'allocation de registres. |
| coloring.mli | coloring.ml | élevé | Ce module résoud un problème de coloriage de graphes à l'aide d'un nombre fini de couleurs, correspondant aux registres physiques allouables. |
| spill.mli | spill.ml | élevé | Ce module résoud un problème de coloriage de graphes à l'aide d'un nombre illimité de couleurs, correspondant à des emplacements de pile. |
| f | |||
| Le langage LTL | |||
| LTL.mli | élevé | Ce module définit la syntaxe abstraite du langage LTL. | |
| ertl2ltlI.mli | ertl2ltlI.ml | élevé | Ce module contient la partie centrale de la traduction de ERTL vers LTL. Il suppose l'allocation de registres effectuée, et utilise cette information pour remplacer les pseudo-registres par des registres du processeur et des emplacements de pile. |
| ertl2ltl.mli | ertl2ltl.ml | moyen | Ce module contient la partie externe de la traduction de ERTL vers LTL. |
| printLTL.mli | printLTL.ml | aucun | Ce module fournit un afficheur pour LTL. |
| interpretLTL.mli | interpretLTL.ml | aucun | Ce module fournit un interprète pour LTL. |
| f | |||
| Le langage LIN | |||
| LIN.mli | élevé | Ce module définit la syntaxe abstraite du langage LIN. | |
| branch.mli | branch.ml | moyen | Ce module supprime toutes les instructions IGoto. Il s'agit d'une transformation de LTL vers lui-même. |
| ltl2linI.mli | ltl2linI.ml | moyen | La traduction de LTL vers LIN consiste principalement à linéariser le graphe de flot de contrôle à l'aide d'un parcours en profondeur d'abord. Ce module contient la partie centrale de cette traduction. |
| ltl2lin.mli | ltl2lin.ml | faible | Ce module contient la partie externe de la traduction de LTL vers LIN. |
| printLIN.mli | printLIN.ml | aucun | Ce module fournit un afficheur pour LIN. |
| interpretLIN.mli | interpretLIN.ml | aucun | Ce module fournit un interprète pour LIN. |
| f | |||
| Le langage ASM | |||
| ASM.mli | élevé | Ce module définit la syntaxe abstraite du langage ASM. Ce langage correspond presque directement à un sous-ensemble du langage assembleur MIPS. | |
| lin2asm.mli | lin2asm.ml | élevé | Ce module effectue la traduction de LIN vers ASM. Celle-ci consiste principalement à remplacer les instructions abstraites d'accès aux emplacements de pile par des instructions d'accès à la mémoire à un décalage fixe vis-à-vis du registre $sp. |
| printASM.mli | printASM.ml | aucun | Ce module fournit un afficheur pour ASM. Il est utilisé pour produire le code assembleur final. |
| main.mli | main.ml | aucun | Ce module met bout à bout toutes les phases du compilateur. |