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 (l'analyse des noms, la vérification des types et la production de code).

La première chose à faire est de choisir une syntaxe abstraite pour le langage misc. 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 pour cette partie 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 introduits dans le langage misc 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. Il faut bien sûr se garder d'ajouter une trop grande quantité de sucre syntaxique à un langage car, comme Alan Perlis l'a joliment dit dans un de ses aphorismes, syntactic sugar causes cancer of the semicolon.

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

  {
    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 misc 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. Par exemple, les phases de vérification de type et de production de code d'un compilateur Java n'ont pas besoin de connaître l'existence de la boucle for, et peuvent se contenter de traiter la boucle while.

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.

En écrivant le code de construction des arbres, vous constaterez qu'il est souvent nécessaire de construire des tableaux d'arbres de taille non connue d'avance. Les tableaux Java n'étant pas redimensionnables, il est nécessaire d'utiliser une autre structure de données durant la collecte des données, et de la transformer ensuite en un tableau.

La bibliothèque standard de Java propose, dans le paquetage java.util, des structures de données parfaitement adaptées au problème : les listes. L'exemple suivant montre comment construire une liste de chaînes, la remplir, et finalement la transformer en un tableau. Pour plus d'information, reportez-vous à la documentation de Sun.

  List strList = new LinkedList ();
  strList.add ("salut");
  strList.add ("ça va ?");
  String[] strArray = (String[]) strList.toArray (new String[strList.size ()]);

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

• Tree.java contient, comme auparavant, la définition de la classe abstraite Tree, classe mère de toutes les classes des nœuds 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.
• Printer.java contient la définition d'un visiteur qui imprime l'arbre syntaxique. Comme pour Tree.java, la plus grosse partie du travail est faite, il ne vous reste qu'à ajouter les fonctions pour les nœuds que vous rajoutez dans Tree.java.
• PrinterTest.java contient un programme qui vous permet de tester votre analyseur syntaxique. Le programme lit un fichier source, l'analyse et imprime dans un fichier objet l'arbre retourné par l'analyseur.

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

Différences

La réalisation en Scala est très semblable à celle en Java. La principale différence est qu'au lieu d'utiliser la technique du visiteur, on utilise la reconnaissance de motifs (pattern matching). C'est pourquoi dans Tree.scala toutes les classes de nœuds sont des classes cas et la classe Printer n'implémente pas de visiteur, mais contient un appel à la méthode match de la classe Tree avec en argument les différents motifs de nœuds.

Une autre différence est qu'on utilise pas (ou très peu) les tableaux java et les listes du paquetage java.util. On préfère utiliser les listes Scala (type scala.List). Celles-ci sont documentées ici. Si vous préférez, vous pouvez aussi consulter leur code source. Celui-ci se trouve dans le fichier List.scala dans le répertoire share/scala/library/scala de la distribution. Sur les machines de la salle INF 3, il se trouve ici :

/home/iclamp/local/packages/scala/share/scala/library/scala/List.scala

Fichiers

Ci-dessous, les fichiers à utiliser pour le projet en Scala.

• Tree.scala contient, comme auparavant, la définition de la classe abstraite Tree, classe mère de toutes les classes des nœuds 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.
• Printer.scala contient une classe qui permet d'imprimer l'arbre syntaxique. Comme pour Tree.scala, la plus grosse partie du travail est faite, il ne vous reste qu'à ajouter les fonctions pour les nœuds que vous rajoutez dans Tree.scala.
• PrinterTest.scala contient un programme qui vous permet de tester votre analyseur syntaxique. Le programme lit un fichier source, l'analyse et imprime dans un fichier objet l'arbre retourné par l'analyseur.