Compilation : partie 3

À présenter lors de la séance du 13 décembre 2002

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

Travail à effectuer

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.

Sucre syntaxique

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

Désignation Notation Equivalence
1 Valeur false false 0
2 Valeur true true 1
3 if sans else if (cond) expr if (cond) expr else ()
4 "ou" logique expr1 | expr2 if (expr1) true 1 else expr2
5 "et" logique expr1 & expr2 if (expr1) expr2 else false 0
6 "non" logique ! expr if (expr) 0 else 1
7 Négation - expr 0 - expr
8 Listes [expr1, expr2, ..., exprn] expr1::expr2::...::exprn::[]
9 Chaînes de caractères "c1c2...cn" code(c1)::code(c2)::...::code(cn)::[]
10 Bloc { stat1; stat2; ...; statn; } { stat1; stat2; ...; statn; () }

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 transformée en ... d'après la (les) règle(s) n°...
if (c) a if (c) a else () 3
c | d if (c) 1 else d 4, 2
[109, 105, 115, 99] 109::105::115::99::[] 8
"misc" 109::105::115::99::[] 9
{} { () } 10
{ printInt(42); } { printInt(42); () } 10
{ printInt(42) } { printInt(42) } aucune (ce n'est pas du sucre syntaxique)

Tableaux d'arbres

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 ()]);

Fichiers

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

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

Projet en Scala

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.