CSC4536– Compilation : De l'algorithme à la porte logique

Portail informatique
Les différentes étapes de la réalisation du compilateur Minijava sont dans la page Compilateur Minijava vers MIPS. Le squelette de départ est fourni dans l'archive Minijava.tar.gz. L'arborescence reprend le schéma d'un projet Jflex+Cup intégrable comme un projet Java dans un IDE.
  • 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.prop)
  • Exécution sur un fichier de test par défaut "input.txt" (si besoin modifier Makefile ou build.prop, ou la classe main.DEBUG)
  • Ajout des cibles "jar" et "runjar" dans la génération (make ou ant) pour créer un jar exécutable du compilateur et exécuter à partir du jar.
  • "main" : le main() du compilateur (à adapter si besoin) et quelques classes "globales" utilitaires :
    • "main.TYPE", "main.OPER" : énumérations pour les noms de type et noms d'opérateur de minijava
    • "main.DEBUG" : ensembles de flags pour adapter les différents modes de trace à l'exécution. A modifier régulièrement à la convenance.
    • "main.CompilException" : pour le plaisir du lancée d'exceptions et une gestion des erreurs fatales dans les différentes phases du compilateur.
    • "main.IndentWriter" : classe utilitaire pour l'impression avec indentation.
  • "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 "./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
  • "allocator" : (sous-)phase allocation mémoire pour la génération MIPS. Pas de modifications nécessaires
  • "codegen" : phase 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.*" : Arbres de Syntaxe Abstraite pour Minijava avec patron de conception Visiteur. NB: la classe "syntax.PrettyPrint" fournit un visiteur opérationnel sur l'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.
  • "./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/Test10* reprennent les mêmes étapes. La prise en compte des tableaux d'entiers (milestone 9) ne se fera qu'a 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)* "}". L'implémentation dans le compilateur est optionnelle (non géré par l'allocator fourni)
  • Ajout des constantes entières négatives (moins unaire uniquement sur les constantes).
  • 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 Java)
