Maîtrise 2003--2004 Projet de compilation
Compilateur d'expressions arithmétiques




TP individuel, à finir à la maison et à rendre
par email au chargé de TP à J+3 au matin

Le but de ce TP est de réaliser un compilateur d'expressions arithmétiques vers le langage de la machine virtuelle qui sera utilisé pour le projet de compilation. Le langage des expressions arithmétiques à compiler, appelé par la suite Arith, est une légère variation du langage présenté dans le TP précédent.

Afin de vous aider à construire ce compilateur, nous vous fournissons sa structure de base (sous la forme d'un ensemble de fichiers) que vous pouvez récupérer avec la commande:

tar zxf/308/Public_Enseignement/TER-COMPIL/tp2/arithc.tgz


Un répertoire arithc est créé, contenant les fichiers suivants:

ast.mli la syntaxe abstraite d'Arith
lexer.mll l'analyseur lexical d'Arith
parser.mly l'analyseur syntaxique d'Arith
syntaxerr.ml une fonction pour localiser les erreurs lexicales et syntaxiques
  dans le fichier source
codevm.mli les instructions de la machine virtuelle
compile.ml les fonctions de production du code de la machine virtuelle
main.ml le programme principal du compilateur
Makefile les règles pour automatiser la compilation du compilateur

Enfin, pour avoir accès aux exécutables de la machine virtuelle, il vous faut ajouter la ligne suivante à la fin de votre fichier .cshrc :

source /308/Public_Enseignement/TER-COMPIL/tpcompil.csh


et lancer ensuite un nouveau shell (par exemple en ouvrant un nouveau terminal).

Le langage Arith

Le langage Arith permet d'évaluer des expressions arithmétiques et de donner un nom à certaines expressions. Un programme du langage Arith est composé d'une suite d'instructions de la forme suivante:
set ident = expr
print expr
où ident est un identificateur et expr est une expression arithmétique pouvant contenir des déclarations de variables locales de la forme:

let ident = expr in expr

Grammaire.
Plus formellement, la syntaxe des instructions de Arith est décrite par la grammaire suivante:

<inst> ::= set <ident>  =  <expr>
  | print <expr>
<expr> ::= <entier>
  | <ident>
  | <expr> <binop> <expr>
  | <unop> <expr>
  | let <ident>  =  <expr>  in  <expr>
  | ( <expr> )
<binop> ::= +  |  -  |  *  |  /
<unop> ::= -

Conventions lexicales.
Espaces, tabulations et retour-chariots constituent les blancs. Les mots set, let, in et print sont des mots-clés (i.e des mots réservés pour notre langage) ; <ident>  est la classe des identificateurs, qui ne peuvent contenir que des caractères alphanumériques et qui commencent nécessairement par une lettre ; enfin <entier>  est une suite non vide de chiffres de 0 à 9. Les opérateurs arithmétiques ont leurs priorités et associativités habituelles.

La machine virtuelle

Le langage cible du compilateur est un sous-ensemble du langage de la machine virtuelle qui sera utilisée pour le projet de compilation. Nous rappelons ici brièvement la partie de cette machine nécessaire pour compiler le langage Arith. Vous pouvez consulter les notes de cours ainsi que la documentation fournie en annexe pour une description complète de son fonctionnement.

L'organisation de la machine virtuelle est décrite par la figure suivante:



La machine contient une zone de code C et un registre pc qui pointe sur l'instruction courante à exécuter. La machine dispose également d'une pile P permettant de stocker des valeurs entières. Trois registres permettent d'accéder à différentes parties de P: sp (stack pointer) pointe sur le premier emplacement vide de la pile, fp (frame pointer) repère l'adresse de base des variables locales et enfin gp pointe sur la base de la pile à partir de laquelle seront stockées les variables globales.

Les instructions de la machine dont vous aurez besoin pour compiler le langage Arith sont les suivantes:

Code Description sp Condition
ADD P[sp-2]:=P[sp-2]+P[sp-1] sp-1 P[sp-2] et P[sp-1] entiers
SUB P[sp-2]:=P[sp-2]-P[sp-1] sp-1 P[sp-2] et P[sp-1] entiers
MUL P[sp-2]:=P[sp-2]*P[sp-1] sp-1 P[sp-2] et P[sp-1] entiers
DIV P[sp-2]:=P[sp-2]/P[sp-1] sp-1 P[sp-2] et P[sp-1] entiers
PUSHI n P[sp]:=n sp+1 n entier
PUSHN n P[sp]:=0 ...P[sp+n-1]:=0 sp+n n entier
PUSHG n P[sp]:=P[gp+n] sp+1 n entier
STOREG n P[gp+n]:=P[sp-1] sp-1 n entier
PUSHL n P[sp]:=P[fp+n] sp+1 n entier
STOREL n P[fp+n]:=P[sp-1] sp-1 n entier
WRITEI imprime P[sp-1] sur l'écran sp-1 P[sp-1] entier
START Affecte la valeur de sp à fp sp  
STOP Arrête l'exécution du programme sp  

Travail demandé

Nous avons délibérément effacé des parties des fichiers contenus dans l'archive arithc.tgz. Le travail qui vous est demandé dans ce TP est de compléter chacun de ces fichiers afin de terminer le compilateur du langage Arith.

Exercice 1 (Arbres de syntaxe abstraite)

Le fichier ast.mli contient les déclarations de type permettant de représenter les programmes du langage Arith sous la forme d'arbres de syntaxe abstraite. Compléter les définitions des types instr, expr et prg en vous aidant de la grammaire du langage Arith.

corrigé: ast.mli

Exercice 2 (Analyse lexicale et syntaxique)

Les fichiers lexer.mll et parser.mly contiennent respectivement l'analyseur lexical et syntaxique de la grammaire du langage Arith. Dans le fichier parser.mly, compléter les déclarations des tokens (ainsi que leurs priorités et associativités) et terminer les définitions des non-terminaux (prog, instrs, instr et expr). Dans le fichier lexer.mll, compléter la règle nexttoken afin de reconnaître les tokens utilisés par l'analyseur syntaxique.

corrigé: lexer.mll, parser.mly

Exercice 3 (Production de code machine)

Le fichier compile.ml contient les fonctions compile_expr, compile_instr et compile_prg qui permettent respectivement de traduire en code machine des valeurs de type expr, instr et prg. Compléter le code de ces trois fonctions.

corrigé: compile.ml

This document was translated from LATEX by HEVEA.