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

Le compilateur fourni est fonctionnel mais uniquement pour une syntaxe très minimaliste (« System.out.println(42); » dans le fichier ./src/test/resources/Jalons/Test101.txt, qui correspond au Jalon 1). Dès que l'on étend 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 compil.Compiler::execute : 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. Ce sont ces mêmes instructions utilisées dans les classes de test SuccessfulMilestonesTest qui permettent de tester phase par phase le compilateur.

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 (voire 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). La phase 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 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 AstNode::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 compil.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/Jalons/.
    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 la construction par jalon de la spécification JFlex+CUP :

• 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),
• Jalon 6 : autres expressions,
• Jalon 7 : autres instructions.

Nous conseillons de faire le travail autant que faire se peut sans regarder les éléments de réponse fournis (pour comprendre la grammaire BNF ainsi que la structure du code fourni), puis de compléter avec la solution (pour éviter d'y passer trop de temps). Et, pensez à tenir à jour le fichier binome_note_travail_sur_le_projet.md.

Dans le fichier binome_note_travail_sur_le_projet.md, copiez les énoncés et répondez aux questions ; pensez à fournir quelques explications. Dans un programme MiniJAVA :

1. est-il possible de définir la valeur d'un entier sous la forme octale ?
2. dans une méthode, peut-on écrire « int a; a = 0; int b; b = n; » ? ou doit-on plutôt écrire « int a; int b; a = 0; b = n; » ?
3. est-il possible de mettre un attribut de classe (static) dans la classe qui contient la méthode main ?
4. est-il possible d'avoir une variable locale dans la méthode main ?

1. ❑ Répondre aux questions posées dans le fichier binome_note_travail_sur_le_projet.md
2. ❑ Réaliser les spécifications JFlex+CUP pour les Jalons 2–7, y compris l'appel au visiteur PrettyPrint (pour voir dans la console le résultat de l'analyse lexicale et de l'analyse syntaxique) ainsi que les tests (intégrés à la construction du compilateur et qui « passent »).
3. ❑ Réaliser l'analyse lexicale ainsi que l'analyse syntaxique du Projet MiniJAVA, c'est-à-dire pour avoir aussi des tableaux.
4. ❑ Indiquer le statut des tâches pour cette phase dans le fichier binome_note_travail_sur_le_projet.md

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 la solution.

É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. DisplayVarDeclarations commence comme suit :

L'appel au visiteur est inclut dans phase.c_semantic.Semantic::execute : 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é).

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 ./src/test/resources/Jalons/Test105.txt :

Au vu de l'énonce et de l'affichage, les méthodes visit sont à redéfinir pour les nœuds de type Formal, Klass, AstMethod, et Variable, et elles utilisent la méthode IdentWriter::print pour afficher les identificateurs (xxxId.name() des nœuds).

É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/Jalons/Test105.txt :

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

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/Jalons/Test105.txt :

Outre la section 7 du Mémento MiniJAVA, il convient de lire attentivement le contenu des classes du paquetage phase.c_semantic.symtab.

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, car 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 BuildSymTab::execute 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. Par ailleurs, afin de les retrouver, les paramètres formels d'une méthode, ici equals, sont rassemblés dans une nouvelle portée dont le nom est construit comme la concaténation du nom de la méthode et de la chaîne de caractères _args, ici equals_args. Ainsi, l'affichage à la console de la table des symboles contiendra les lignes suivantes :
  Scope Root Scope Object boolean equals(Object this, Object o) Scope equals_args Object this Object o Scope equals

É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. la section 7 Mémento MiniJAVA, le code source, et plus particulièrement les méthodes 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).

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, après la redéfinition de la visite par défaut (montrée ci-dessous dans defaultVisit), les visites des nœuds de l'AST de type KlassMain (aussi montrée ci-dessous), Klass, AstMethod, 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. Dans les visites : Klass (appel de newKlassScope), AstMethod (appel de newMethodScope), StmtBlock (appel de new Scope)

