Pablo Rauzy ===================================== | Rapport du projet compilation MiMo | ===================================== Table des matières ================== Architecture du compilateur l. 23 - Le main l. 37 - Le lexer l. 44 - Le parser l. 51 - Le typage l. 72 - La défonctorisation et le renommage l. 105 - La compilation et la production de code l. 123 Compilation et lancement des démos l. 137 Choix faits et difficultés rencontrées l. 156 Notes l. 198 Architecture du compilateur =========================== Il y a sept modules dans mon projet qui compile le code en quatres passes : - le lexer (lexer.mll) - le parser (parser.mly) - le main (main.ml) - le typage (typing.ml) - la défonctorisation et le renommage (defunct.ml) - la compilation (compile.ml) - la production de code (mips.ml) à cela s'ajoute une interface qui déclare juste des types pour l'arbre de syntaxe abstraite (ast.mli). Le main ------- C'est le main qui appelle les modules dans l'ordre où ils sont cités ici. J'ai repris la gestion des arguments de la ligne de commande d'un TD. C'est aussi lui qui récupère les exceptions levées et affiche les messages d'erreurs. Le lexer -------- Le lexer est écrit pour ocamllex (à ce propos voir la sections "Notes") et n'a rien de spécial. La gestion des retour à la ligne pour le repport d'erreur et repris d'un TD (mini-pascal je crois). Le parser --------- Le parser ne suit pas exactement la découpe de la syntaxe donnée dans le sujet, cela est dû à la façon dont j'ai développé le compilateur (en ajoutant les fonctionnalités couche par couche, cela est développé dans la section "Choix faits et difficultés rencontrées"). Pour ajouter les positions dans l'arbre de syntaxe abstraite partout j'ai voulu utiliser une macro. Je me suis donc documenter sur camlp4, qui à l'air d'être un outils très puissant, mais l'est trop pour faire une simple macro. J'utilise donc le préprocesseur de GCC (option -E) sur le parseur avant de l'envoyer à menhir. Celui ci se charge simplement de remplacer la macro suivante dans le fichier : #define I(e) {expr=(e); spos=$startpos; epos=$endpos;} Il y a un conflit shift/reduce restant dans mon parseur mais je ne comprends pas le problème que menhir a et donc encore moins comment le corriger. Le fichier de conflit est src/parser_tmp.conflicts une fois la compilation effectuée. Le typage --------- J'utilise plusieurs environnement pour le typage afin de pouvoir chercher à différent endroits dans un ordre précis. Il y a trois environnements globaux : - un pour les primitives `print_int`, `read_int`, `not` et `ref` - un pour les déclarations de haut niveau (hors des modules) - un pour les modules de haut niveau (hors d'autres modules). La séparation de ces deux derniers environnement est dû à l'ajout successifs de fonctionnalités au compilateur et au fait que les types des déclarations ne sont pas représenté de la même manière que ceux des modules. Il y a deux environnements locaux : - un environnement local qui contient tout ce qui est local au niveau des déclarations (arguments des fonctions, variables liées par un let..in ou un match..with) - un environnement local spécial pour les modules qui est local à chaque module (qui sert entre autre à gérer les redéfinitions). À cela s'ajoute une liste de liste de chaine de caractère pour gérer les modules ouvert par une instruction `open`. La structure générale du typage est un parcours récursifs des éléments de la liste des élements de premier niveau de l'arbres syntaxique. Il ne fais qu'une vérification en parcourant l'arbre et retourne une liste de chaîne de caractères correspondant à des warnings (uniquement dans le cas où une liste d'instructions en contient des de type non unit et qui ne sont pas la dernière de la liste) ou lève une exception si le programme est mal typé. La défonctorisation et le renommage ----------------------------------- Ces deux opérations se font chacune en un nouveau parcours de l'arbre de syntaxe abstraite : La défonctorasation recréer un arbre de syntaxe abstraite plus simple, sans foncteur et qui ne contient plus les informations de localisation. Ensuite une passe de renommage est faite pour ne plus avoir de module. Il est intéressant de savoir que le renommage est fait seulement avec des informations récupérer lors de cette même passe et ne nécessite pas l'utilisation de données récupérées par les passes précédentes. Il reste des constructeurs `Module` et `Struct` dans l'arbre de syntaxe abstraite après ces deux opérations mais ce ne sont que des conteneurs pour une liste de déclarations de premier niveau (puisqu'il n'y a plus de module). La compilation et la production de code --------------------------------------- La compilation de cet arbre est ensuite fait à l'aide du module de production de code dans le module de compilation. Cette phase n'a pas vraiment posée problème. Le module Mips, qui génère le code proprement dit, codé de manière similaire à ce qui est fait dans le premier TD. Le processus de compilation en lui même est aussi repris du même TD. Compilation et lancement des démos ================================== Une fois dans le dossier rauzy-mimo présent dans l'archive rauzy.tgz il suffit de lancer la commande `make` pour compiler le projet. La commande `make demo-syntax` lancera le compilateur avec l'option ``-parse-only'' sur les mauvais exemples puis sur les bons. De manière similaire, `make demo-typing` lancera les démonstration de typages avec l'option ``-type-only''. Enfin, la commande `make demo` lancera la compilation puis l'exécution dans spim des démonstrations du triangle de Pascal modulo 7 et de la fractale de Mandelbrot (/!\ cela suppose que spim est installé et est présent dans le PATH !) Choix faits et difficultés rencontrées ====================================== Je ne savais vraiment pas par où commencer le projet. J'ai donc choisi au début de le développer par couches successives. C'est à dire que plutôt que de faire et tester le lexer, puis le parser etc. j'ai fais toutes la chaîne de compilation puis un langage très simple dans lequel ont pouvait juste déclarer des entiers. J'y ai ensuite ajouté dedans et retouchant tout du lexer au module de compilation les opérations arithmétiques, puis les primitives ``print_int'' et ``read_int'', puis les booléens et la primitive ``not'', puis le test conditionnel ``if''... Tout ça en pouvant compiler jusqu'au bout et faire des test dans spim pour chaques fonctionnalités ajoutées. Je n'avais pas vu qu'il fallait spécialiser les variables dès que possible quand j'ai commencé le projet. Il y a du coup un choix que je regrette d'avoir fait au début dans le module de typage d'utiliser un environnement non persistent pour l'environnement local (un Map.Make(String) plutôt qu'un Hashtbl par exemple). Du coup je n'ai pas pu simplement m'occuper de la spécialisation et elle n'est finalement pas implémenté dans mon compilateur. C'est tout à fait faisable mais comme ce n'est pas une des choses les plus importantes du projet c'est une chose dont j'ai décidé de m'occuper à la fin si j'avais encore du temps, et je n'en ai pas eu. Il en est de même pour les types récursifs non fonctionnels. Je n'ai réussi dans ocaml qu'à faire des listes générées par un cons récursives et ça ne me semble pas difficile à implémenter, il suffit que le second élément de la paire pointe sur la paire elle même, mais par manque de temps je ne l'ai pas fait non plus. Du coup seul les fonctions peuvent être récursives dans mon compilateur. En dehors de ces deux problèmes la principale difficulté que j'ai eu a été de bien comprendre de l'intérieur le mécanisme des modules et des foncteurs étant donné que je ne m'en suis jamais servi pour coder (j'ai utilisé ceux de la lib standard de OCaml je n'en avais jamais codé moi même). Notes ===== Il n'y a pas de commentaire dans le code, c'est pas génial mais je n'en ai ressenti l'utilité à aucun moment. Je n'ai pas eu assez de temps à la fin pour en rajouter mais je suis bien conscient que pour un lecteur extérieur ça n'est peut-être pas idéal, même sur un projet de taille modeste comme celui là. J'ai sur mon ordinateur une version a priori identique à celle de clipper de ocamllex (3.11.1) mais il se trouve que le ocamllex de clipper me génère 41 états contre 46 sur mon ordinateur. Si vous avez une explication du pourquoi du comment je suis intéressé :-). Et aussi, si vous connaissez le développeur de ocamllex et/ou si vous avez un compte sur le bug tracker (pas la motivation de créer un compte juste pour ça...), il faudrait lui dire qu'il y a un fail orthographique dans l'aide (argv[0] not inside) $ ocamllex --help usage: ocamlex [options] sourcefile ("bug" trouvé par Samuel Bizien, histoire de lui rendre ce qui est à César)