Le but de cette partie est de produire le code machine correspondant au programme analysé, en fonction des règles sémantiques du langage. Toutes les étapes précédentes avaient pour seul but de s'assurer que le programme était correct par rapport aux règles du langage, et de transformer le programme textuel en une forme facilement manipulable: l'arbre abstrait. Une fois ce travail préparatoire effectué, le compilateur peut commencer avec la production de code cible.

La production de code nous occupera jusqu'à la fin du semestre. Nous séparerons cette partie en plusieurs étapes, que nous vous conseillons d'effectuer dans l'ordre donné, mais vous êtes bien entendu libres de vous organiser comme bon vous semble.

L'idée générale de la production de code est relativement simple: il s'agit de parcourir l'arbre abstrait et de produire, pour chaque nœud, le code qui lui correspond. La production de code s'organise donc autour des visiteurs.

L'implémentation des différents cas du visiteur peut être faite par étapes. Celles-ci sont décrites ci-dessous. La description de chaque étape commence par l'énumération des productions de la grammaire abstraite qui doivent être implémentées au cours de l'étape.

Étape 1

T = BasicType U
  | ListType T
  | FunType { T } T

Les déclartions de types ne produisent pas de code et les méthodes caseBasicType, caseFunType, caseFunType ne devraient jamais être appelées. Ces méthodes peuvent donc simplement rester vide.

Étape 2

E = Binop O E E
  | UnitLit
  | IntLit int
  | ...

O = Add
  | Sub
  | Mul
  | Div
  | Mod
  | Eq
  | Ne
  | Lt
  | Le
  | Gt
  | Ge
  | ...

Le but de la deuxième étape est de produire du code pour les expressions arithmétiques. À la fin de cette étape, le compilateur devrait être capable de compiler des programmes constitués d'une simple expression arithmétique, comme (1+2)*3.

Au cours de cette étape, on produit également le code pour la valeur () (le nœud UnitLit). Cette valeur est simplement représentée par l'entier 0.

Étape 3

E = If E E E
  | ...

Le but de la troisième étape est d'ajouter la gestion des expressions conditionnelles au compilateur.

Étape 4

E = Binop O E E
  | Listop L E
  | NilLit
  | ...

O = Cons
  | ...
  
L = Head
  | Tail
  | IsEmpty

Le but de la quatrième étape est d'ajouter la gestion des listes au compilateur. La représentation que nous allons utiliser pour les listes est basée sur des paires dont le premier élément contient la tête de la liste, et le second sa queue. La queue peut être la liste vide List(), que l'on représente par la constante 0.

En mémoire, on représente les paires par une zone contenant les deux éléments de la paire côte à côte. On manipule ces zones au moyen de pointeurs qui pointent vers leur début. L'opérateur :: ne fait donc rien d'autre que d'allouer une telle zone, puis il y place la tête et la queue de la liste, avant de retourner un pointeur vers la zone. L'opérateur head extrait pour sa part la première valeur d'une telle zone, tail extrait la seconde, et isEmpty vérifie si le pointeur qu'elle reçoit est nul. Bien entendu, head et tail doivent signaler une erreur s'ils sont appliqués à la liste vide, au moyen de l'appel système SYS_EXIT.

Il faut noter que toutes les données que nous utilisons dans le langage (les entiers, les pointeurs de fonction et les [pointeurs vers les] listes) peuvent être représentés en mémoire par un mot. Cela implique que toutes les paires ont la même taille en mémoire, et que les opérateurs ::, head, tail et isEmpty fonctionnent donc de manière uniforme quel que soit le type du contenu de la liste sur laquelle ils agissent.

La figure ci-dessous montre comment la liste 1::2::3::4::List() peut être représentée en mémoire. Les flèches représentent des pointeurs.

Pour allouer la mémoire, vous devez utiliser l'appel système SYS_GC_ALLOC. Son utilisation implique d'initialiser l'allocateur mémoire. Cela est fait au début de la méthode caseProgram de la classe Gen.

Étape 5

F = Formal ident T

S = VarDef F E
  | ...
  
E = Assign ident E
  | Ident ident
  | B
  | ...

B = Body { S } E

