Compilation : De l'algorithme à la porte logique (2023-2024)

• Gestion des packages Java avec en particulier un package syntax pour l'analyse syntaxique (classes Yylex, parse, sym, CupParse, Ast*...).
• Génération Make ou Ant avec un nom fixe pour les spécifications spec/minijava (si besoin modifier Makefile ou build.properties).
• Exécution sur un fichier de test par défaut input.txt (si besoin modifier Makefile ou build.properties, ou la classe main.Debug).

• main : la classe main() du compilateur main.Compiler et quelques classes "globales" utilitaires :
  • main.EnumType, main.EnumOper : énumérations des noms de type et des noms d'opérateur de Minijava.
  • main.Debug : ensembles d'options pour adapter les différents modes de trace à l'exécution. A modifier régulièrement à la convenance.
  • main.IndentWriter : classe utilitaire pour l'impression avec indentation.
  • main.CompilerException : pour le plaisir du lancée d'exceptions et une gestion des erreurs fatales dans les différentes phases du compilateur.
  • main.CompilerTest : Une classe main pour tester le compilateur avec une entrée Minijava dans une String à la place d'un fichier.
• syntax : phases d'analyse lexicale et syntaxique du compilateur. Pas de modifications nécessaires, sauf par effet de bord, en modifiant les spécifications CUP et JFlex dans de répertoire spec.
• semantic : phase d'analyse sémantique du compilateur. A écrire ou compléter.
• intermediate : phase génération du code intermédiaire du compilateur. A écrire ou compléter.
• codegen : phase allocation mémoire et génération de l'assembleur du compilateur. A écrire ou compléter.

De plus, les structures de données importantes partagées entre les différentes phases du compilateurs sont données et ne nécessitent pas de modifications :

• syntax.ast.* : Arbre de Syntaxe Abstraite pour Minijava avec patron de conception Visiteur.
  N.B. : la classe syntax.PrettyPrint fournit un visiteur opérationnel pour cet AST Minijava.
• semantic.symtab.* : Table des symboles avec portées et héritage Orienté Objet.
• intermediate.ir.* : Définition de la Représentation Intermédiaire du compilateur.
• codegen.access.* : Transfert MIPS entre les registres et les variables intermédiaires.

