CSC4251_4252 — Compilation : du langage de haut niveau à l'assembleur

La structure de données pour la table des symboles est fournie dans le paquetage phase.c_semantic.symtab.*.

L'une des nouveautés du projet Maven pour le projet MiniJAVA est l'organisation en phases du code du compilateur. La voici :

• compil : le paquetage contenant la classe principale du compilateur main.Compiler et quelques classes « globales » utilitaires dans le sous-paquetage util :
  • compil.Compiler : la classe principale du compilateur avec la méthode main, et plus important, la méthode Compiler::execute qui enchaîne les différentes phases du compilateur ;
  • main.EnumOper et main.EnumType : énumérations des noms des opérateurs et des noms des types MiniJAVA ;
  • compil.util.Debug : ensembles d'options pour adapter les différents modes de trace à l'exécution. À modifier régulièrement à la convenance ;
  • compil.util.IndentWriter : classe utilitaire pour l'impression avec indentation. Cette classe est utilisée dans les impressions de l'AST ;
  • compil.util.CompilerException : pour le plaisir du lancée d'exceptions et une gestion des erreurs fatales dans les différentes phases du compilateur ;
  • compil.util.AstLocations : classe utilitaire représentant les positions dans le fichier source analysé.
• phase.b_syntax : les classes des phases d'analyse lexicale et syntaxique du compilateur. La classe Syntax est la classe appelant la classe CupParse dans la méthode Syntax::execute. Les classes dans le paquetage phase.b_syntax.ast sont celles qui peuvent être utilisées dans la spécification CUP. Pas de modifications nécessaires, sauf par effet de bord, en modifiant les spécifications JFlex et CUP dans le répertoire src/main/resources/specifications ;
• phase.c_semantic : les classes de la phase d'analyse sémantique du compilateur. La classe Semantic est la classe appelant les différents visiteurs dans la méthode Semantic::execute. Le sous-paquetage contient des classes pour construire la table des symboles : interface SymbolTable puis première mise en œuvre dans la classe SimpleSymbolTable, avant de construire la classe Scope qui regroupera les différentes tables des symboles pour les classes, les méthodes ainsi que les variables. Le paquetage phase.c_semantic contiendra à terme les visiteurs de l'analyse sémantique. À écrire ou compléter ;
• phase.d_intermediate : les classes de la phase de génération de la représentation intermédiaire sous la forme de « code à 3 adresses ». La transformation de l'AST en code intermédiaire sera effectuée par une visite : classe visiteur Intermediate et méthode Intermediate::execute. Le concept de « code à 3 adresses » est réalisé dans le record JAVA IntermediateRepresentation. Le paquetage phase.d_intermediate.ir contient les classes des différentes structures de données pour la représentation intermédiaire. Le résultat de cette phase est une instance de la classe IntermediateRepresentation, c'est-à-dire des listes de variables, de constantes, d'étiquettes, d'instructions, etc. À écrire ou compléter ;
• phase.codegen : les classes de la phase d'allocation mémoire et de génération de l'assembleur MIPS. La classe CodeGen enchaîne dans la méthode CodeGen::execute la visite du visiteur Allocator pour l'allocation mémoire, la visite du visiteur ToMips pour l'écriture des instructions MIPS, et enfin, l'édition de lien, qui dans le cadre du compilateur MiniJAVA correspond à l'ajout de la classe Object, et des méthodes Object::equals, System.out::println et System::exit. Le sous-paquetage phase.codegen.access contient des classes utilitaires pour les accès depuis et vers la mémoire. À écrire ou compléter.

N.B. : les structures de données importantes partagées entre les différentes phases du compilateurs sont données et ne nécessitent pas a priori de modifications :

• phase.b_syntax.ast.* : l'Arbre de Syntaxe Abstraite pour MiniJAVA avec patron de conception Visiteur.
  Par ailleurs, la classe syntax.PrettyPrint fournit un visiteur opérationnel pour l'AST MiniJAVA.
• phase.c_semantic.symtab.* : la table des symboles avec portées et héritage orienté objet.
• phase.d_intermediate.ir.* : la définition de la Représentation Intermédiaire du compilateur.
• phase.e_codegen.access.* : le transfert MIPS entre les registres et les variables intermédiaires.

