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

Le compilateur fourni est fonctionnel mais uniquement pour une syntaxe très minimaliste (Hello 42 dans le fichiel ./src/test/resources/Milestones/Test101.txt, qui correspond au Jalon 1). Dès que l'on va étendre la syntaxe, le comportement du compilateur est indéfini.

Les différentes phases du compilateur sont exécutées en séquence dans la méthode main.Compiler::main : les analyses lexicale et syntaxique ensemble, puis l'analyse sémantique, ensuite la génération de la représentation intermédiaire, et enfin la génération de code avec l'exécution du code MIPS généré par l'outils MARS.

À la fin de chaque phase, l'instruction en commentaire Compiler.stopAfterXxxx() permet d'arrêter la séquence. Par exemple, l'instruction Compiler.stopAfterSyntax() est utilisée lorsque l'on souhaite compléter et tester la spécification JFlex+CUP sans que les autres phases n'aient été écrites. (Ces mêmes instructions sont utilisées dans certains tests JUnit.)

Comme pour les différentes phases du compilateur, le travail est à réaliser de manière incrémentale en ajoutant au fur et à mesure les différentes règles de la grammaire (Jalons 1,..., 9) et en validant avec les tests JUnit afférents ou avec un fichier input.txt à compléter ou adapter.

L'ensemble du compilateur est réalisé dans un premier temps en ignorant les tableaux d'entiers (Jalon 9). L'étape finale du projet ajoute les tableaux d'entiers dans l'ensemble des phases du compilateur.

Réaliser l'analyse lexicale et syntaxique de MiniJAVA pour les Jalons&nbps;2 à 7.

• Lire la documentation du projet Mémento MiniJAVA, sections 2, 3, 4 et 10.
• Écrire les spécifications JFlex et CUP pour réaliser l'analyse du langage MiniJAVA :
  • L'identificateur this peut être ignoré en temps que mot-clé dans l'analyse lexicale. Il est traité comme les autres noms de variable dans l'analyse syntaxique. Le rôle particulier de this sera pris en compte au niveau de l'analyse sémantique qui forgera la déclaration implicite de cette variable.
  • La gestion des localisations dans le fichier source (méthode AddPosition) est optionnelle, mais conseillée car elle aide lors du déverminage.
• Construire l'Arbre de Syntaxe Abstraite en suivant les définitions du paquetage phase.b_syntax.ast.*.
• Tester et valider l'analyse syntaxique en vérifiant l'impression des AST, et le résultat du visiteur phase.b_syntax.PrettyPrint. Adapter si besoin la classe main.util.Debug pour modifier les traces imprimées par le compilateur.
• Utiliser les classes de tests dans ./src/test/java/test pour les tests. En particulier :
  • pour tester les analyses avec des entrées correctes, utiliser la classe SuccessfulMilestonesTest avec :
    • soit les méthodes jalonString[1-7], qui utilisent en entrée des chaînes de caractères définies dans la classe de test,
    • soit les méthodes jalonFile[1-7], qui utilisent en entrée les fichiers dans le répertoire src/test/resources/Milestones/.
    Nous proposons les deux formes (chaîne de caractères et fichiers) pour, lors du déverminage, laisser choisir entre « jouer » avec des chaînes de caractères ou avec les contenus des fichiers ;
  • pour tester les analyses avec des entrées incorrectes, et qui doivent être détectées comme étant incorrectes, utiliser la classe ErrorsLexicalSyntacticTest.
  • pour tester des exemples plus conséquents, utiliser la classe RunningTest avec les fichiers dans le répertoire ./src/test/resources/Running/ : les fichiers Test20[1-7].txt, AckermannFunction.txt, ImplemSimplisticBigNum.txt, etc.

Voici par la construction par étape de la spécification JFlex+CUP les jalons :

• Jalon 2 : grammaire d'opérateur et priorités, cf. les exercices JFlex+CUP sur « Calculatrice »,
• Jalon 3 : listes simples, cf. les exercices JFlex+CUP sur les « Grammaires de listes »,
• Jalon 4 : listes avec séparateurs, cf. les exercices JFlex+CUP sur les « Grammaires de Listes »,
• Jalon 5 : doubles listes, cf. les classes KlassBody et MethBody dans la spécification CUP fournie,
• Jalon 6 : autres expressions,
• Jalon 7 : autres instructions.

Cette étape suppose d'avoir une analyse lexicale et syntaxique opérationnelle pour le langage MiniJAVA. Compléter l'étape précédente en utilisant éventuellement le corrigé.