En guise d'exemple, voici la redéfinition de la visite par défaut ainsi que de la visite pour le nœud KlassMain :

Voici un exemple de résultat d'exécution sur le fichier exemple ./src/test/resources/Jalons/Test103.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 reconstruit aussi la racine de l'arbre des portées pour ajouter l'arbre d'héritage des classes 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).

Voici un exemple de résultat d'exécution sur le fichier exemple ./src/test/resources/Jalons/Test103.txt. Comme montré dans le tableau qui suit, pour que la classe enfant Test3 inclut les identificateurs de la classe parente Test2, la portée de la classe enfant est « déplacée » dans la portée de la classe parente : ce déplacement est opéré par la méthode Scope::addInheritance.

Les méthodes de test test403SemanticError1 et test403SemanticError2 de test de la classe de tests JUnit test.ErrorsSemanticsInheritanceTest montrent deux exécutions avec un cycle dans l'arbre d'héritage :

Écrire la fonction sémantique Identifier allready defined.

Écrire un nouveau visiteur phase.c_semantic.VarUndefUnused 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. Faire attention au cas particulier de la variable this qui a dû être systématiquement ajoutée comme premier paramètre dans les méthodes.

Les méthodes visit à redéfinir sont celles pour les types ExprCall, ExprNew, ExprIdent, StmtAssign, StmtArrayAssign (pour les tableaux), et AstMethod (attendre après le contrôle de type).

Cf. la section 5 du Mémento MiniJAVA ainsi que le code fourni...

Dans le fichier binome_note_travail_sur_le_projet.md, copiez les énoncés et répondez aux questions ; pensez à fournir quelques explications :

1. lorsque l'on écrit un visiteur héritant du visiteur par défaut AstVisitorDefault, à quoi sert l'appel à la méthode defaultVisit dans les méthodes redéfinies ?
2. lorsque l'on ajoute un nouveau type de nœud dans l'AST, faut-il modifier le visiteur par défaut AstVisitorDefault ? si oui, pourquoi ?
3. que fait notre compilateur en cas d'erreur dans la gestion de l'héritage (détection d'un cycle) ?
4. notre compilateur considère-t-il comme une erreur de redéfinition l'écrasement d'un paramètre d'appel par une variable locale ? Qu'en est-il du compilateur javac ?
5. notre compilateur accepte-t-il la séquence qui suit ? Qu'en est-il du compilateur javac ?
   { int a; a = 0; b = 0; int b; }

1. ❑ Répondre aux questions posées dans le fichier binome_note_travail_sur_le_projet.md
2. ❑ Réaliser la construction de la table des symboles (visiteur BuildSymTab, mais aussi les visiteurs DisplayVarDeclarations, DisplayScopes, et DisplayVarDeclarationsInScopes) ainsi que les tests (intégrés à la construction du compilateur et qui « passent »). Attention : vérifier aussi les affichages ! Par exemple avec les exemples donnés dans l'énoncé.
3. ❑ Réaliser la construction de la table des symboles du Projet MiniJAVA, c'est-à-dire pour avoir aussi des tableaux.
4. ❑ Indiquer le statut des tâches pour cette phase dans le fichier binome_note_travail_sur_le_projet.md

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. méthode phase.c_semantic.symtab.Scope::lookup*).

Ce schéma fonctionne pour les méthodes de classe (static) mais ne fonctionne pas pour les méthodes d'instance. En effet, pour une méthode d'instance, la recherche ne dépend pas de la portée courante mais dépend de la classe concrète du receveur (this). Pour x.get(), la déclaration de get() est à chercher à partir de la portée de la classe concrète de x.