• Dans le répertoire src/test/resources/Jalons/, des exemples de sources MiniJAVA valides ou pas pour les tests. Par exemple, un fichier de test qui doit « compiler », au sens MiniJAVA du terme, pour les différents jalons identifiés dans l'énoncé du projet : du jalon 101 au jalon 107, qui sont construits lors des séances, puis le jalon 109 (avec les tableaux), que vous construisez en mode projet. Autres exemples, les répertoires SyntaxError et SemanticError contiennent des exemples qui ne doivent pas « compiler », au sens MiniJAVA du terme. Derniers exemples, des exemples plus conséquents sont dans les répertoires Modern et Running.
• Dans le répertoire src/test/java/test, des classes de tests pour les différentes étapes de développement du compilateur MiniJAVA, en débutant avec ErrorsLexicalSyntacticTest et SuccessfulMilestonesTest. Au besoin, ajouter ou retirer l'annotation JUnit @Disabled sur une méthode de test annotée @Test pour respectivement exécuter ou ne pas exécuter le test avec la commande mvn clean install ou mvn test, ou dans l'IDE Eclipse avec le menu contextuel Run As > JUnit Test. Par ailleurs, comme pour l'arborescence src/test/resources, d'autres classes de tests sont disponibles.
• Dans le répertoire Docs : une partie des documentations données dans ce mémento.

La première colonne donne une décomposition par jalon (milestone) pour la définition de la syntaxe MiniJAVA et le développement des autres phases du compilateur. Les fichiers de tests src/test/resources/Jalons/Test10* reprennent les mêmes jalons. La classe de test test.SuccessfulMilestonesTest utilisent ces mêmes jalons.

• ClassBody ::= (Variable|Method)* au lieu de Variable* Method*. Plus conforme et plus général. Évite un conflit LR inutile (ou une récursivité droite).
• MethodBody ::= (Variable|Statement)* au lieu de Variable* Statement*.
• Gestion des variables de bloc : "{" (Variable|Statement)* "}" remplace "{" (Statement)* "}".
• Un token <BOOLEAN_LITERAL> à la place de 2 tokens true et false.
• "System" "." "out" "." "println" remplace "System.out.println". Juste pour le plaisir de la conformité JAVA.

• Les commentaires : // et /* */.
• La définition du token <INTEGER_LITERAL> par 0|[1-9][0-9]*. Compatibilité avec la notation octale !
• La définition JFlex du token IDENTIFIER par [:jletter:][:jletterdigit:]*
  Chouette ! c'est JAVA qui valide les identificateurs MiniJAVA.
  Chouette ! src/test/resources/Running/PeanoPlusUTF8Матрёшка.txt montre du cyrillique !

• la méthode System.out.println(...) n'imprime que des entiers ;
• l'attribut length ne s'applique que sur un tableau ;
• il existe une classe Object (rappel : une classe sans extends est traitée comme extends Object) ;
• la classe Object contient la méthode Object.equals(Object) : cf. implémentation fournie dans phase.c_semantic.BuildSymTab et phase.e_codegen.LinkRuntime ;
• l'héritage des méthodes, le polymorphisme et la redéfinition (overridding) ne seront pas gérés intégralement dans la compilation. En pratique, la génération finale MIPS pourra supposer les méthodes identifiées uniquement par leur nom. Plus précisément, la redéfinition est gérée dans la phase sémantique avec le contrôle de type, mais le code MIPS généré n'utilisera que le nom de la méthode pour former le label MIPS, n'autorisant donc pas plusieurs méthodes avec le même nom (surcharge), et n'autorisant donc pas plus la rédéfinition de méthode ;
• la liaison « dynamique » ou « tardive » n'est pas gérée par le compilateur ;
• le nombre de paramètres des méthodes pourra être borné à trois dans la génération finale ;
• (optionnel) les variables sont initialisées.

La définition des priorités et associativités dans JAVA (et donc pour MiniJAVA) :

Voici une description synthétique de l'AST (paquetage phase.b_syntax.ast.*) avec les constructeurs de chaque nœud. Dans le code, ce sont des record JAVA qui sont utilisés : cf. la section 2 du Mémento JAVA.

N.B. : les attributs des nœuds sont des arguments de la fabrique (méthode create), les autres arguments étant (1) le label, (2) les nœuds enfants dans l'AST ainsi que (3)  la position du nœud dans le texte analysé.

