MASTER 1ère année

Projet de

Compilation

(Compilateur d'un noyau impératif d'OCAML)


But du projet

Réaliser un compilateur pour le langage micrOCAML décrit ci-dessous. Ce compilateur produira en sortie du code assembleur MIPS. Cet assembleur très simple est proche du code 3 adresses vu en cours et en TD.


1 Présentation du langage

Grammaire du langage

On donne ci-dessous la grammaire complète du langage micrOCAML. Ce langage est un sous-ensemble impératif de OCAML. Dans cette grammaire, les mots-clés et les terminaux apparaissent en fonte courrier. Les constantes booléennes sont true et false. Le terminal ident représente les identificateurs qui sont formés d’une lettre minuscule suivi d’une suite de caractères alphanumériques ou d’une apostrophe ou du caractère de soulignement. Les commentaires débutent par les deux caractères (* et se terminent par les deux caractères *). Ils peuvent être imbriqués (pour implémenter l'imbrication de commentaires avec Lex, vous pouvez utiliser les start conditions). Les tableaux sont unidimensionnels et indicés à partir de 0. Par convention syntaxique, un appel de procédure ne doit pas apparaître seul dans la branche then d'un if. Par exemple, if !x>0 then proc(x) else x := 0 est syntaxiquement incorrect ! A la place, on peut par exemple écrire if !x>0 then begin proc(x) end else x := 0.


program → decllist instr ;;

decllist → ε | decl in decllist

vardecllist → ε | vardecl in vardecllist

decl → vardecl | fundecl

vardecl → let ident : type = valcst                             // déclaration d'une constante
           |  let ident : atomictype ref = ref atomiccst         // déclaration et initialisation d'une variable

fundecl → let fundef | let rec fundefs               // groupe de fonctions ou procédures (mutuellement récursives)

fundefs →  fundef | fundef and fundefs

fundef →  ident arglist = vardecllist instr                            // déclaration d'une procédure
        |  ident arglist : atomictype = vardecllist instr ; expr     // déclaration d'une fonction
        |  ident arglist : atomictype = vardecllist expr             // déclaration d'une fonction pure

type →  atomictype | atomictype array

atomictype →  bool | int

valcst →  atomiccst | Array.make integer atomiccst

atomiccst → integer | ( - integer ) | boolean

arglist → ( ) | arglist1

arglist1 → ( arg ) | ( arg ) arglist1

arg → ident : type |  ident : atomictype ref                             

instr → if expr then instr                                  // conditionnelle

     |   if expr then instr else instr                         // alternative

     |   while expr do sequence done                         // itération

     |   begin sequence end    |    begin end                  // bloc d'instructions

       |     ident := expr                                       // affectation d'une variable

     |   ident . ( expr ) <- expr                            // affectation d'un élément de tableau

     |   ident exprlist   |    ident ( )                         // appel de procédure

     |   print_int expr                                      // écriture d'un entier sur la sortie standard

     |   print_string string                                  // écriture d'une chaîne de caractères

sequence → instr | sequence ; instr

expr → integer | boolean | ( expr ) | expr opb expr | opu expr
       
        |    if expr then expr else expr                // alternative

        |      ident exprlist   |     ident ( )               // appel de fonction

        |    read_int ( )                                  // valeur d'un entier lu sur l'entrée standard 

           |      ident                                        // valeur d'une constante

           |       ! ident                                     // valeur d'une variable

        |    ident . ( expr )                            // valeur d'un élément de tableau

exprlist → expr | exprlist expr

opb → + | − | ∗ | / | < | <= | > | >= | = | <> | && | ||

opu → − | not


Exemples de programme micrOCAML

  1. Factorielle (version itérative) :           exemple1.ml
  2. Factorielle (version récursive) :         exemple2.ml
  3. Crible d'Erathostène :                         exemple3.ml
  4. Fonctions mutuellement récursives :  exemple4.ml
  5. Echange de 2 variables :                     exemple5.ml
  6. Imbrication de if then else :                exemple6.ml


Exécution d'un programme

Les programmes micrOCAML peuvent être exécutés en utilisant l'interpréteur ou le compilateur OCAML (ces outils sont installés sur la machine turing) : 

Par exemple, pour exécuter un programme, disons "essai.ml", situé dans le répertoire courant, avec l'interpréteur, il suffit de taper la commande ocaml essai.ml :

$ cat essai.ml
(* Un simple Hello World ! *)

begin
  print_string "Hello World !\n"
end
$ ocaml essai.ml
Hello World !
$

Il est aussi possible de créer un code exécutable en utilisant le compilateur OCAML. La commande est ocamlc :

$ ocamlc essai.ml
$ ./a.out
Hello World !
$

NB : Vous pouvez prendre le compilateur OCAML comme modèle dans la mesure où le code exécutable généré par votre compilateur doit se comporter comme le code exécutable généré par le compilateur OCAML. Mais puisque micrOCAML est seulement un sous-ensemble de OCAML, les erreurs détectées par votre compilateur ne sont pas les mêmes que celles du compilateur OCAML. D'autre part, comme votre langage source est uniquement impératif et que le langage OCAML est avant tout fonctionnel, les techniques de compilation utilisées ne sont pas les mêmes.


2 Génération de code


Le code généré devra être en assembleur MIPS R2000. L’assembleur est décrit dans les documents mips.pdf et mips.ps. Voici des exemples de codes MIPS :

Le code assembleur devra être exécuté à l’aide du simulateur de processeur R2000 SPIM. Celui-ci est installé sur la machine turing. Pour exécuter un code assembleur, il suffit de faire : spim <nom_du_code>.s. Si vous désirez installer SPIM sur votre propre machine :