Pour cette séance, on s'intéresse à la partie arrière du compilateur : nous vous fournissons du code s'occupant des analyses lexicale, syntaxique et sémantique, et votre rôle consiste à coder les quatre transformations élémentaires qui vont de la syntaxe abstraite au code assembleur.
Structure du compilateur
Le compilateur utilise successivement plusieurs syntaxes abstraites, de plus en plus éloignées du langage source et de plus en plus proches du langage assembleur :
- Syntaxe abstraite source (SourceAst.ml) : la syntaxe abstraite du langage source, sur laquelle est définie sa sémantique. Elle est obtenue après les analyses lexicale et syntaxique.
- Syntaxe abstraite non typée (UntypedAst.ml) : similaire à la syntaxe abstraite source, mais ne comporte plus aucune mention des types.
- Syntaxe abstraite avec sauts (GotoAst.ml) : les structures de contrôles ont disparu et sont remplacées par des instructions de saut.
- Représentation intermédiaire (IrAst.ml) : les expressions sont décomposées en séquences d'instructions élémentaires. C'est à ce niveau que vous travaillerez sur l'optimisation du code (séances 3 et 4).
- Représentation intermédiaire avec allocation des variables (AllocatedAst.ml) : similaire à la représentation intermédiaire, mais chaque identifiant est maintenant associé à un emplacement physique défini (registre ou emplacement de pile).
Le squelette qui vous est fourni est essentiellement constitué du minimum de code permettant de compiler avec succès le programme base.a6m suivant :
main(integer x) ( print(x); )Vous y trouverez en outre :
- Un module de vérification du typage (SourceTypeChecker.ml)
- Un module de traduction de la syntaxe abstraite source à la syntaxe abstraite non typée (SourcetoUntyped.ml)
- Des modules d'analyse lexicale et syntaxique (PrebuiltLexer.ml et PrebuiltParser.ml) à utiliser avec l'option -frontend du compilateur, en attendant que vos propres modules soit opérationnels (ce sera le sujet de la séance numéro 2).
- Une bibliothèque Mips, qui fournit des primitives pour représenter du code assembleur et générer le texte correspondant.
Travail à effectuer
Chacune des quatre tâches consiste à faire la transition d'une représentation intermédiaire à la suivante, de la syntaxe abstraite non typée jusqu'au code assembleur.1. Traduction des structures de contrôle (UntypedtoGoto.ml)
Cette passe laisse intacte les expressions. En revanche, vous n'avez plus pour représenter les instructions de boucles et de branchements que les trois constructions suivantes :
- Label(lab) : définit une étiquette lab pouvant servir de cible à un saut.
- Goto(lab) : saute à l'instruction suivant l'étiquette lab.
- CondGoto(e, lab) : saute à l'instruction suivant l'étiquette lab si l'expression e vaut vrai.
Exemple, partant du programme source
main(integer x) (
var integer s;
s := 0;
while s*s < x+1 (
s := s+1;
);
print(s+47);
)
pour lequel on a une table des symbole
x -> FormalX, TypInteger
s -> Local, TypInteger
et un code
s := 0;
while s*s < x+1 (
s := s+1;
);
print(s+47);
on peut obtenir le code
s := 0;
goto test_boucle
label debut_boucle
s := s+1;
label test_boucle
goto debut_boucle when s*s < x+1
print(s+47);
2. Traduction des expressions (GototoIr.ml)
Cette passe laisse les instructions essentiellement intactes. En revanche, vous ne pouvez plus appliquer les opérateurs arithmétique qu'à des valeurs déjà calculées : des constantes ou une référence à une variable (l'ensemble formant le type value).
Par exemple, à partir du programme précédent on peut obtenir
s := 0;
goto test_boucle
label debut_boucle
s := s+1;
label test_boucle
tmp1 := s * s
tmp2 := x + 1
tmp0 := tmp1 < tmp2
goto debut_boucle when tmp0
tmp3 := s + 47
print(tmp3);
3. Allocation des variables (IrtoAllocated.ml)
Cette passe ne modifie pas le code, mais uniquement la table des symboles. Chaque variable doit être associée à un emplacement physique, qui pour cette séance sera simplement un emplacement sur la pile (construceur Stack du type alloc_info).
Par exemple, à partir du programme précédent on peut obtenir la nouvelle table de symboles :
x -> Stack(0)
s -> Stack(-4)
tmp0 -> Stack(-8)
tmp1 -> Stack(-12)
tmp2 -> Stack(-16)
tmp3 -> Stack(-20)
4. Génération de code assembleur (AllocatedtoMips.ml)
La représentation intermédiaire obtenue à ce stade est très proche du code assembleur, il n'y a plus qu'à traduire.
L'exemple précédent pourrait mener à
li $t0, 0
sw $t0, -4($fp)
b test_boucle
debut_boucle:
lw $t0, -4($fp)
addi $t0, $t0, 1
sw $t0, -4($fp)
test_boucle:
lw $t0, -4($fp)
lw $t1, -4($fp)
mul $t0, $t0, $t1
sw $t0, -12($fp)
lw $t0, 0($fp)
li $t1, 1
add $t0, $t0, $t1
sw $t0, -16($fp)
lw $t0, -12($fp)
lw $t1, -16($fp)
slt $t0, $t0, $t1
sw $t0, -8($fp)
lw $t0, -8($fp)
bnez $t0, debut_boucle
lw $t0, -4($fp)
addi $t0, $t0, 47
sw $t0, -20($fp)
lw $a0, -20($fp)
li $v0, 11
syscall
li $v0, 10
syscall
La bibliothèque Mips
La bibliothèque Mips fournie permet de décrire du code assembleur Mips en Caml. Le code précédent pourrait être traduit de la manière suivante :li $t0, 0 | li t0 0 sw $t0, -4($fp) | @@ sw t0 (-4) fp b test_boucle | @@ b "test_boucle" debut_boucle: | @@ label "debut_boucle" lw $t0, -4($fp) | @@ lw t0 (-4) fp addi $t0, $t0, 1 | @@ addi t0 t0 1 sw $t0, -4($fp) | @@ sw t0 (-4) fp test_boucle: | @@ label "test_boucle" lw $t0, -4($fp) | @@ lw t0 (-4) fp lw $t1, -4($fp) | @@ lw t1 (-4) fp mul $t0, $t0, $t1 | @@ mul t0 t0 t1 sw $t0, -12($fp) | @@ sw t0 (-12) fp lw $t0, 0($fp) | @@ lw t0 0 fp li $t1, 1 | @@ li t1 1 add $t0, $t0, $t1 | @@ add t0 t0 t1 sw $t0, -16($fp) | @@ sw t0 (-16) fp lw $t0, -12($fp) | @@ lw t0 (-12) fp lw $t1, -16($fp) | @@ lw t1 (-16) fp slt $t0, $t0, $t1 | @@ slt t0 t0 t1 sw $t0, -8($fp) | @@ sw t0 (-8) fp lw $t0, -8($fp) | @@ lw t0 (-8) fp bnez $t0, debut_boucle | @@ bnez t0 "debut_boucle" lw $t0, -4($fp) | @@ lw t0 (-4) fp addi $t0, $t0, 47 | @@ addi t0 t0 47 sw $t0, -20($fp) | @@ sw t0 (-20) fp lw $a0, -20($fp) | @@ lw a0 (-20) fp li $v0, 11 | @@ li v0 11 syscall | @@ syscall li $v0, 10 | @@ li v0 10 syscall | @@ syscall