Compilation : De l'algorithme à la porte logique

Portail informatique

Memento du projet Minijava

Les différentes étapes de la réalisation du compilateur Minijava sont décrites dans la page Compilateur Minijava vers MIPS.
Ce Memento regroupe des documentations utiles tout au long de la réalisation du compilateur. En partie, ces informations sont aussi accessibles via la documentation Java (Javadoc) que l'on peut générer pour le projet.

Structuration des sources

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.

Nouveautés par rapport à un projet JFlex+CUP


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

Les packages du projet

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

Quelques fichiers utiles

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

Définition du langage Minijava

La grammaire BNF de Minijava

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.

Différences avec la version originale


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.

Précisions lexicales pour Minijava


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")

Quelques Hypothèses sémantiques pour Minijava et le compilateur


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.

Extensions (optionnel)


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.

Priorité et Associativité

La définition des priorités et associativités dans Java (et donc pour Minijava) :
Priorité Opérateur Type Associativité
1 (basse) =
+= -= *= ...
Affectations Droite
2 ? : Opérateur Ternaire Droite
3 || OU logique Gauche
4 && ET logique Gauche
5 | OU inclusif bit à bit Gauche
6 ^ OU exclusif bit à bit Gauche
7 & ET bit à bit Gauche
8 == != Égalités Gauche
9 < <= > >=
instanceof
Comparaisons Gauche
10 << >> >>> Décalages bits Gauche
11 + - Addition Soustraction Gauche
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 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.

Description de l'AST

Une description synthétique de l'AST (package syntax.ast.*) avec les constructeurs de chaque nœud.
N.B. : Champs des nœuds == Arguments du constructeur

Gestion des erreurs

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 pour ce cours.
Il convient toutefois de pouvoir stopper l'exécution en cas d'erreurs. L'exception main.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 faire toutes les fonctions sémantiques même si une des fonctions implique de ne pas continuer la génération. 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)

Décoration d'Arbres

Attributs sémantiques


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

Calcul récursif


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) { currentValue=calcul(currentValue,node); // Héritage de l'attribut AttrType savedValue=currentValue; // Sauvegarde 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).

Mise en œuvre pour le compilateur Minijava


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) { currentValue=calcul(currentValue,node); // Héritage de l'attribut attr.set(node, currentValue); // Stockage 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; }

Table des Symboles

La structure de données pour la table des symboles est fournie dans le package semantic.symtab.*.

L'arbre des portées


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

Portées pour Minijava


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.

Séparation des identificateurs


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.

Représentation Intermédiaire

La Représentation Intermédiaire est fournie dans le 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 IRvariable) : arg1, arg2, result et un main.EnumOper op. Cette utilisation sera spécifique pour chaque type d'instruction
Les "adresses" IRvariable 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 :

Génération MIPS

La génération du code MIPS est réalisée dans le package codegen (et codegen.access).

Les classes utilisées sont :
  • Reg : Une classe énumération pour gérer les noms de registre dans les différentes classes du package.
  • MipsWriter : Une classe utilitaire pour écrire le texte MIPS dans un fichier. Contient un ensemble de helpers pour produire et formater un jeu d'instructions MIPS suffisant pour notre compilateur.
  • Allocator : Allocation mémoire de l'ensemble des variables de la forme intermédiaire. Création pour chaque variable d'un access.Access qui produit le code MIPS pour charger ou sauvegarder entre une variable et un registre.
  • ToMips : Traduction de la forme intermédiaire en programme MIPS.
  • LinkRuntime : Ajout d'un runtime MIPS (prédéfini) au programme produit par la traduction ToMips.
  • Codegen : La phase de génération de code du compilateur. Enchaine : la création du fichier MIPS, l'allocation mémoire, la traduction de la forme intermédiaire et l'ajout du runtime MIPS.

Utilisation des registres et convention d'appel


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.

Sélection d'instruction


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

Édition de lien, Runtime


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.

Résumé AST et IR par milestone

Apparition des différents nœuds de l'AST et des instructions Intermédiaires en fonction des milestones du langage Minijava :
Milestone syntax.ast.* intermediate.ir.*
1 Hello World Axiom, KlassMain, Ident, ExprLiteralInt, StmtPrint QLabel, QParam, QCallStatic
2 Calculette ExprOpBin QAssign
3 Classes, Méthodes, Instanciation Klass, Method, Type, ExprNew, ExprCall QLabelMeth, QReturn, QCall, QNew
4 Paramètres formels et Arguments Formal, ExprIdent
5 Variables Variable
6 Expressions ExprOpUn, ExprLiteralBool, StmtAssign QAssignUnary, QCopy
7 Instructions StmtBlock, StmtIf, StmtWhile QJump, QJumpCond
9 Tableaux d'entiers StmtArrayAssign, ExprArrayNew, ExprArrayLookup, ExprArrayLength QAssignArrayFrom, QAssignArrayTo, QNewArray, QLength

CSC4251-52 (CSC 4536), TELECOM SudParis, P. Hennequin,Last modified: Juillet 2022