Écrire un visiteur phase.c_semantic.DisplayVarDeclarations qui hérite de syntax.ast.AstVisitorDefault et qui imprime l'ensemble des identificateurs des variables déclarées.
Le visiteur phase.b_syntax.PrettyPrint peut donner une idée de squelette, mais le travail demandé ici est beaucoup plus court (20-30 lignes). DisplayVarDeclarations commence comme suit :

Inclure l'appel au visiteur dans phase.c_semantic.Semantic pour tester : pour ce premier visiteur, la construction d'une instance de la classe suffit (l'appel à la méthode accept sur l'objet axiome démarre la visite et la méthode Debug::log affiche le log accumulé). Voici le début complété de la séquence de visiteurs appelés dans la méthode Semantic::run :

Adapter le visiteur pour préciser, pour chaque variable, s'il s'agit d'un attribut de classe, d'une variable locale, ou d'un paramètre formel de méthode.
Voici un exemple de résultat d'exécution sur le fichier exemple sur ./src/test/resources/Milestones/Test105.txt :

Compléter le visiteur pour afficher les noms de classes et de méthodes déclarées.

Au vu de l'énonce et de l'affichage, les méthodes visit sont à redéfinir pour les nœuds de type Formal, Klass, Method, et Variable.

Écrire un autre petit visiteur phase.c_semantic.DisplayScopes qui reconstruit uniquement la structure des accolades {} du fichier d'origine.

Voici un exemple de résultat d'exécution sur le fichier exemple sur ./src/test/resources/Milestones/Test105.txt :

Fusionner les 2 visiteurs précédents dans un seul visiteur DisplayVarDeclarationsInScopes. On imprime ainsi l'ensemble des identificateurs à l'intérieur de leur portée respective.

Voici un exemple de résultat d'exécution sur le fichier exemple sur ./src/test/resources/Milestones/Test105.txt : = Affichage des identificateurs dans leur portée : Test2{a(field), b(field), Start{i(formal), j(formal), k(local), }un{}}Test3{zero{}}

La construction de la Table des symboles pour le compilateur MiniJAVA est réalisée par la classe phase.c_semantic.BuildSymTab. Le squelette fourni est un visiteur qui ne fait rien, mais contient les helpers utiles pour réaliser le travail. Analyser les helpers avant de commencer le travail ; souvent ils répondent à la question « où est-ce que cela se trouve ? »

On notera que :

• la table des symboles (rootScope) est un attribut de l'enregistrement phase.c_semantic.SemanticTree. C'est un objet de type Scope ayant pour nom « Root » et n'ayant pas de portée parente ;
• à la lecture de l'enregistrement SemanticTree, on voit que la table des symboles est un des attributs sémantiques de l'analyse sémantique du projet MiniJAVA. Sans surprise, on trouvera que l'attribut qui sera étudié à l'étape suivant celle-ci est le typage des nœuds de l'AST, principalement pour le contrôle du type, le langage JAVA étant un langage dit fortement typé ;
• la classe Object et sa méthode equals sont déjà intégrées dans la table des symboles avec le code fourni : la méthode addObjectKlass est appelée au début de la méthode SemanticTree::run et crée un objet de type InfoMethod pour la méthode Object::equals avant de l'ajouter dans la portée de la classe Object en appelant la méthode newMethodScope ;
• tout programme MiniJAVA commence conventionnellement par la classe Main : cf. la section 2.1 du memento MiniJAVA. Aussi, la classe Main de MiniJAVA est intégrée dans le code du squelette à titre d'exemple de méthode BuildSymTab::visit. Les symboles de cette classe (main(), args, className) n'ont en réalité pas d'utilisation dans le langage MiniJAVA.

Écrire la classe BuildSymTab qui construit la table des symboles pour le langage MiniJAVA :

• Construire l'arbre des portées qui structure la table des symboles : (cf. Mémento MiniJAVA, sources, et helpers).
• Calculer l'attribut sémantique hérité currentScope qui associe à chaque nœud de l'AST la portée où se trouve le nœud. Cet attribut réalise le lien vers les identificateurs visibles depuis ce nœud.
• Stocker l'attribut sémantique currentScope (décoration de l'AST) dans la structure semantic.semanticTree (attribut scopeAttr) pour pouvoir le réutiliser dans la suite de l'analyse sémantique et dans les phases suivantes du compilateur (cf. méthode helper) setScope.
• Stocker dans l'arbre des portées l'ensemble des informations de déclaration d'identificateurs (classe, méthode, variable/attribut) en utilisant les méthodes phase.c_semantic.symtab.Info*.
• Gérer la « variable » this dont la déclaration est implicite dans l'AST :
  • Pour chaque méthode, ajouter dans la table des symboles une déclaration explicite de this comme premier paramètre de la méthode.
  • Le type de la variable this est le nom de la classe courante !
  • Il faut dont calculer l'attribut sémantique hérité currentKlass qui associe à chaque nœud de l'AST, la classe englobante du nœud. Il n'est pas utile de stoker cet attribut dans l'arbre sémantique car l'attribut BuildSymTab::currentKlass correctement mis à jour lors de la visite suffit.