Par conséquent, dans le cas d'une liaison statique (cas pour MiniJAVA), on considère le type formel (déclaré) de x qui est connu lors de l'analyse sémantique (contrôle de type). Dans le cas d'une liaison dynamique (JAVA), on considère le type actuel (réel) de x (celui de l'instanciation avec new). La liaison dynamique est donc potentiellement réalisée à l'exécution ou dans une phase d'analyse sémantique dynamique (flot d'exécution, etc.).

Écrire un visiteur qui calcule l'attribut Type de chaque expression dans l'AST MiniJAVA. Le Type est un objet de type MJType avec des valeurs prédéfinies (compil.util.MJPrimitiveTypes) pour les types primitifs ou un objet de type compil.util.MJTypeClass pour les types des classes. 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 serait aussi nécessaire pour l'allocation mémoire dans la phase de génération de code assembleur. Divulgation : en réalité, on ignorera l'attribut en allouant un mot de quatre octets pour toutes les variables quelque soit le type !

Comme indiquée au début de la phase, le travail à faire est conséquent. En effet, on doit redéfinir la visite pour la plupart des nœuds de l'AST, en l'occurrence :

• les nœuds Expr* pour positionner l'attribut de type ;
• la plupart des nœuds Stmt* et Expr* pour vérifier (méthode checkType) la compatibilité des types ;
• le nœud Type pour valider (avec la méthode checkTypeName) des noms de type dans les nœuds enfants des nœuds Variable, AstMethod et Formal ;
• le nœud AstMethod pour vérifier la compatibilité du type de retour (type de returnExpr).

En guise d'aide, cf. la description des nombreuses méthodes helpers ainsi que le pseudo-code de la visite des nœuds de type ExprCall dans la section qui suit.

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 transtypage pour les types primitifs. Pour les types Objet, 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 (méthode récursive compareType) et l'on a aucun besoin de mémoriser ces cas de transtypage pour les phases suivantes de la compilation (on ne fera pas de typage dynamique, par exemple pour la liaison tardive en cas de redéfinition de méthodes).

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 (overloading), mais on autorise la redéfinition (overriding) sans la réaliser dans les phases suivantes.

É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 pour accélérer le développement, la seconde appelant la première. 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 identificateurs, 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 à 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.

En guise d'aide, voici le pseudo-code de la visite des nœuds de type ExprCall :

Terminer et valider les questions « Undefined » et « Unused » de la phase précédente (phase 2) en intégrant la recherche des méthodes. On ne traite que la liaison statique et l'on ignore le polymorphisme des méthodes.

Dans le fichier binome_note_travail_sur_le_projet.md, copiez les énoncés et répondez aux questions ; pensez à fournir quelques explications :

1. Le compilateur MiniJAVA gère-t-il la surcharge ? Si ce n'est pas le cas, que fait le compilateur ? Pour cette question, cf. aussi la section 2.4 du Mémento MiniJAVA ;
2. Le compilateur MiniJAVA gère-t-il la redéfinition ? la liaison dynamique ? Si ce n'est pas le cas, que fait le compilateur ? Pour cette question, cf. aussi la section 2.4 du Mémento MiniJAVA ;
3. Dans le code du visiteur TypeChecking, comment voit-on que le type est un attribut synthétisé ?
4. Pourquoi la méthode compareType appelée par la méthode checkType est-elle récursive ?

Les éléments pour ajouter les tableaux au contrôle de type de l'analyse sémantique existante, c'est-à-dire pour passer du Jalon 7 au Jalon 9, sont disponibles à la fin de cette page dans la section intitulée « Projet MiniJAVA en autonomie : On ajoute les tableaux ».

1. ❑ Répondre aux questions posées dans le fichier binome_note_travail_sur_le_projet.md
2. ❑ Réaliser le contrôle de type (visiteur TypeChecking) ainsi que les tests (intégrés à la construction du compilateur et qui « passent »). Attention : vérifier aussi les affichages !
3. ❑ Réaliser le contrôle de type du Projet MiniJAVA, c'est-à-dire pour avoir aussi des tableaux.
4. ❑ Indiquer le statut des tâches pour cette phase dans le fichier binome_note_travail_sur_le_projet.md

On écrit un traducteur de l'AST vers la Représentation Intermédiaire en utilisant l'approche « code à 3 adresses » (cf. section 8 du Mémento MiniJAVA). La classe intermediate.Intermediate donne un canevas de départ avec des méthodes helpers.

Il s'agit d'écrire un visiteur de l'AST avec les calculs et traductions qui suivent :

• 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.

Réaliser le travail par étape en reprenant les jalons de la syntaxe MiniJAVA et les méthodes de tests de la classe de tests test.SuccessfulMilestonesTest (Cf. les exemples src/test/resources/Jalons/Test10*.java).

Premier rappel : la dernière section du mémento donne la liste des nœuds de l'AST par jalon.

Second rappel : les diapositives du cours donnent des éléments pour la traduction.

En guise d'aide, voici les exemples de programmes en représentation intermédiaire sans les optimisations :

Dans le fichier binome_note_travail_sur_le_projet.md, copiez les énoncés et répondez aux questions ; pensez à fournir quelques explications. Dans un programme MiniJAVA :

1. pour traduire les nœuds de l'AST de type ExprNew, que fait notre compilateur ? quel constructeur ?
2. quel est le rôle de l'attribut currentMethod ? comment est-il manipulé ? est-ce un attribut synthétisé ou hérité ?
3. que fait notre compilateur du problème du dangling else ? comment le traduit-on ?
4. quel usage fait-on des étiquettes/labels ? pour quels types de nœud de l'AST sont-elles utilisées et pourquoi ? (on tiendra compte des ajouts si on les a fait)

Les éléments pour passer du Jalon 7 au Jalon 9 sont disponibles à la fin de cette page dans la section intitulée « Projet MiniJAVA en autonomie : On ajoute les tableaux ».

Une optimisation dans la génération de la forme intermédiaire consiste à évaluer directement les opérations sur des constantes plutôt que de traduire de manière générique pour faire cette évaluation à l'exécution. Modifier le schéma de traduction pour le nœud ExprOpBin sous la forme

Idem pour ExprOpUn.

Cet ajout « se teste » plus particulièrement avec les fichiers Jalons/Test102.txt et Running/Test201.txt.

Pour optimiser l'exécution, mais aussi parce que c'est la sémantique dans le langage JAVA, modifier le schéma de traduction pour l'opérateur booléen « ET » (&&) de manière à ne pas évaluer les deux opérandes quand cela n'est pas nécessaire. De manière plus générale, la traduction sur les expressions booléennes se fera en utilisant plutôt une forme d'instruction « IF » qu'une forme d'opérateur logique.

N.B. : En JAVA, les expressions (n != null) && (n.istrue) ou (n == null) || (n.istrue) sont correctes (pas de NullPointerException) car le deuxième opérande n'est évalué qu'en fonction de la véracité du premier opérande.

Le schéma de traduction de && devient :

Faire le même travail sur l'opérateur unaire "NOT" et le traduire sans utiliser de QAssignUnary.

Cet ajout « se teste » plus particulièrement avec le fichiers Jalons/Test106.txt et Running/Test202.txt.

1. ❑ Répondre aux questions posées dans le fichier binome_note_travail_sur_le_projet.md
2. ❑ Réaliser la génération de la forme intermédiaire (visiteur Intermediate) ainsi que les tests (intégrés à la construction du compilateur et qui « passent »). Attention : vérifier aussi les affichages !
3. ❑ Réaliser la génération de la forme intermédiaire du Projet MiniJAVA, c'est-à-dire pour avoir aussi des tableaux.
4. ❑ Indiquer le statut des tâches pour cette phase dans le fichier binome_note_travail_sur_le_projet.md

Cf. la section 9 du Mémento MiniJAVA.

Dans toute cette phase, qui conclue les travaux sur le compilateur MiniJAVA, l'enjeu est la validation du fonctionnement du compilateur sur les exemples du dossier ./src/test/resources/Jalons/*. Ces exemples sont utilisés dans la classe de test JUnit test.SuccessfulMilestonesTest.

On rappelle cette demande importante : garder les fichiers Jalons/Test10?.txt tels quels, et créer d'autres fichiers pour d'autres tests intermédiaires.

En guise d'aide, voici les exemples de traduction MIPS sans les optimisatons :

Analyser rapidement le contenu et le fonctionnement des classes suivantes : Codegen (Codegen::execute est appelée par la méthode Compiler::execute) ; Allocator (avec la méthode Allocator::execute appelée par CodeGen::execute) ainsi que les classes du paquetage phase.e_codegen.access ; ToMips (qui est le visiteur, avec la méthode execute appelée par la méthode CodeGen::execute) ; MipsWriter (qui est utilisé par le visiteur ToMips pour écrire les instructions dans le fichier MIPS créé) ; et LinkRuntime (avec la méthode LinkRuntime::execute qui est appelée par la méthode CodeGen::execute).

Pour terminer notre compilateur, seule la classe ToMips nécessite d'être modifiée.

Écrire par étape (jalon, milestone) la classe ToMips pour réaliser la compilation du langage MiniJAVA. Enfin, le bout du tunnel !!!

Premier rappel : la dernière section du mémento donne la liste des nœuds de l'AST par jalon.

Second rappel : les diapositives du cours donnent des éléments pour la traduction.

Dans le fichier binome_note_travail_sur_le_projet.md, copiez les énoncés et répondez aux questions ; pensez à fournir quelques explications. Dans un programme MiniJAVA :

1. Quels sont les instructions de la représentation intermédiaire (quadruplets) qui sont impliquées dans la réalisation de la convention d'appel ? Quelles sont les méthodes utilitaires de la classe ToMips que l'on peut enchaîner pour la mise en œuvre de la convention d'appel (de l'appel au retour, chez l'appelante et chez l'appelée) ? Indiquer la séquence.
2. Dans une méthode d'instance, comment le compilateur MiniJAVA accède-t-il à un attribut de l'instance ? Via quel registre ?
3. Quelles sont les variables globales dans un programme MiniJAVA ? Où sont-elles en mémoire ?