Le traitement d'erreurs n'est pas la priorité pour notre compilateur MiniJAVA. C'est une question importante pour la réalisation d'un compilateur, mais un peu gourmande en temps pour cet enseignement.

Il convient toutefois de pouvoir stopper l'exécution en cas d'erreurs. L'exception compil.util.CompilerException est définie pour cela.

Souvent une erreur ne nécessite pas un arrêt immédiat de l'exécution, mais interdit de passer à la phase suivante de la compilation. C'est par exemple pratique de pouvoir exécuter toutes les fonctions de l'analyse sémantique même si une des fonctions implique de ne pas continuer la génération. On gère ce cas par exemple dans la phase sémantique (méthode phase.c_semantic.Semantic::execute) en utilisant un booléen error, qui est activé en cas d'erreur et testé en fin de phase pour lever une exception : les visiteurs sont exécutés en séquence sous la forme « error = [visiteur].execute() || error » et une exception est levée à la fin de la séquence si « error ».

Les phases d'analyse sémantique et de génération de la forme intermédiaire travaillent à partir de l'arbre de syntaxe et consistent principalement à ajouter dans l'arbre des informations utiles ou nécessaires pour la génération finale du code MIPS : par exemple,

• la liaison des identificateurs avec leur déclarations ;
• le typage pour les expressions du langage ;
• les transtypages implicites dans les expressions ;
• la nature des variables (statique/dynamique, locale/globale, etc.) ainsi que les contraintes pour leur implantation mémoire (pile, tas, registre, etc.) ;
• les chemins d'exécution pour l'analyse sémantique dynamique (cf. coutures d'arbres) ;
• ...

Le calcul des attributs se fait naturellement en utilisant un parcours récursif en profondeur de l'AST. Différents choix sont toutefois possibles sur la façon de partager ou de propager les valeurs des attributs entre voisins :

• solution « parcours récursif pure » : les attributs hérités sont des paramètres d'appel de la fonction récursive, les attributs synthétisées sont des valeurs de retour de la fonction récursive.
• solution « parcours récursive sans paramètres » : les attributs hérités sont gérés avec une variable globale currentValue et une variable locale savedValue suivant le schéma :
  AttrType currentValue=rootValue; visit(AstNode node) { AttrType savedValue = currentValue; // Sauvegarde currentValue = calcul(currentValue,node); // Héritage de l'attribut for (AstNode enfants : node) visit(enfant); // Récursions currentValue = savedValue; // Restauration }
• solution « parours récursif sans retour » : les attributs synthétisés sont gérés avec une variable globale retour suivant le schéma :
  AttrType retour; visit(AstNode node) { visit(enfant1); // Récursion AttrType r1 = retour; // Sauvegarde temporaire visit(enfant2); // ... AttrType r2 = retour; ... retour = calcul(r1,r2,...); // Synthèse de l'attribut return; }
• solution « parcours avec stockage » : les schémas précédents peuvent être simplifiés si les valeurs des attributs sont stockées pour chaque nœud de récursion et accessibles entre nœuds voisins (cf. section suivante).

Pour éviter de « polluer » les classes de l'AST, le choix est de n'avoir qu'un unique prototype pour le parcours récursif (patron Visiteur) et donc une solution « sans paramètres et sans retour ». Le stockage des attributs se fait aussi de façon neutre pour l'AST, en utilisant un dictionnaire de type Map<AstNode,AttrType> pour chaque attribut sémantique. La classe générique phase.c_semantic.SemanticAttribut<R> donne une interface rapide pour le stockage des attributs.

Le stockage des Attributs permet de simplifier le schéma « parcours récursif sans retour » dans lequel on n'a plus besoin de la variable retour car on peut accéder à l'attribut d'un enfant avec le dictionnaire de l'attribut. De même, le schéma « parcours récursif sans paramètre » n'a plus besoin de la variable savedValue pour sauvegarder la valeur de l'attribut.

Pour le compilateur MiniJAVA, on réalise donc le calcul des attributs sémantiques suivant les deux schémas qui suivent :

• pour les attributs hérités :
  SemanticAttribute attr = new SemanticAttributey<AttrType>(); AttrType currentValue = rootValue; visit(AstNode node) { attr.set(node, currentValue); // Stockage currentValue = calcul(currentValue,node); // Héritage de l'attribut for (AstNode enfants : mode) visit(enfant); // Récursions currentValue = attr.get(node); // Restauration }
• pour les attributs synthétisés :
  SemanticAttribute attr = new SemanticAttribute<AttrType>(); visit(AstNode node) { for (AstNode enfant : mode) visit(enfant); // Récursions AttrType tmp = calcul(attr.get(enfant1),attrget(enfant2)...) // Synthèse de l'attribut attr.set(node, tmp) ; // Stockage return; }

La structure de données pour la table des symboles est fournie dans le paquetage phase.c_semantic.symtab.* : interface SymbolTable et classe SimpleSymbolTable.

La table des symboles est un arbre défini dans la classe phase.c_semantic.symtab.Scope :

• l'arbre est chaîné dans les 2 sens (enfants et parent) ;
• les nœuds de l'arbre correspondent aux différentes portées des déclarations des identificateurs. Un identificateur est visible dans sa portée, ainsi que dans les portées descendantes dans la table des symboles ;
• un identificateur dans une portée peut devenir invisible dans une portée enfant qui définit un identificateur de même nom. C'est le cas par exemple lorsqu'une classe enfant introduit un identificateur qui est déjà utilisé dans une classe parente, le second « cache » le premier ;
• de manière spécifique pour l'orienté objet, la tables de symboles intègre le concept d'héritage de classe, c'est-à-dire qu'un identificateur est aussi recherché en remontant si besoin l'arbre d'héritage des classes. Ainsi, la recherche d'un identificateur (méthodes lookUp*) à un endroit d'un programme consiste donc à rechercher l'identificateur dans la portée courante, et en cas d'échec à remonter dans les portées parentes jusqu'à la racine.

La liaison entre l'AST et l'arbre des portées est réalisée avec un attribut sémantique hérité (argument SemanticAttribute<Scope> attrScope du record SemanticTree) qui associe à chaque nœud de l'AST sa portée courante.

Dans Java ou MiniJAVA, les portées sont produites par (de la granularité la plus fine à la granularité la plus forte) :

• les « blocs d'instructions » avec des variables locales,
• les « méthodes » avec les variables locales et les paramètres. Pour notre compilateur, on choisit d'utiliser 2 portées différentes pour les paramètres (portée parente) et pour les variables locales (portée enfant). Ce n'est pas un choix très naturel, mais cela rend service dans la phase de génération de code.
• les « classes » avec les attributs et les méthodes (et les classes internes en JAVA),
• la « Racine », qui est la portée globale contenant les classes.

En pratique, comme nous excluons la possibilité d'avoir des classes internes, une table des symboles pour MiniJAVA possède des portées « classe » à la racine, qui contiennent des portées « méthode » au deuxième niveaux, et ensuite des portées « bloc » sur les niveaux suivants.

La table des symboles gère de façon séparée les identificateurs pour les noms de classes, les noms de méthodes, et les noms de variables ou d'attributs :

• chaque Scope de la table des symboles contient 3 dictionnaires de type Map<String,Info> pour les identificateurs définis localement dans la portée : l'attribut variables pour les objets InfoVar, ; l'attribut methods pour les objets InfoMethod, et l'attribut klasses pour les objets InfoKlass ;
• la table des symboles Scope décline l'interface traditionnelle suivant la nature des identificateurs avec les méthodes lookupVariable, insertVariable, getVariables, lookupKlass, etc., lookupMethod, etc. ;
• les méthodes lookup* intègrent la recherche récursive en remontant l'arbre des portées. Les autres méthodes agissent uniquement sur la portée courante.

Pour simplifier les phases suivantes de la compilation, on réduit un peu le spectre du compilateur en supposant que :

• les méthodes deviennent maintenant globales, c'est-à-dire que les noms de méthodes sont uniques dans le fichier source. Ainsi, dans la représentation intermédiaire comme dans le code final MIPS, une méthode correspond à un label avec le nom de la méthode. En cas de duplication, la détection se fera au niveau de l'assemblage avec MARS et un message duplicated label ;
• toutes les « variables » de MiniJAVA ou de la forme intermédiaire possède une mise en œuvre en mémoire identique avec un mot de 32 bits. On simplifie ainsi le calcul des tailles, des alignements, etc.

La Représentation Intermédiaire est fournie dans le paquetage phase.d_intermediate.ir.* et le record phase.d_intermediate.IntermediateRepresentation.

La Représentation Intermédiaire utilise un schéma « code à 3 adresses » : un programme est une séquence d'instructions IRquadruple, et une instruction peut potentiellement utiliser trois variables (ou « adresses », ou IRvariable) : arg1, arg2, result, et une opération op (un énumérateur de compil.EnumOper). Cette utilisation est spécifique pour chaque type d'instruction.

Les « adresses » IRVariable se déclinent en :

• IRConst pour des constantes ou valeurs immediate de l'assembleur MIPS,
• IRLabel pour des noms de labels/étiquettes qui deviendront des adresses de saut dans l'assembleur MIPS,
• IRTempVar pour des variables ajoutées dans la génération de code intermédiaire (variables temporaires pour exécuter les calculs, etc.),
• phase.c_semantic.symtab.InfoVar pour les variables issues du code source (la classe InfoVar implémente aussi l'interface IRVariable).

Voici une description synthétique de la forme Intermédiaire du compilateur MiniJAVA :

La génération du code MIPS est réalisée dans le paquetage phase.e_codegen (ainsi que le paquetage phase.e_codegen.access).

Les classes utilisées sont :

• MIPSRegister : une énumération pour gérer les noms de registre MIPS dans les différentes classes du paquetage ;
• MipsWriter : une classe utilitaire pour écrire le texte MIPS dans un fichier. Cette classe contient un ensemble de méthodes dites helpers pour produire et formater un jeu d'instructions MIPS suffisant pour notre compilateur ;
• Allocator : une classe utilitaire pour l'allocation mémoire de l'ensemble des variables de la forme intermédiaire. Cette classe contient la création pour chaque variable d'une instance de type access.Access qui produit le code MIPS pour les méthodes de chargement ou de sauvegarde entre une variable et un registre. Cette classe gère produit aussi le code MIPS pour la construction de la trame d'appel d'une méthode (paramètres et variables locales de la méthode) ;
  • N.B. 1 : la méthode Allocator::methodAlloc gère l'allocation pour les arguments, et ce quelque soit leur nombre, c'est-à-dire ≥ 4 ;
  • N.B. 2 : les méthodes tempoAlloc et methodAlloc traitent différemment la méthode de classe main (allocation statique en utilisant le registre $gp) des méthodes d'instances (allocation dans la pile en utilisant le registre $fp).
• ToMips : la classe du visiteur qui traduit la forme intermédiaire en programme MIPS ;
• LinkRuntime : la classe utilitaire qui ajoute un runtime MIPS (prédéfini). Le code assembleur du runtime est ajouté (à la fin du) au programme produit par la traduction ToMips ;
• Codegen : la classe appelée par le compilateur (classe compil.Compiler) pour la phase de génération de code du compilateur. La méthode Codegen::execute enchaîne : la création du fichier MIPS, l'allocation mémoire, la traduction de la forme intermédiaire en code MIPS et l'ajout du runtime MIPS.

La convention d'appel est illustrée dans les exercices des TP sur l'assembleur MIPS ainsi que dans les diapositives du cours.

La classe phase.e_codegen.Allocator implémente déjà l'allocation mémoire à l'intérieur du cadre d'appel (frame) et la position des arguments dans les registres et sur la pile.

Pour la réalisation du compilateur MiniJAVA, on peut se limiter à un ensemble réduit d'instructions MIPS (cf. helpers dans la classe phase.e_codegen.MipsWriter).

L'environnement d'exécution (interaction avec le système d'exploitation) du code produit par le compilateur est réalisé par la classe phase.e_codegen.LinkRuntime qui fait la concaténation d'un Runtime MIPS au code produit par la traduction du code intermédiaire. Ce code fournit les fonctions :

• _new_object pour l'allocation dynamique de mémoires (malloc). La mémoire allouée est initialisée à zéro ;
• equals pour la méthode boolean Object.equals(Object o) ;
• _system_out_println pour l'impression d'une valeur entière ;
• _system_exit pour la terminaison avec exit status et impression.