• Réaliser enfin la fonction sémantique allready defined qui détecte les erreurs de redéfinition d'identificateur au sein d'une même portée. Ce n'est fonctionnellement pas l'endroit pour faire cela, mais c'est très économique de le faire ici (et c'est déjà presqu'écrit avec le code de la méthode BuildSymTab::checkRedef !).
• Valider le travail en vérifiant l'impression de la table des symboles (passe 1 de la phase 3, qui est l'analyse sémantique).

Comme préparé dans les premiers visiteurs avec la fusion dans la classe DisplayVarDeclarationsInScopes, la table des symboles est d'abord remplies pour la déclaration des portées et des variables. Donc, les visites des nœuds de l'AST de type Klass, Method, Variable, et StmtBlock doivent être redéfinies dans le visiteur BuildSymTab. Ensuite, on n'oubliera pas de gérer currentScope et currentKlass comme indiqué ci-dessus.

Voici un exemple de résultat d'exécution sur le fichier exemple sur ./src/test/resources/Milestones/Test105.txt :

Avant d'utiliser l'héritage des classes JAVA, il est urgent de valider l'absence de boucles dans l'héritage. Cette fonction sémantique est réalisée par la classe semantic.CheckInheritance (algorithmique très basique et peu optimisé !).

Dans la même classe, on va de plus reconstruire la racine de l'arbre des portées pour ajouter l'arbre d'héritage des classes (si c'est un arbre !) comme arbre d'héritage des visibilités des identificateurs. L'héritage orienté objet deviendra alors transparent pour la recherche dans la table des symboles.

Parcourir rapidement le code et tester le fonctionnement en analysant l'impression de la table des symboles (passe 2).

Écrire la fonction sémantique Identifier allready defined.

Comparer le comportement du compilateur MiniJAVA avec celui de javac dans le cas d'une variable locale de méthode qui redéfinit un argument de la méthode.

Écrire un nouveau visiteur qui vérifie que tous les identificateurs utilisés dans l'AST, sont bien liés à une déclaration dans la table des symboles.

Ignorer pour le moment les identificateurs de méthode, qui ne peuvent être traités qu'après le contrôle de type : rechercher la méthode pour obj.method() nécessite de connaître le type de obj. N.B. : si l'on prend en compte la liaison dynamique de JAVA, le test n'est plus après le contrôle de type mais éventuellement à l'exécution !

On peut aussi ignorer l'identificateur de classe de la classe parente dont le contrôle est déjà réalisé de fait dans semantic.CheckInheritance.

Intégrer dans le visiteur Undefined précédent la fonction sémantique qui signale l'ensemble des variables déclarées mais non utilisées. On notera que semanticTree.rootScope.getAllVariables() donne la collection de toutes les variables du programme. Il suffit donc de supprimer au fur et à mesure les variables utilisées pour avoir en fin de visite les variables Unused.

cf. Mémento MiniJAVA et code fourni...

Le schéma de liaison entre les identificateurs et leurs déclarations réalisé avec la table des symboles consiste à rechercher la déclaration en partant de la portée courante et en remontant l'arbre des portées (cf. Scope::lookup*()).

Ce schéma fonctionne pour les variables ou pour les méthodes de classe (static) mais ne fonctionne pas directement pour les méthodes d'instance. Pourquoi ?
Si l'on a x.get(); y.get(); dans une même portée, où chercher la déclaration de get() ?
En fait la question est incorrecte. Il y a potentiellement plusieurs déclarations différentes.
solution ?...

Écrire un visiteur qui calcule l'attribut Type de chaque expression dans l'AST MiniJAVA. Le Type est un String avec des valeurs prédéfinies (main.EnumType) pour les types primitifs, ou un nom de classe pour les types Objets. La classe phase.c_semantic.TypeChecking est fournie comme squelette pour démarrer la construction du contrôle de type.

Le Type est un attribut synthétisé qui est stocké dans la structure SemanticTree pour la suite de la compilation. L'attribut Type est nécessaire pour le contrôle de type à suivre, et sera aussi indispensable pour l'allocation mémoire dans la phase de génération de code assembleur.

