Le but de cette partie est de produire le code machine correspondant au programme analysé. 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.

Pour les autres parties du projet, on a toujours donné une spécification formelle de ce qu'il fallait implémenter sous forme d'une grammaire lexicale, d'une grammaire syntaxique et de règles de typage. Pour cette partie, on suppose qu'il y a un consensus sur la signification à l'exécution des différents concepts du langage Eins (fonctions, objets, opérateurs, etc). On se passera donc d'une description formelle (en cas de doute, utilisez le forum de discussion).

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 des visiteurs de génération de code peut être faite par étapes. Celles-ci sont décrites ci-dessous. La description de chaque étape commence par l'énumération des nœuds de la syntaxe abstraite qui doivent être implémentés au cours de l'étape.

Étape 1 : les types

T = IntType
  | TypeIdent ident
  | FunType { T } T
    

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

Étape 2 : les expressions arithmétiques

E = IntLit int
  | Binop B E E
  | Unop U E
  | ...

B = Add | Sub | Mul | Div | Mod
  | ...

U = Neg
  | ...
    

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.

Étape 3 : l'expression conditionnelle

E = If E E E
  | ...
    

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

Étape 4 : les classes et les objets

P = Program { D } E

D = ClassDef ident { F }
  | ...

E = New ident { E }
  | Select E ident
  | NullLit
  | ...
    

Une classe définit un type. Ce type est utilisé pendant l'analyse du programme mais n'a pas de contenu calculatoire. Autrement dit, aucune instruction ne doit être générée pour une déclaration de classe. Par contre, pour chaque symbole de champ de la classe, il faut se rappeler de sa position dans la classe. On stocke donc cette position dans le champ offset du symbole (voir classe Symbol).

Si C est une classe avec les champs f1, ..., fn, l'expression new C(e1, ...., en) doit créer un objet tel que si l'on sélectionne le champ fi sur cet objet on obtient la valeur de l'expression ei.

Concrètement, un objet est représenté dans la partie "tas" de la mémoire par une zone contenant les valeurs de ses champs mises côte à côte. La valeur d'un objet est l'adresse du début de cette zone mémoire. La génération de code pour une expression new C(e1, ..., en) ne fait donc rien d'autre qu'allouer une zone mémoire, stocker la valeur des expressions e1 ... en dans cette zone et retourner l'adresse du début de la zone. Les expressions e1 ... en doivent être évaluées de gauche à droite.

La génération de code pour le nœud de sélection de champ (Select) utilise l'information stockée dans le champ offset du symbole associé au champ. La sélection d'un champ sur l'objet null, représenté par l'entier 0, doit être signalée par une erreur 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] objets) peuvent être représentés en mémoire par un mot.

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 déjà fait au début de la méthode caseProgram de la classe Gen.

Étape 5 : les blocs et les variables locales

F = Formal ident T

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

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, appelé bloc d'activation, alloué sur la pile. L'adresse 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 Block doit bien sûr générer le code des énoncés et de l'expression qu'ils contiennent. En plus de cela, ils doivent libérer la mémoire allouée sur la pile par les éventuels nœuds VarDef qu'ils contiennent.

Étape 6 : les boucles

S = While E { S }
  | Do E
  | ...
    

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

Étape 7 : les opérateurs logiques et de comparaisons

E = Unop U E
  | Binop B E E
  | ...

U = Not
  | ...

B = Or
  | Eq | Ne | Lt | Le | Gt | Ge
  | ...
    

Étape 8 : les fonctions

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.

Les arguments des fonctions doivent être évalués de gauche à droite avant d'être passés à la fonction.

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-partial.java (à renommer en Generator.java) contient les visiteurs 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.

Parfois l'exécution d'un programme Eins échoue à cause d'un dépassement de la mémoire. Il est possible de dire à l'interpréteur d'utiliser une taille plus grande pour la mémoire :

        risc-emu -mem=1000000 monfichier.risc
      

Pour utiliser les émulateurs RISC sur votre ordinateur personnel, vous pouvez télécharger l'une des deux archives suivantes: risc-20050120.tar.gz ou risc-20050120.zip. Aprés désarchivage, les exécutables se trouvent dans le répertoire bin.

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

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.