Organisation du petit compilateur

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.