Les éléments pour passer du Jalon 7 au Jalon 9 sont disponibles à la fin de cette page dans la section intitulée « Projet MiniJAVA en autonomie : On ajoute les tableaux ».

Supprimer la contrainte sur le nombre d'arguments des méthodes. La classe phase.e_codegen.Allocator implémente déjà la convention d'appel et définit l'accès aux arguments 4 à N (0($fp), 4($fp), etc.), c'est-à-dire dans la pile avant la frame de l'appelée. Il faut uniquement modifier les séquences d'appel et de sortie au niveau de l'appelante.

Pour ce faire, modifier le traitement de l'instruction QCall pour accepter un nombre quelconque d'arguments dans le langage MiniJAVA.

Vérifier que le compilateur fonctionne encore. Dans la classe de tests JUnit test_other.RunningTest :

• src/test/resources/Running/Test204.txt : appel de fonction avec moins de 4 arguments ;
• src/test/resources/Running/Test205.txt : appel de fonction avec plus de 4 arguments ;
• src/test/resources/Running/AckermannFunction.txt : appel de fonction récursive « gourmande ».

1. ❑ Répondre aux questions posées dans le fichier binome_note_travail_sur_le_projet.md
2. ❑ Réaliser la génération de l'assembleur MIPS (visiteur IRvisitorDefault) ainsi que les tests (intégrés à la construction du compilateur et qui « passent »). Attention : vérifier aussi les affichages !
3. ❑ Réaliser la génération de l'assembleur MIPS du Projet MiniJAVA, c'est-à-dire pour avoir aussi des tableaux.
4. ❑ Indiquer le statut des tâches pour cette phase dans le fichier binome_note_travail_sur_le_projet.md