Spoiler : en réalité, on ignorera l'attribut en allouant un mot de quatre octets pour toutes les variables quelque soit le type !

Intégrer dans le visiteur précédent le contrôle de type, c'est-à-dire la vérification de l'ensemble des contraintes de typage du langage MiniJAVA.

Dans MiniJAVA, il n'y a pas de transtypages pour les types primitifs. Pour les types Object, on a le transtypage naturel lié à l'héritage des classes. Un objet possède le type de tous ces ancêtres. Ce mécanisme est implanté dans le squelette fourni et l'on a aucun besoin de mémoriser ces cas de transtypage pour les phases suivantes de la compilation.

On notera l'absence de surcharge des opérateurs, c'est-à-dire la possibilité qu'un opérateur change de sémantique en fonction du type des opérandes. Pour les méthodes, on ignore la liaison dynamique et les possibilités de surcharge, mais on permet la redéfinition (overriding).

Étudier les nombreuses méthodes helpers :

• erreur : permet d'afficher un message d'erreur en gardant mémoire qu'il y a eu une erreur, mais sans arrêter l'analyse. L'intérêt de ne pas s'arrêter à la première erreur est d'essayer d'en détecter plusieurs en une seule exécution du compilateur MiniJAVA ;
• getType : par exemple, lors de la visite d'un nœud, permet d'obtenir le type d'un nœud enfant (il faut dans ce cas avoir visiter cet enfant avant l'appel) ;
• setType : par exemple, sur un nœud opérande litéral d'une expression, permet de fixer le type. Conseil : utiliser le type VOID lors d'une erreur, par exemple avec un opérateur binaire inconnu dans une expression ; cela permet de continuer l'analyse du typage ;
• getScope et lookupKlass : par exemple, getScope cherche la méthode dans la portée d'une classe (trouvée avec lookupKlass) lors d'un appel de méthode (nœud de type ExprCall) ;
• compareType et checkType : on fournit ces deux méthodes, la seconde appelant la première pour accélérer le développement. Leur lecture est importante pour la compréhension de la gestion du typage pour l'héritage dans le compilateur MiniJAVA. La méthode checkType est la méthode par excellence qui est appelée lors de la visite d'un nœud ;
• checkTypeName : permet, par exemple, lors de la visite d'un nœud de déclaration d'un nouveau type (ExprNew) ou d'utilisation d'un type (Type), de vérifier que le type est connu ;
• lookupVarType : après la recherche de la variable dans la portée d'un nœud de l'AST, cherche le type de la variable. Cette méthode est utile lors de la visite des nœuds utilisant des identifiants, et plus précisément ExprIdent et StmtAssign. On notera que le type VOID est fourni lorsque la variable n'a pas été trouvée ;

Tester au fur et au mesure sur des exemples valides (p.ex. dans la classe de tests SuccessfulMilestonesTest) ou invalides (p.ex. dans la classe de tests ErrorsSemanticsTypingTest). En cas de doute, on peut aussi comparer avec le comportement du compilateur javac sur les mêmes exemples.

Terminer et valider les questions « Undefined » et « Unused » de l'étape 2 en intégrant la recherche des méthodes. On ne traite que la liaison statique et l'on ignorera le polymorphisme des méthodes.

• Les méthodes deviennent maintenant globales, c'est à dire que les noms de méthodes sont uniques dans le fichier source. 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 auront une implantation en mémoire identique avec un mot de 32 bits. On simplifie ainsi le calcul des tailles, des alignements...

• Calcul (et stockage) d'un Attribut synthétisé Var, qui pour chaque nœud "expression" contient la variable (IRvariable) utilisée par la forme intermédiaire pour stocker le résultat de l'expression. Cette variable est généralement une variable temporaire générée par le traducteur mais peut aussi être une constante ou une variable du programme d'origine.
• Calcul d'un attribut hérité currentMethod qui contient le nom de la méthode courante. Cette information est utilisée uniquement pour associer une portée locale aux variables temporaires IRtempo et permettre une meilleure allocation mémoire à venir.
• Traduction des nœuds de l'AST sous forme de séquences d'instructions IRquadruple. Les exemples de base pour les schémas de traduction sont illustrés dans les diapositives du cours.
• La traduction se fait à la volée au sens où le programme final est la concaténation des traductions de chaque nœud de l'AST en suivant l'ordre de la visite.

