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 son « vrai » travail, 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 représentant le programme et de produire, pour chaque nœud, le code qui lui correspond. La production de code s'organise donc autour d'un visiteur.

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.

T = UnitType
  | IntType
  | ListType T
  | FunType { T } T.

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

E = Operation O E [ E ]
  | UnitLit
  | IntLit int
  | ...

O = Eq | Add
  | Ne | Sub
  | Lt | Mul
  | Le | Div
  | Gt | Mod
  | 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.

E = If E E E
  | ...

Le but de la trosième étape est d'ajouter la gestion des expressions conditionnelles au compilateur. Pour ce faire, commencez par ajouter les items conditionnels, comme cela a été vu au cours, puis utilisez-les pour compiler les expressions conditionnelles.

E = Operation O E [ E ]
  | NilLit
  | ...

O = Cons
  | 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, comme en Lisp. Une liste n'est donc rien d'autre qu'une paire dont le premier élément contient la tête de la liste, et le second sa queue. La queue peut être la liste vide [], 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 booléens, 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::[] 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 Generator.

S = VarDecl ident T E
  | ...

E = Assign ident E
  | Ident ident
  | Block { 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 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 de la pile (stack size).

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. Le seul point auquel il faut faire attention est qu'il faut libérer tous les registres qui ont été alloués lors de cette génération. Ces registres, s'il y en a, sont tous reférencés par l'item retourné par l'appel à generate et peuvent donc être libérés en appelant la méthode freeRegisters sur cet item.

start: ...             // code de la condition
       B?? R? exit     // sortie de la boulce
       ...             // code du corps
       BEQ R0 start    // retour au début de la boucle
exit : ...             // suite du programme

P = Program { D } E.

D = FunDecl ident { F } T E.

F = Formal ident T.

E = FunCall 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.

N'oubliez pas que, en misc, on peut manipuler les fonctions comme n'importe quelle autre donnée, via les pointeurs de fonction.

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

• Code.java contient les méthodes pour produire les instructions assembleur.
• Item.java contient la classe Item et ses sous-classes, dont la plupart sont à compléter au fur et à mesure.
• 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.
• Main.java contient le programme principal (la seule différence avec GeneratorTest.java est que ce programme génère un fichier avec l'extension .risc lorsque aucun fichier objet n'est spécifié).
• 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.

Les fichiers pour le projet en Scala : Code.scala, Item.scala, Generator.scala, GeneratorTest.scala, RISC.java (attention il est différent de celui pour le projet en Java).

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.

Nom	Taille	Utilisation
a, b, c	5 bits	Numéros de registres
ic	16 bits	Entier signé
uc	16 bits	Entier non signé
oc	21 bits	Déplacement signé
lc	26 bits	Adresse non signée