Logo EPFL
LAMP
Ecole Polytechnique Fédérale de Lausanne
Compilation 2004/2005
French only
Partie 3 : Construction de l'arbre

A présenter lors de la séance du 10 décembre 2004.

  But

Le but de cette partie est de modifier l'analyseur syntaxique pour qu'il construise l'arbre syntaxique correspondant au programme source. Cet arbre syntaxique sera ensuite utilisé par toutes les phases suivantes du compilateur.

La première chose à faire est de choisir une syntaxe abstraite pour le langage eins. Une syntaxe vous est proposée ici, mais vous êtes libres de choisir la vôtre si la nôtre ne vous convient pas. Notez toutefois que les fichiers que nous distribuons utilisent cette syntaxe abstraite.

Une fois la grammaire abstraite choisie, il importe de la traduire en code Java, en écrivant une sous-classe de la classe Tree pour chaque construction de la grammaire abstraite. Ensuite, l'analyseur syntaxique doit être augmenté afin de construire effectivement l'arbre. Finalement, pour vérifier que l'arbre construit est correct, il faut un moyen de l'imprimer sous forme textuelle.

Nous avons introduit dans le langage eins une certaine quantité de sucre syntaxique. On nomme ainsi les constructions d'un langage qui sont strictement équivalentes à d'autres, mais qui ont une syntaxe différente. Le sucre syntaxique n'apporte donc aucune expressivité au langage, mais permet par contre souvent de rendre la vie du programmeur plus douce, en allégeant certaines notations, d'où son nom.

Un exemple de sucre syntaxique en Java est la boucle for. En effet, tout ce qui est exprimable au moyen de la boucle for est exprimable au moyen de la boucle while, puisqu'on a l'équivalence suivante :

          for (e1; e2; e3) e4
        
est équivalent à
          e1;
          while (e2) {
          e4; e3;
          }
        

La boucle for n'est donc pas strictement nécessaire en Java, puisqu'elle ne permet pas d'exprimer des choses qui ne sont pas exprimables sans elle, mais elle permet parfois de simplifier et de clarifier les programmes.

Le sucre syntaxique de eins est défini dans la table ci-dessous. La manière correcte (et simple) de traiter le sucre syntaxique dans un compilateur est de le supprimer totalement, au moment de la construction de l'arbre. Le sucre syntaxique existe donc dans la grammaire concrète, mais pas dans la grammaire abstraite. Cela simplifie grandement les phases ultérieures du compilateur, qui doivent gérer uniquement les constructions de base du langage.

N°  Désignation Notation Equivalence
1 Valeur false false 0
2 Valeur true true 1
3 "et" logique expr1 & expr2 !(!expr1 | !expr2)
4 if sans else if (cond) expr if (cond) expr else new Unit()
5 Chaîne de caractères "c1 ... cn" new List(code(c1), ... new List(code(cn), null)...)
6 Bloc (expression) { stat1 ... statn } { stat1 ... statn new Unit() }

Dans l'équivalence du sucre syntaxique pour les chaînes de caractères, l'expression code(c) représente le code ASCII du caractère c.

Le tableau ci-dessous donne quelques exemples de transformation de sucre syntaxique.

L'expression ... est interprétée comme ... d'après la (les) règle(s) n°...
true & false !(!1 | !0) 1,2,3
if (c) a if (c) a else new Unit() 4
"eins" new List(101, new List(105, new List(110, new List(115, null)))) 5
{ do printInt(42); } { do printInt(42); new Unit() } 6
{} { new Unit() } 6

Nous vous fournissons les fichiers suivants pour vous aider dans cette partie.

  • Tree-partial.java (à renommer en Tree.java) contient, comme auparavant, la définition de la classe abstraite Tree, classe mère de toutes les classes des noeuds de l'arbre. Nous avons ajouté à ce fichier la définition de plusieurs sous-classes concrètes de Tree, en fonction de notre grammaire abstraite. Il ne vous reste que quelques sous-classes à ajouter.
  • Visitor-partial.java (à renommer en Visitor.java) contient la définition de l'interface Visitor.
  • Printer-partial.java (à renommer en Printer.java) contient la définition d'un visiteur qui imprime l'arbre syntaxique. Comme pour Tree-partial.java, la plus grosse partie du travail est faite, il ne vous reste qu'à ajouter les fonctions pour les noeuds que vous rajoutez dans Tree-partial.java.
  • PrinterTest.java contient un programme qui vous permet de tester votre analyseur syntaxique.

Bien entendu, le gros du travail consiste à modifier votre analyseur syntaxique (fichier Parser.java) afin qu'il construise l'arbre.