• La classe Reg fournit une énumération des registres MIPS pour les autres classes du package.
• La classe MipsWriter est une classe utilitaire pour l'impression dans un fichier des instructions MIPS. On peut l'adapter ou la compléter à la convenance de chacun.
• La classe LinkRuntime réalise l'édition des liens qui se limite à la concaténation du Runtime MIPS.
• La classe ToMips réalise la traduction de la forme intermédiaire vers MIPS. Pour le moment, elle ne gère que le programme hello 42 (Test101).
• La classe Allocator et le package codegen.access construit, à partir de la table des symboles (AST + IR), l'allocation mémoire des variables, des classes, des cadres d'appel... (cf. question suivante).

• Les différents types d'accès aux variables de la forme intermédiaire et la mise en œuvre à travers les classes codegen.access.Access*.
• La gestion des variables instances de classe : instanciation et accès aux champs.
• La mise en œuvre de la convention d'appel et le calcul des tailles des cadres d'appel (frame).
• L'allocation des variables locales, temporaires, ou globales.

• Analyser la structure de la classe ToMips : "Visiteur IR", Helpers, gestion des appels "spéciaux" (_system_*),...
  • L'accès aux variables IR (utilisation de codegen.access) est réalisé avec les méthodes regLoad(), regStore().
  • Les registres $v0 et $v1 sont librement accessibles pour les calculs temporaires dans le traitement de chaque instruction IR.
  • La gestion des paramètres est réalisée avec une liste java.util.ArrayList<IRvariable> params, qui est remplie par les instructions QParam, et utilisée puis réinitialisée dans les instructions QCall et QCallStatic.
  • ...
• Étapes :
  • Traduction de l'instruction QAssign(+,*).
    • Charger les 2 arguments de QAssign dans $v0 et $v1.
    • Effectuer l'opération avec résultat dans $v0.
    • Enregistrer $v0 dans le résultat de QAssign.
  • Traduction de l'instruction QNew.
    • Sauvegarder le registre $a0
    • Charger dans $a0 la taille de l'objet à instancier (cf. Allocator.classSize())
    • Appeler la fonction _new_object du Runtime MIPS
    • Enregistrer $v0 (résultat de _new_object) dans le résultat de QNew.
    • Restaurer $a0.
    • N.B. : On applique ici une convention d'appel simplifiée.
  • Construction la convention d'appel : QLabelMethod et QReturn pour l'appelé, QCall et QParam pour l'appelant.
    • QLabelMethod :
      • Écrire le label de fonction.
      • Positionner le cadre d'appel (framepointer) $fp = $sp.
      • Allouer le cadre d'appel = avancer la pile de la taille du cadre d'appel Allocator.frameSize().
      • Sauvegarder les registres adéquats ($ra,$s0,$s1,...).
      • Recopier les valeurs des arguments $a1, $a2, $a3 dans les 3 premiers variables locales du cadre d'appel.
    • QReturn :
      • Restaurer les registres adéquats.
      • Charger dans $v0 la valeur de retour.
      • Libérer le cadre d'appel. On notera que $fp contient la valeur de $sp à restaurer !
    • QCall :
      • Sauvegarder les registres adéquats ($fp,$a0,$a1,$a2,$a3,$t0,$t1,...).
      • Charger les (maximum 4) paramètres dans les registres $a0,$a1,$a2,$a3. Attention : pour éviter un éventuel problème d'écrasement, le registre $a0 doit être chargé (et écrasé) en dernier.
      • Effectuer l'appel : jal.
      • Restaurer les registres adéquats.
      • Enregistrer $v0 comme résultat du QCall.
  • et le reste : QAssign*, QCopy, QLabel, QJump*,...
    Aide-toy, le Ciel t’aidera. — (Jean de la Fontaine, Le Chartier embourbé, dans Fables, livre sixième, 1692-94)

• la cible jar de make ou de ant permet de créer une archive Compiler.jar exécutable du compilateur.
• L'exécution du compilateur se fait alors avec : java -jar Compiler.jar fichier1 fichier2....
• On teste ensuite chaque fichier assembleur produit avec mars fichier.mips.

• Modifier le traitement de l'instruction QCall pour accepter un nombre quelconque d'arguments dans le langage MiniJAVA.
• Attention de bien empiler (modif de $sp) les arguments supplémentaires avant de créer la frame ; et de dépiler à la fin.
• Vérifier que le compilateur marche encore pour une fonction récursive comme factorielle ou Ackermann.
• Vérifier aussi le fonctionnement sur ./Exemples/Running/Test205.java.

• Vérifier que le compilateur de départ est raisonnablement correct (cf. dernière question de l'étape 5).
• Faire un commit/backup/mail_a_1_ami pour ne pas casser le "compilateur qui marche".
• Prévoir éventuellement des tests simples de non-régression (un petit script qui compile N fichiers de tests, et imprime le résultat de l'exécution avec mars).