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 Zwei (méthodes, objets, opérateurs, etc). On se passera donc d'une description formelle (en cas de doute, utilisez le forum de discussion ou l' interpréteur Zwei que nous vous fournissons).

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 du pattern matching (ou des visiteurs en Java).

L'implémentation des différents cas des fonctions 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 0 : Les primitives d'entrée-sortie

E = ReadInt
  | ReadChar
  | ...

S = PrintInt E
  | PrintChar E
  |...
    

La génération de code pour les primitives d'entrée-sortie consiste simplement à utiliser les appels-système correspondants : SYS_IO_RD_INT, SYS_IO_RD_CHR, SYS_IO_WR_INT et SYS_IO_WR_CHR (et aussi SYS_IO_FLUSH pour forcer l'affichage).

Étape 1 : Les types

T = ClassType name
  | IntType
  | NullType
    

Les occurrences de types ne produisent pas de code, il n'est donc pas nécessaire de définir la génération de code pour les nœuds ClassType, IntType et NullType.

É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 (sans les méthodes) et les objets

P = Program { D } E

D = ClassDef name [ name ] { M }
  | ...

M = FieldDecl name T
  | ...

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

Dans un premier temps, on choisit de ne pas s'occuper de la génération de code pour les définitions de méthode et les appels de méthode. Ce travail est décrit plus tard, dans l'étape 8.

Pour chaque 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 correspondant (voir classe Symbol). Il se peut que cela ait déjà été fait pendant la phase d'analyse de types.

Si C est une classe avec les champs f1, ..., fn (cette liste inclut les champs hérités), 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 un pointeur vers sa table de méthode virtuelle et les valeurs des champs de l'objet, tout mis 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. Dans cette étape, un espace doit aussi être prévu pour la table des méthodes virtuelles, mais ne doit pas être initialisé (vous le ferez à l'étape 8). 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 E name utilise l'information stockée dans le champ offset du symbole contenu dans Name. 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 manipulons dans le langage (les entiers 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 l'implémentation du cas Program dans la fonction gen.

Étape 5 : Les blocs et les variables locales

S = Var name T E
  | Set name E 
  | ...

E = Ident name
  | 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 Var déclare une nouvelle variable qui est placée au sommet de la pile. Afin que les nœuds Set 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é pendant la génération de code pour le nœud Var.

Pour générer le code du nœud Set name E, on utilise le symbole qui a été stocké dans name lors de l'analyse des types. Le champ offset de ce symbole désigne la position sur la pile à laquelle la nouvelle valeur E 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 finale qu'ils contiennent. En plus de cela, ils doivent libérer la mémoire allouée sur la pile par les éventuels nœuds Var 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 (nœud Do) 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 l'expression qu'il contient.

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

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

U = Not
  | ...

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

Étape 8 : Les méthodes

M = MethodDef name { name T } T E
  | ...

E = Call E name { E }
  | ...
    

Le but de la septième et dernière étape est d'ajouter la gestion des méthodes au compilateur. Cela inclut le calcul de la table des méthodes virtuelles pour chaque classe, la génération de code pour les définition de méthodes et pour les appels de méthodes. Il vous faudra aussi retoucher la génération de code pour le nœud New de manière à stocker au début de chaque object un pointeur vers la table des méthodes virtuelles de sa classe.

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

Le programme de test GeneratorTest.scala vous permet de tester votre générateur de code. Il lit un fichier source et affiche le code assembleur généré.

Pour lancer le programme à partir du répertoire racine de votre projet, utilisez la commande suivante :

La sortie est simplement affichée à l'écran si l'argument fichier-destination n'est pas spécifié.

Pour le fichier d'exemple Factorial.zwei on obtient ceci:

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

Code.scala contient les méthodes pour produire les instructions assembleur.

Generator-partial.scala (à renommer en Generator.scala) contient les fonctions de génération de code. Il s'agit du principal fichier à compléter.

GeneratorTest.scala contient le programme de test.

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.

Le fichier compressé part5.zip contient tous les fichiers Scala dont vous avez besoin pour la partie 5 (part5.zip contient également les fichiers fournis pour les parties 1 à 4).

Les fichiers fournis avec le canevas Java sont: Makefile, build.xml, RISC.java, Code.java, Generator-partial.java, GeneratorTest.java.

Le fichier compressé part5-java.zip contient tous les fichiers Java dont vous avez besoin pour la partie 5 (part5-java.zip contient également les fichiers fournis pour les parties 1 à 4).

Pour tester les programmes produits par votre compilateur, nous mettons à votre disposition un interpréteur RISC 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 Zwei é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-20051207.tgz ou risc-20051207.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.