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

1  Introduction

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.

2  Comment ça se passe

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:

3  Quelques règles du jeu

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.

4  L’architecture de mcc

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).

5  Le langage C--

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.

6  La sémantique opérationnelle à grands pas de C--

Elle est définie dans le cours: voir la section 1.6 du poly de sémantique numéro 1.

7  Guide de référence rapide de l’assembleur x86

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.

8  Installer VirtualBox

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.

8.1  La façon simple

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.

8.2  La façon compliquée

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.

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.

Enfin, téléchargez le projet:

9  Un dernier mot

Bon courage, et travaillez bien! N’hésitez pas à nous contacter: goubault@lsv.ens-cachan.fr.


This document was translated from LATEX by HEVEA.