Le but de la cinquième étape est d'ajouter la gestion des blocs, des variables locales et des affectations. Pour cela, il vous faut gèrer la pile. Comme vous l'avez vu au cours, chaque appel de fonction a le droit d'utiliser un bloc de mémoire, appelé bloc d'activation, alloué sur la pile. L'addresse du début de ce bloc ne change pas au cours d'un appel donné; il est désigné par FP (frame pointer). La fin du bloc est variable; elle est repérée par le registre SP (stack pointer). La différence entre SP et FP est appelée la taille du bloc d'activation (frame size).

Lors de la génération de code, vous devez calculer pour chaque instruction quelle est la taille du bloc d'activation. Pour cela, la classe Code fournit les méthodes incFrameSize, decFrameSize et getFrameSize.

Le nœud Formal déclare une nouvelle variable qui est placée au sommet de la pile. Afin que les nœuds Assign et Ident puissent accéder à cette variable, il faut qu'ils sachent où elle se trouve sur la pile. Pour cela, on utilise le champ offset de la classe Symbol. Ce champ contient la position de la variable sur la pile par rapport à FP. Il doit être initialisé par le nœud Formal.

Pour générer le code du nœud Assign, on utilise le symbole qui a été stocké dans le nœud lors de l'analyse des types. Le champ offset de ce nœud désigne la position sur la pile à laquelle la valeur doit être stockée.

La génération de code des nœuds Body doit bien sûr générer le code des instructions et de l'expression qu'ils contienent. En plus de cela, ils doivent libérer la mémoire allouée par d'éventuels nœuds VarDef qu'ils contiennent.

Étape 6

S = While E E
  | Exec E
  | ...

Le but de la sixième étape est d'ajouter la gestion des boucles while et des expressions utilisées en tant qu'instruction. La génération de code pour les nœuds Exec revient simplement à générer le code de son expression.

Étape 7

P = Program { D } B

D = FunDef ident { F } T E

E = Apply E { E }
  | ...

Le but de la septième et dernière étape est d'ajouter la gestion des fonctions au compilateur.

La gestion des fonctions inclut les fonctions prédéfinies printInt, printChar, readInt et readChar. Ces fonctions peuvent être traitées de manière tout à fait standard si on prend soin de produire leur code avant de produire le reste du code.

Pour cette étape, nous vous fournissons les fichiers suivants :

• Code.java contient les méthodes pour produire les instructions assembleur.
• Generator.java contient le visiteur de génération de code. Il s'agit du principal fichier à compléter.
• GeneratorTest.java contient le programme de test.
• DefaultVisitor.java: Visiteur comportant un cas par défaut.
• RISC.java contient la définition de diverses constantes liées au processeur DLX, par exemple des constantes pour les instructions et pour les appels système (entrées/sorties, glaneur de cellules, ...). Les commentaires importants qui figurent dans ce fichier sont aussi disponibles sous forme HTML.

Pour tester les programmes produits par votre compilateur, nous mettons à votre disposition un interpréteur et un débogueur graphique simple. Ces outils prennent un certain nombre d'options, dont vous pouvez obtenir la liste en les lançant avec l'option -h.

L'interpréteur se lance en tapant ~iclamp/soft/bin/risc-emu, tandis que le débogueur se lance en tapant ~iclamp/soft/bin/risc-gui.

L'architecture utilisée a brièvement été présentée au cours. Les éléments importants sont rappelés ici.

Le processeur comporte 32 registres, numérotés de 0 à 31. Quelques registres ont un usage particulier :

• R0 contient toujours la valeur 0 et n'est pas modifiable,
• R1 est utilisé pour stocker le résultat au retour d'un appel de fonction.
• R31 est utilisé par les instructions d'appel (BSR et JSR) pour stocker l'adresse de retour,
• R30 est utilisé pour stocker le pointeur de pile SP (stack pointer),

À noter que le pointeur de pile doit être initialisé au début du programme. Cela est fait au début de la méthode caseProgram de la classe Gen.

Toutes les instructions sont codées au moyen de 32 bits. Certaines parties de ces 32 bits peuvent contenir des constantes, dont il est important de connaître la taille au moment de la production de code. Sur la feuille distribuée au cours et décrivant le jeu d'instruction, ainsi que dans la documentation de l'interface RISC, ces constantes sont identifiées par un nom. La table ci-dessous donne la taille de ces constantes.