(Super-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 d'entier.
  • Il existe une classe "Object". Une classe sans extends explicite est considérée comme étant extends Object.
  • La classe "Object" contient la méthode Object.equals(Object). Implémentation dans semantic.SemanticTree et runtime MIPS.
  • L'héritage des méthodes, le polymorphisme et la surdéfinition (overridding) ne seront pas gérés intégralement dans la compilation. En pratique, la génération finale MIPS supposera les méthodes identifiées uniquement par leur nom.
  • La liaison dynamique n'est pas géré 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'instruction. Pas de difficultés mais pas très utiles 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 eles". Au niveau de la génération, se factorise avec if ,,, else {}.
  • Ajouter les méthodes void. Traiter void comme un nom de type ou pas ?
  • (super-mega-bonus) Utiliser une grammaire complète de Java (~500lignes) : BNF Java7
La définition des priorités et associativités dans Java (et donc pour minijava) :
PrioritéOpérateurTypeAssociativité
1 (basse)=
+= -= *= ...
AffectationsDroite
2? :Opérateur TernaireDroite
3||OR logiqueGauche
4&&AND logiqueGauche
5|OR inclusif bit à bitGauche
6^OR exclusif bit à bitGauche
7&AND bit à bitGauche
8== !=ÉgalitésGauche
9 < <= > >=
instanceof
ComparaisonsGauche
10 << >> >>>Décalages bitsGauche
11 + -Addition SoustractionGauche
12 * / %Multiplication,Division,Modulo Gauche
13 ++ --
+ - ! ~
(type)
Pré-incréments
Opérateurs unaires
Transtypage
Droite
14 ++ -- Post-incréments Droite
15 (haute) ()
[]
·
Parenthèses
Élément de tableau
Sélection attribut/méthode
Gauche
Effet de bord gênant des priorités dans CUP : Lorsque des tokens ont une priorité déclarée dans CUP, ils sont considérés comme plus prioritaires que les tokens sans priorité. Ainsi quand on ajoute un nouveau token dans la spécification avec un éventuel nouveau conflit shift/reduce, CUP ne signalera éventuellement pas ce conflit qu'il considère déjà résolu avec la priorité par défaut.
Une description synthétique de l'AST (package syntax.ast.*) avec les constructeurs de chaque nœud (NB : Champs des nœuds == Arguments du constructeur) : La traitement d'erreurs n'est pas la priorité du compilateur minijava. Il convient toutefois de pouvoir stopper l'exécution en cas d'erreurs. L'exception main.CompilException 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 faire toutes les fonctions sémantiques même si une des fonctions implique de ne pas continuer la générations. On pourra gérer ce cas par exemple en utilisant un booléen error, activé en cas d'erreur, et testé en fin de phase pour lancer une exception plutôt que de continuer la phase suivante. (Illustration dans semantic.Semantic)

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 le 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) { currentValue=calcul(currentValue,node,...) // Héritage de l'attribut AttrType savedValue=currentValue; // Backup for ( ASTNode fils : node) recurse(fils) // Recursion currentValue=savedValue // Restore }
  • Solution "récursif sans retour (void)" : 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) AttrType r1=RETOUR; recurse(fils2) AttrType r2=RETOUR; ... RETOUR=calcul(r1,r2,...) 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é attr = new SemanticAttribut<>(); AttrType currentValue=rootValue; recurse (ASTNode node) { currentValue=calcul(currentValue,node,...) // Héritage de l'attribut attr.set(node, currentValue) // Stockage for (ASTNode fils : mode) recurse(fils) // Récursion currentValue=attr.get(node); // Restore }
  • Attribut Synthétisé attr = new SemanticAttribut<>(); recurse (ASTNode node) { for (ASTNode fils : mode) recurse(fils) // Récursion attr.set(node, calcul(attr.get(fils1),attr.get(fils2),...) //Synthése de l'attribut ) // .. et Stockage return; }
La structure de données pour la table des symboles est fournie dans le package semantic.symtab.*.
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 de 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. L'héritage des classes objets est codé dans la structure d'arbre des portées en utilisant la classe semantic.CheckInheritance qui vérifie l'absence de boucles dans l'héritage, puis modifie la table des symboles en intégrant l'arbre d'héritage à la racine de l'arbre des portées. La construction de la table des symboles est donc réalisée en deux passes.

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 les 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 Minijave (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, getVariable, lookupKlass, ..., lookupMethod,...
  • Les méthodes lookup* intègrent la recherche récursive en remontant l'arbre de portée. Les autres méthodes agissent uniquement sur la portée courante.
  • cf. sources et énoncé du TP pour plus de détails
La Représentation Intermédiaire est fournie dans la package intermediate.ir.* et la classe intermediate.IR..
La Représentation Intermédiaire utilise un schéma "code à 3 adresses". Un programme est une séquence d'instructions IRQuadruple. Une instruction peut potentiellement utiliser trois variables ( ou "adresses" ou IRVar) : arg1, arg2, result et un main.OPER op. Cette utilisation. sera spécifique pour chaque type d'instruction
Les "adresses" IRVar se déclinent en :
  • IRConst pour des constantes ou valeurs immediate de l'assembleur
  • IRLabel pour des noms de label qui deviendront des adresses de saut dans l'assembleur
  • IRTempo pour des variables ajoutées dans la génération de code intermédiaire (variables temporaires pour exécuter les calculs...)
  • semantic.symtab.InfoVar pour les variables issues du code source

Une description synthétique de la forme Intermédiaire du compilateur Minijava :

L'environnement d'exécution (interaction avec le système d'exploitation) du code produit par le compilateur est réalisé par la concaténation d'un Runtime MIPS. Le runtime fournit les fonctions :
  • _system_out_println pour l'impression d'une valeur entière
  • _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 Object.equals(Object o)

Pour la réalisation du compilateur Minijava, on peut se limiter à un ensemble réduit d'instruction MIPS : La classe utilitaire codegen.MIPS fournit des "helpers" basiques pour l'écriture MIPS avec cet ensemble d'instruction.

La convention d'appel est précisée dans les slides du cours.

CSC 4536, TELECOM SudParis, P. Hennequin,Last modified: Nov 2019