• ./Exemples/** : des exemples de sources Minijava valides ou pas pour les tests,
• ./Docs/* : une partie des documentations données dans ce mémento.

La première colonne donne une décomposition par étape (milestone) pour la définition de la syntaxe Minijava et le développement des autres phases du compilateur. Les fichiers de tests ./Exemples/Milestone/Test10* reprennent les mêmes étapes. La prise en compte des tableaux d'entiers (milestone 9) ne se fera qu'à la fin du projet après l'écriture d'un compilateur complet pour les autres étapes.

Les différences avec la grammaire de Andrew J. Appel, Modern Compiler Implementation in Java sont :

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

Dans un esprit de conformité avec Java, l'analyse lexicale de Minijava intègre :

• 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 ! ./Exemples/Running/TestPeano.java fonctionne en cyrillique !

(Bonus) On peut aussi ajouter l'utilisation du underscore et les formes octales, hexadécimales et binaires pour les littéraux Entiers de Java (cf. Exercices bonus : "Constantes entière en Java")

Pour la réalisation du compilateur, on suppose :

• 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. Une classe sans extends est traitée comme extends Object.
• La classe Object contient la méthode Object.equals(Object). Implémentation fournie dans semantic.BuildSymTab et runtime MIPS.
• L'héritage des méthodes, le polymorphisme et la sur-dé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.
• La liaison "dynamique" ou "tardive" n'est pas gérée par le compilateur.
• Le nombre d'arguments des méthodes pourra être borné à trois dans la génération finale.
• Les variables sont initialisées.

Des extensions possibles, mais non traitées dans le projet :

• Remplacer l'instruction unique du main() par une séquence d'instructions. Pas de difficultés mais pas très utile puisque l'on peut déjà mettre un bloc d'instruction dans le main() de Minijava !
• Ajouter l'instruction if sans else. Au niveau syntaxique, conflit du dangling else. Au niveau de la génération, se factorise avec if... else {}.
• Ajouter le moins unaire uniquement sur les littéraux entiers.
• Ajouter les méthodes void. Traiter void comme un nom de type ou pas ?
• Ajouter les tableaux pour tout type d'élément : booléens (facile), objets (facile), tableaux (difficultés pour la gestion de new xxx[][]).
• (super-méga-bonus) Utiliser une grammaire complète de Java (~500 lignes) : BNF Java 7.

Les phases d'analyse sémantique et de génération de code intermédiaire travaillent à partir de l'arbre de syntaxe et vont principalement rajouter dans l'arbre des informations utiles ou nécessaires pour la génération finale.
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..) et les contraintes pour leur implantation mémoire (pile, tas, registre,...).
• Les chemins d'exécution pour l'analyse sémantique dynamique (cf. coutures d'arbres).
• ...

La mise en œuvre consiste à ajouter des attributs dans les nœuds de l'AST.
Le calcul de ces attributs se décline sur 2 modes :

• Attributs hérités : la valeur est construite à partir de l'attribut du parent et des propriétés du nœud.
• Attributs synthétisés : la valeur est construite à partir des attributs des enfants et des propriétés du nœud.

Il peut exister des attributs "Mixtes" qui en général sont traités par une décomposition en sous-attributs hérités ou synthétisés (exemple : table des symboles).

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 "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 "récursif 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; recurse (AstNode node) { AttrType savedValue=currentValue; // Sauvegarde currentValue=calcul(currentValue,node); // Héritage de l'attribut for (AstNode fils : node) recurse(fils); // Récursions currentValue=savedValue; // Restauration }
• Solution "récursif sans retour" : Les Attributs Synthétisés sont gérés avec une variable globale "RETOUR" suivant le schéma :
  AttrType RETOUR; recurse (AstNode node) { recurse(fils1); // Récursion AttrType r1=RETOUR; // Sauvegarde temporaire recurse(fils2); // ... AttrType r2=RETOUR; ... RETOUR=calcul(r1,r2,...); // Synthèse de l'attribut return; }
• Solution "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 fera aussi de façon neutre pour l'AST, en utilisant une Map<AstNode,AttrType> pour chaque attribut sémantique. La classe générique semantic/SemanticAttribut<R> donne une interface rapide pour le stockage des attributs.

Le stockage des Attributs permet de simplifier le schéma "récursif sans retour" dans lequel, on n'a plus besoin de la variable "RETOUR" car on peut accéder à l'attribut d'un fils avec la Map de l'attribut. De même le schéma "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éalisera donc le calcul des attributs sémantiques suivant les deux schémas :

• Attribut Hérité
  SemanticAttribut attr = new SemanticAttribut<AttrType>(); AttrType currentValue=rootValue; recurse (AstNode node) { attr.set(node, currentValue); // Stockage currentValue=calcul(currentValue,node); // Héritage de l'attribut for (AstNode fils : mode) recurse(fils); // Récursions currentValue=attr.get(node); // Restauration }
• Attribut Synthétisé
  SemanticAttribut attr = new SemanticAttribut<AttrType>(); recurse (AstNode node) { for (AstNode fils : mode) recurse(fils); // Récursions AttrType tmp=calcul(attr.get(fils1),attrget(fils2)...) // Synthèse de l'attribut attr.set(node, tmp) ; // Stockage return; }

La table des symboles est un arbre défini par la classe Scope

• L'arbre est chaîné dans les 2 sens (filles 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.
• La visibilité peut être surchargée (et donc devenir invisible) dans une portée fille qui définit un identificateur de même nom.
• 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 parents jusqu'à la racine.
• De manière spécifique pour Java, la tables de symboles intègre le concept d'héritage de classe. C'est à dire qu'un identificateur sera aussi recherché en remontant si besoin l'arbre d'héritage des classes.

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

Dans Java ou Minijava, les portées sont produites par :

• 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 mère) et pour les variables locales (portée fille). 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 champs et les méthodes (et les classes internes en Java),
• la "Racine" portée globale contenant les classes.

En pratique, une table des symboles pour Minijava (pas de classes internes) aura 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 tables de type Map<String,Info> avec les identificateurs définis localement dans la portée.
• Les informations associées aux identificateurs sont définies par les classes InfoKlass, InfoMethod et InfoVar.
• L'interface traditionnelle d'une table des symboles est Info lookup(String); Info insert(String,Info), Collection<Info> getInfos() (cf. classe Table).
• La table des symboles Scope décline l'interface traditionnelle suivant la nature des identificateurs avec les méthodes lookupVariable, insertVariable, getVariables, lookupKlass,... lookupMethod,...
• 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.
• cf. sources, documentation Java et énoncé du TP pour plus de détails.

La convention d'appel est illustrée dans les diapositives du cours.

La classe 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 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 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 qui implémente la méthode boolean Object.equals(Object o).
• _system_out_println pour l'impression d'une valeur entière.
• _system_exit pour terminaison avec exit status et impression.