Projet de programmation 1: compilateur de C--Jean Goubault-Larrecq |
LSV/UMR 8643, CNRS, ENS Cachan & INRIA Futurs projet SECSI |
61 avenue du président-Wilson, F-94235 Cachan Cedex |
goubault@lsv.ens-cachan.fr |
Phone: +33-1 47 40 75 68 Fax: +33-1 47 40 75 21 |
Le cours de programmation s’étend tout au long de la 1ère année à Cachan. Vous aurez à y faire plusieurs projets. Le tout premier d’entre eux a lieu au premier trimestre de l’année scolaire.
Il s’agit d’écrire un compilateur pour un sous-ensemble strict du langage C, que nous appellerons C--. Le langage cible sera l’assembleur x86. Votre compilateur sera écrit en OCaml.
Voici un exemple de programme que votre compilateur devrait compiler:
Ce programme, qui sera un de nos exemples le premier jour de cours code la commande Unix cat.
Au passage, j’ai évidemment fait le projet avant vous. Voici ce que mon compilateur produit:
.globl main main: pushl %ebp movl %esp, %ebp subl $8, %esp movl $1, %eax movl %eax, -8(%ebp) jmp .main_1 .main_2: subl $4, %esp movl $.main_3, %eax pushl %eax movl -8(%ebp), %eax pushl %eax movl 12(%ebp), %eax popl %ebx movl (%eax, %ebx, 4), %eax pushl %eax call fopen addl $8, %esp movl %eax, -12(%ebp) jmp .main_4 .main_5: movl stdout, %eax pushl %eax movl -4(%ebp), %eax pushl %eax call fputc addl $8, %esp .main_4: movl $1, %eax negl %eax pushl %eax movl -12(%ebp), %eax pushl %eax call fgetc addl $4, %esp movl %eax, -4(%ebp) popl %ebx cmpl %ebx, %eax je .main_8 movl $0, %eax jmp .main_9 .main_8: movl $1, %eax .main_9: cmpl $0, %eax je .main_6 movl $0, %eax jmp .main_7 .main_6: movl $1, %eax .main_7: cmpl $0, %eax jnz .main_5 movl -12(%ebp), %eax pushl %eax call fclose addl $4, %esp addl $4, %esp movl -8(%ebp), %eax addl $1, -8(%ebp) .main_1: movl 8(%ebp), %eax pushl %eax movl -8(%ebp), %eax popl %ebx cmpl %ebx, %eax jl .main_10 movl $0, %eax jmp .main_11 .main_10: movl $1, %eax .main_11: cmpl $0, %eax jnz .main_2 movl stdout, %eax pushl %eax call fflush addl $4, %esp movl $0, %eax pushl %eax call exit addl $4, %esp addl $8, %esp movl %ebp, %esp popl %ebp ret .main_3: .asciz "r" .align 4 |
Ceci peut vous sembler bien mystérieux. C’est normal! Ça le sera moins après le premier cours.
D’abord, je vous recommande de travailler sous Linux, et plus spécifiquement (à Cachan) sur les machines de la salle C411. Il vous faut un Linux 32 bits, ou 64 bits depuis l’année 2013 (merci à Lucca Hirschi).
Si vous voulez travailler chez vous, et que votre machine est sous Windows, ou Mac OS, je vous recommande de travailler sous VirtualBox: voir en section 8 pour les détails pratiques.
Le projet sera écrit en OCaml. Toutes les versions de Caml ou OCaml ≥ 2.04 devraient faire l’affaire.
Ensuite, vous devez récupérer
l’archive
du projet. Décompressez-là avec bzip2
et désarchivez le
tout avec tar
(ou avec 7zip
sous Windows; sur MacOSX, double-cliquez). Vous pouvez faire le tout en une seule étape en
tapant tar xvjf projetminic.tbz
.
Vous devriez obtenir un répertoire MiniC
et
les fichiers suivants:
drwxr-xr-x goubault/lsv 0 2005-09-26 17:57:13 ProjetMiniC/ -rw-r--r-- goubault/lsv 1041 2005-10-07 11:15:35 ProjetMiniC/genlab.ml -rw-r--r-- goubault/lsv 396 2005-09-26 17:56:08 ProjetMiniC/cat.c -rw-r--r-- goubault/lsv 12949 2005-10-07 11:15:35 ProjetMiniC/clex.mll -rw-r--r-- goubault/lsv 2198 2005-10-07 11:15:35 ProjetMiniC/main.ml -rw-r--r-- goubault/lsv 226254 2005-10-07 11:15:35 ProjetMiniC/clex.ml -rw-r--r-- goubault/lsv 936 2005-10-07 11:15:35 ProjetMiniC/verbose.ml -rw-r--r-- goubault/lsv 2752 2005-10-07 11:15:35 ProjetMiniC/error.ml -rw-r--r-- goubault/lsv 12910 2005-10-07 11:15:35 ProjetMiniC/ctab.mly drwxr-xr-x goubault/lsv 0 2005-10-07 11:15:36 ProjetMiniC/Exemples/ -rw-r--r-- goubault/lsv 459 2005-10-07 11:15:36 ProjetMiniC/Exemples/cat.c -rw-r--r-- goubault/lsv 1308 2005-10-07 11:15:36 ProjetMiniC/Exemples/cat.s -rw-r--r-- goubault/lsv 739 2005-10-07 11:15:36 ProjetMiniC/Exemples/fact.c -rw-r--r-- goubault/lsv 7256 2005-10-07 11:15:36 ProjetMiniC/Exemples/sieve.s -rw-r--r-- goubault/lsv 2064 2005-10-07 11:15:36 ProjetMiniC/Exemples/sieve.c -rw-r--r-- goubault/lsv 2425 2005-10-07 11:15:36 ProjetMiniC/Exemples/fact.s -rw-r--r-- goubault/lsv 1214 2005-10-07 11:15:35 ProjetMiniC/ctab.mli -rw-r--r-- goubault/lsv 9081 2005-10-07 11:15:35 ProjetMiniC/cparse.ml -rw-r--r-- goubault/lsv 521 2005-10-07 11:15:35 ProjetMiniC/depend -rw-r--r-- goubault/lsv 981 2005-10-07 11:15:35 ProjetMiniC/compile.mli -rw-r--r-- goubault/lsv 52296 2005-10-07 11:15:35 ProjetMiniC/ctab.ml -rw-r--r-- goubault/lsv 1849 2005-10-07 11:15:35 ProjetMiniC/Makefile |
Votre travail consiste à écrire le fichier manquant
compile.ml
. Vous pouvez y écrire ce que
vous voulez, l’important est de définir la fonction dont le type est
spécifié dans le fichier d’interface
compile.mli
:
val compile : out_channel -> Cparse.var_declaration list -> unit;;
Cette fonction prend un canal de sortie en premier argument,
appelons-le out
, et un programme C--,
appelons-le π, et imprime sur out
un texte
en assembleur x86 qui code le programme π. Ce texte en assembleur
ressemblera donc au texte de l’introduction (voir le fichier
cat.s).
Lorsque vous aurez écrit le fichier
compile.mli
, compilez le tout en invoquant
make
. Comme vous l’aura sûrement expliqué
Sébastien, ceci va appliquer un certain nombre de commandes dans un
ordre défini par les dépendances exprimées dans le fichier
Makefile
.
Le résultat sera un programme, qui s’appellera
mcc
et sera dans le répertoire
ProjetMiniC
. Vous pourrez tester ce
programme en tapant ./mcc
suivi du nom d’un fichier C-- à compiler.
Par exemple, si vous tapez (en partant du répertoire
ProjetMiniC
):
cd Exemples ../mcc cat.c |
Ceci devrait produire un fichier assembleur
cat.s
, que vous pourrez consulter, et un
fichier exécutable cat
, que vous pourrez
tester en tapant (sous le répertoire
ProjetMiniC/Exemples
):
./cat cat.s |
Il est évidemment plus que probable que le code assembleur que vous
produisiez, au moins au début, ne soit pas de la meilleure qualité.
Notamment, mcc
appelle le compilateur
gcc
pour compiler le code assembleur que
vous aurez produit vers un vrai exécutable. Si votre code assembleur
n’est pas syntaxiquement correct, ceci échouera. Il se peut aussi que
vous obteniez un exécutable, mais qu’il plante (message
Segmentation fault
, typiquement).
Dans tous les cas, vous pouvez:
mcc
à ne produire que le code
assembleur, sans le compiler. Appelez-le avec l’option
-E
:
../mcc -E cat.c |
compile
produit. Vous pouvez envoyer ce
code dans un fichier, disons cat.s
encore
une fois, par:
../mcc -E cat.c >cat.s |
ddd
. Si vous ne
l’avez pas, rabattez-vous sur xxgdb
, ou
dans le pire des cas sur gdb
. Utilisez
les commandes
ddd
pour voir le contenu des registres
de la machine. Sous gdb
, tapez
info registers
pour le même effet (en moins beau).
%esp
vaut 0xbffff8e0
,
tapez 0xbffff8d0
dans le champ “from” pour voir un peu de
part et d’autre de 0xbffff8e0
. Sous
gdb
, vous obtiendrez le même effet (en
moins beau) avec l’incantation:
Vous pouvez allez regarder les fichiers que vous voulez. Le seul
fichier que vous n’aurez pas est celui que vous avez à écrire,
compile.ml
.
Vous n’avez le droit de modifier aucun des fichiers de
l’archive
du projet. En fait, vous devrez vous limiter à écrire vos
fonctions dans le fichier compile.ml
. L’idée,
c’est que si je prends votre fichier compile.ml
et je l’ajoute à l’archive, que je tape
make
, j’obtiens un compilateur fonctionnel
pour C--.
Une autre façon de le dire: vous pouvez aller bidouiller les autres
fichiers du projet si ça vous chante, par exemple, pour ajouter des
appels à Printf.printf
, et voir comment ça
marche, mais vous ne devez pas faire des modifications dans ces
fichiers qui soit essentielles à la bonne marche de votre compilateur.
D’abord, quand on exécute mcc
, il va
commencer par exécuter le code qui se trouve dans le fichier
main.ml
.
Celui-ci lit les options de commande (-E
par
exemple), puis appelle l’analyseur syntaxique
Ctab.translation_unit
, auquel on passe
l’analyseur lexical Clex.ctoken
.
Le source de l’analyseur syntaxique, qui servira aussi de
documentation pour la grammaire du langage C--, est dans le fichier
ctab.mly
. La description des
tokens lexicaux est dans clex.mll
.
L’analyseur syntaxique fournit un programme sous forme d’une liste de
Cparse.var_declaration
. Les d’une liste de
var_declaration
sont déclarées au début du
fichier cparse.ml
, comme suit:
type mon_op = M_MINUS | M_NOT | M_POST_INC | M_POST_DEC | M_PRE_INC | M_PRE_DEC (* Les operations unaires: M_MINUS: calcule l'oppose -e de e; M_NOT: calcule la negation logique ~e de e; M_POST_INC: post-incrementation e++; M_POST_DEC: post-decrementation e--; M_PRE_INC: pre-incrementation ++e; M_PRE_DEC: pre-decrementation --e. *) type bin_op = S_MUL | S_DIV | S_MOD | S_ADD | S_SUB | S_INDEX (* Les operations binaires: S_MUL: multiplication entiere; S_DIV: division entiere (quotient); S_MOD: division entiere (reste); S_ADD: addition entiere; S_SUB: soustraction entiere; S_INDEX: acces \`a un element de tableau a[i]. *) type cmp_op = C_LT | C_LE | C_EQ (* Les operations de comparaison: C_LT (less than): <; C_LE (less than or equal to): <=; C_EQ (equal): ==. *) type loc_expr = locator * expr and expr = VAR of string (* une variable --- toujours de type int. *) | CST of int (* une constante entiere. *) | STRING of string (* une constante chaine. *) | SET_VAR of string * loc_expr (* affectation x=e. *) | SET_ARRAY of string * loc_expr * loc_expr (* affectation x[e]=e'. *) | CALL of string * loc_expr list (* appel de fonction f(e1,...,en) *) (* operations arithmetiques: *) | OP1 of mon_op * loc_expr (* OP1(mop, e) denote -e, ~e, e++, e--, ++e, ou --e. *) | OP2 of bin_op * loc_expr * loc_expr (* OP2(bop,e,e') denote e*e', e/e', e%e', e+e', e-e', ou e[e']. *) | CMP of cmp_op * loc_expr * loc_expr (* CMP(cop,e,e') vaut e<e', e<=e', ou e==e' *) | EIF of loc_expr * loc_expr * loc_expr (* EIF(e1,e2,e3) est e1?e2:e3 *) | ESEQ of loc_expr list (* e1, ..., en [sequence, analogue a e1;e2 au niveau code]; si n=0, represente skip. *) type var_declaration = CDECL of locator * string (* declaration de variable de type int. *) | CFUN of locator * string * var_declaration list * loc_code (* fonction avec ses arguments, et son code. *) and loc_code = locator * code and code = CBLOCK of var_declaration list * loc_code list (* { declarations; code; } *) | CEXPR of loc_expr (* une expression e; vue comme instruction. *) | CIF of loc_expr * loc_code * loc_code (* if (e) c1; else c2; *) | CWHILE of loc_expr * loc_code (* while (e) c1; *) | CRETURN of loc_expr option (* return; ou return (e); *) |
Le type locator
est juste un pointeur sur des
informations permettant aux fonctions
Error.error
et
Error.warning
d’afficher des message d’erreur
sensés.
Le fichier cparse.ml
contient aussi des
fonctions utiles, comme string_of_loc_expr
,
qui vous permettent d’obtenir une version imprimable d’une expression
C--, ce que vous pouvez utiliser en phase de débogage.
Le fichier genlab.ml
contient une fonction
genlab
qui vous permettra de fabriquer des labels uniques,
ce qui devrait être bien pratique lorsque vous émettrez des
instructions de saut dans votre code assembleur.
Le fichier verbose.ml
déclare une variable
verbose
que vous pourrez tester pour régler
le niveau d’informations de débogage que vous voudrez afficher (elle
vaut 1 si vous appelez mcc
avec l’option
-v1
, 2 si avec l’option
-v2
, et 0 par défaut).
C-- est un sous-ensemble extrêmement réduit du langage C. Ont été
supprimés de C: tous les types struct
,
union
, enum
, ainsi que
les tableaux, et la plupart des types scalaires. En fait, il ne reste
que les types int
,
char *
, et les pointeurs sur les types C-- (récursivement).
L’avantage est que tous ces types tiennent sur 32 bits (64 bits en version 64 bits). Vous n’aurez donc pas à vous casser la tête pour savoir combien de place allouer à chaque variable: ce sera toujours 4 octets (8 octets en version 64 bits).
Ensuite, de nombreuses constructions de C ont été supprimées, mais pas suffisamment pour ne pas pouvoir compiler des programmes intéressants.
En principe, C-- est un sous-ensemble de C, ce qui signifie que vous
pourrez tester mcc
en comparant les
programmes qu’il produit avec ceux produits par
gcc
.
Il n’y a qu’une exception à ce principe: l’arithmétique sur les
pointeurs a une sémantique différente en C-- et en C. Si vous
déclarez int *p
et écrivez
p++
en C, ceci ajoute
sizeof(int)
, soit 4, à l’adresse
p
. En C–, ça n’est censé qu’ajouter un. Je
doute que vous ayez à considérer ce genre de subtilités, mais qui
sait.
Elle est définie dans le cours: voir la section 1.6 du poly de sémantique numéro 1.
Voir l’annexe A (pour les architectures 32 bits) et l’annexe B (pour les architectures 64 bits) de la leçon numéro 2.
Un moyen portable de travailler sur le projet, évitant ainsi par exemple les problèmes de largeur de mot (32 ou 64 bits), est de travailler sous un émulateur.
Je vous conseille VirtualBox. Attention: avant de vous lancer dans la procédure qui suit, assurez-vous d’avoir une connexion à Internet, si possible haut débit. Vous en aurez besoin jusqu’au bout.
Vous aurez aussi besoin de suffisamment d’espace disque disponible. L’installation que je vous propose fait 5,1 Go. Assurez-vous d’avoir au moins 6 Go (gigaoctets) libres sur votre disque.
Récupérez d’abord VirtualBox, en suivant le lien https://www.virtualbox.org/.
Allez ensuite chercher l’installation que je vous ai préparée, en
http://www.lsv.ens-cachan.fr/~goubault/CoursProgrammation/minicfiles.tgz.
Ca peut vous prendre du temps: c’est une archive d’environ 2,35 Go...
Décompressez. Sous Windows, il vous faudra un archiveur, comme
7zip
. Sous Unix, utilisez tar xvzf
:
tar xvzf minicfiles.tgz
Sous MacOS X, double-cliquez pour décompresser.
Installez-là où vous voulez. Je vais faire l’hypothèse que vous êtes
sous un système Unix (pour commencer), sous le répertoire
/home/toto/
. La commande ci-dessus a créé un répertoire
/home/toto/MiniC/
Tapez la commande magique:
vboxmanage registervm /home/toto/MiniC/MiniC.vbox
Sous Windows, c’est la même commande, mais avec \
au lieu de
/
, par exemple:
vboxmanage registervm "C:Program Files\MiniC\MiniC.vbox"
En général, le dernier argument doit être le chemin complet du fichier
MiniC.vbox
.
La création d’une machine virtuelle est assez intuitive. Une fois VirtualBox installé, lancez-le, et suivez les instructions. Je vous décris comment ça se passe chez moi, sur un MacBook Pro (l’interface peut changer légèrement sur d’autres machines). Prévoyez quand même une bonne heure, à vue de nez.
Avant de continuer, allez récupérer une image de disque de démarrage. Vu ce que l’on a fait plus haut, allez récupérer une installation Linux Debian.
Vous pouvez maintenant lancer la machine virtuelle. Lors du premier démarrage, VirtualBox va vous demander le disque de démarrage ci-dessus, pour installation Linux Debian.
debian-6.0.5-i386-netinst.iso
si vous
avez fait comme moi).
debian-6.0.5-i386-netinst.iso
, vu comme lecteur de CD.
Cliquez sur “Start”.
minic-
<votre nom>”. Par exemple, ma
machine virtelle s’appelle minic-goubault-larrecq
. (À ce
stade, vous vous apercevrez sans doute que votre clavier n’est
toujours pas bien configuré: le “_
” s’obtient en tapant sur
la touche “6” au-dessus du “T” et du “Y”.)
Il est fortement déconseillé d’utiliser un mot de passe que vous utiliseriez déjà par ailleurs: vous ne voulez pas qu’une attaque depuis le réseau sur votre machine virtuelle compromette le reste de votre machine ou divulgue vos informations bancaires à l’extérieur (si vous utilisez votre machine aussi pour faire des achats en ligne...)
guest
.
Choisissez le “modèle du clavier” adéquat (par exemple, chez moi, “Macbook/Macbook pro”).
Sur le Macintosh, cliquez aussi sur “Options...”, puis sur “Touche sélectionnant le 3e niveau”, puis sur la case “Alt gauche”. Ceci vous permettra de taper “|” via alt-gauche + “L”, comme sous le Mac. Cliquez “Fermer”.
Il faut maintenant installer des logiciels. La commande en ligne,
pour les plus courageux, est apt-get install
suivi du nom du
paquet. Mais allez plutôt dans le menu “Système”, sous-menu
“Administration”, “Gestionnaire de paquets Synaptic”.
Il vous demande le mot de passe. C’est celui de “root” qu’il vous faut. J’espère que vous vous en souvenez... sinon, tant pis, recommencez tout depuis le début.
gedit
, auquel
vous pouvez accéder dans le menu “Applications”, sous-menu
“Accessoires”, “Editeur de textes gedit”. Pour les fans,
utilisez synaptic et installez xemacs21
.
gcc
est déjà installé aussi, mais pas
gdb
. Dans synaptic, cliquez sur la loupe “Rechercher” tout
en haut à droite (pas dans la case “Quick search”, qui ne fait de
recherche que sur les paquets déjà affichés). A “Rechercher”,
tapez “gdb”. Le bouton “Rechercher dans:” doit marquer “Nom”
plutôt que “Description et nom”. Il vous propose plusieurs noms
de paquets, cliquez sur “gdb”, ou mieux sur “xxgdb” si vous
voulez une interface graphique. De façon alternative, installez
ddd
(même procédure).Une fois tout ça fait, cliquez sur le bouton “Appliquer” en haut de la fenêtre, au milieu. C’est bête, mais si vous ne le faites pas, c’est comme si vous n’aviez rien fait.
Enfin, téléchargez le projet:
projetminic.tbz
sous le répertoire /home/guest/Downloads/
cd ~/Downloads tar xvjf projetminic.tbz cd ProjetMiniC make
compile.ml
manque. C’est normal! C’est celui que vous
devrez écrire.
Bon courage, et travaillez bien! N’hésitez pas à nous contacter: goubault@lsv.ens-cachan.fr.
This document was translated from LATEX by HEVEA.