Quelques suggestions avant de démarrer :

• Vérifier, selon l'état d'avancement dans le projet, que, dans la phase courante, le compilateur est raisonnablement fonctionnel : par exemple, dans la phase d'analyse lexicale et d'analyse syntaxique, « des tests passent »
• Faire un commit/backup/mail_a_1_ami pour ne pas casser le « compilateur qui marche ».
• Remarquez que les tests JUnit existants, que vous avez écrits ou que vous avez enabled (en retirant l'annotation @Disabled), agissent comme des tests de non-régression. Ils font partie du processus de construction du compilateur avec Maven. Notez cependant que les tests de la phase de génération du code MIPS avec ensuite l'exécution du programme généré avec Mars « se contentent » de tester la levée d'une exception ; autrement dit, les résultats des exécutions Mars ne sont pas testés.

A priori, deux token et cinq règles de grammaire sont à ajouter dans les spécifications JFlex et CUP.

Par ailleurs, quatre nouveaux nœuds sont à utiliser dans l'AST : phase.b_syntax.ast.*Array*.

Ne pas oublier non plus de fixer une priorité pour les tokens []. (Ajout : tester aussi le comportement sans cette priorité)

En guise d'exemple, voici dans le fichier suivant un exemple d'affichage à la console pour le programme Test109.txt :

La table des symboles est inchangée à part l'existence d'un type main.EnumType.INT_ARRAY.

Le contrôle de type doit traiter les 4 nouveaux types de nœud de l'AST :

• ExprArrayLength : contrôle du type de l'expression dans expr.length ;
• ExprArrayLookup : contrôle du type des deux expressions dans exprArray[exprIndice] ;
• ExprArrayNew : contrôle du type INT pour la taille du tableau ;
• StmtArrayAssign : contrôle du type INT pour l'indice de la case du tableau accédée et contrôle du type « tableau de XXX » pour la variable correspondant au tableau.

Pour rappel, les diapositives du cours donnent des éléments pour le contrôle des types.

En guise d'exemple, voici dans le fichier suivant un exemple d'affichage à la console pour le programme Test109.txt (en incluant les ajouts) :

Les quatre nouveaux types de nœuds de l'AST correspondent à quatre nouvelles instructions de la Représentation Intermédiaire : QLength, QAssignArrayFrom, QNewArray, et QAssignArrayTo. La traduction des trois premiers type de nœuds inclue la création d'une nouvelle variable temporaire et celle du dernier recherche la variable correspondant au tableau accédé.

Pour rappel, les diapositives du cours donnent des éléments pour la traduction.

En guise d'exemple, voici dans le fichier suivant un exemple d'affichage à la console pour le programme Test109.txt :

Traduire les 4 nouvelles instructions IR dans ToMips.

Pour rappel, les diapositives du cours donnent des éléments pour la traduction.

L'instanciation des tableaux utilisera la fonction _new_object du Runtime MIPS, avec le schéma suivant à implémenter :

Une variable tableau proprement dite est gérée de façon transparente par Allocator pour qui toutes les variables sont des valeurs sur 4 octets, aussi bien pour les types primitifs (entier, booléen), que pour les types références (instance de classe ou tableau).

En guise d'exemple, voici dans le fichier suivant un exemple d'affichage à la console pour le programme Test109.txt :

Et voici le programme MIPS généré : exemple_execution_test109_phase_e_code_assembleur.mips.

Valider le bon fonctionnement du compilateur.

Utiliser les Exemples */Test*9.txt et le très bel exemple TestBigNum qui calcul 42 comme somme de 3 cubes ! Enfin la vraie révélation du secret de l'univers !!! (ou du metavers !)

Ajouter le contrôle des bornes à l'exécution sur les tableaux.

Ajouter aussi le contrôle à l'exécution sur la taille positive dans l'instanciation des tableaux.

Voici quelques éléments :

• Utiliser l'instruction MIPS : sltu $t0, $t1, $t2 (?!?). Cf. méthode phase.e_codegen.MipsWriter::inRange.
• Gérer une sortie en erreur en utilisant la fonction _system_exit(errorCode) du Runtime MIPS (errorCode=111 ou 42 ou...).

Ajouter au langage MiniJAVA, les tableaux de booléens :

• Ajouter un nom de type dans main.EnumType et une règle dans la spécification CUP.
• Adapter éventuellement le nœud de l'AST ExpArrayNew pour le contrôle de type.
• Compléter le contrôle de type sur les tableaux (entier ou booléen).
• Et cela marche, ou pas !!!