Projet de compilation: tree

Description de l'étape

Vous devez définir un type de données permettant de représenter la structure syntaxique de tout programme Drei accepté par votre analyseur syntaxique (parser). Ce type peut définir un arbre de syntaxe abstrait (AST) correspondant à notre grammaire abstraite pour Drei, mais vous êtes libres de faire autre chose si ceci vous déplaît.
Vous devez compléter votre analyseur syntaxique (parser) pour générer une instance de votre AST représentant uniquement le programme analysé.
Vous devez aussi disposer d'un moyen, typiquement une méthode «visiteur», pour écrire (dans un fichier ou sur la console) un programme Drei valide à partir d'une instance de votre AST.

Le résultat de l'impression du résultat de l'analyse d'un fichier source Drei par votre compilateur doit être un programme Drei valide, sans sucre syntaxique (vois ci-dessous) et avec le même signification sémantique que l'original. Vous pouvez valider certaines de ces propriétés de la manière suivante.

Exécuter votre compilateur deux fois de suite, en se servant du résultat de la première exécution pour lancer la seconde. Les deux résultats doivent être identiques caractère pour caractère.
Exécuter votre compilateur deux fois de suite, en se servant du résultat de la première exécution pour lancer la seconde, et testez (avec l'opérateur “==” si vous utilisez des classes “case”) l'égalité des ASTs générés par l'analyseur dans les deux cas.

Sucre syntaxique

Certaines constructions de la syntaxe concrète de drei n'ont pas besoin d'être représentées dans l'AST. Ce sont les constructions qui sont strictement équivalentes à d'autres constructions du langages, mais avec une syntaxe différente, et que l'on appelle «sucre syntaxique».

L'AST construit par l'analyseur syntaxique peut encore contenir le sucre syntaxique — ce qui requiert une étape de nettoyage par la suite — ou l'analyseur peut directement générer un AST non sucré. La seconde solution est probablement plus simple.

Equivalences pour les expressions sucrées
Expr. sucrée	Expressions équivalente
`e1 \|\| e2`	`!(!e1 && !e2)`
`false`	`0`
`true`	`1`
`"abc"`	`new Cons(A, new Cons(B, new Cons(C, new Nil())))` où `X` est la position sur la table ASCII du caractère `x`
`""`	`new Nil()`
`if (Expr) Statement`	`if (Expr) Statement else {}`

Classes de l'arbre

Dans le cas le plus simple, vous définirez le type de l'AST par une série de classes case qui héritent d'une classe Tree commune. Rappelez-vous que Scala permet de définir plusieurs classes dans un seul fichier. La classe Tree fournie dispose de l'interface suivante.

package dreic
abstract class Tree {
  def pos: Int
  def setPos(p: Int): this.type
}

pos: Un méthode qui retourne la position à laquelle se trouve le première lexème correspondant à ce noeud de l'arbre.
setPos: Une méthode qui permet de définir la position du noeud. Elle retourne le noeud lui-même afin de permettre de l'utiliser «en ligne», comme dans f(myTree setPos(34)) qui appelle f avec le noeud myTree dont la position à été définie simultanément. Notez qu'une telle fonction ne peut être définie en Java.

Un canevas définissant la classe Tree est à votre disposition.

Class de l'analyseur

Pour l'analyseur, il vous faut modifier la classe Parser de l'étape précédente pour générer l'arbre. L'interface de la classe modifiée sera la suivante.

package dreic
class Parser(in: java.io.InputStream) extends Scanner(in) {
  def parse: Tree
}

parse: Une méthode qui va analyser (par rapport à la grammaire Drei) le flux de lexèmes du scanner et retourner l'AST correspondant.

Classe de l'imprimeur

Si vous définissez l'imprimeur comme une classe, vous pouvez lui donner l'interface suivante.

package dreic
class Printer(out: java.io.PrintWriter) {
  def print(tree: Tree): Printer
}

print: Un méthode qui imprime l'arbre tree sur la sortie out. De manière similaire à setPos, celle-ci retourne une instance de Printer, ce qui permet d'écrire des appels chaînés comme print(…).print(…).print(…).

Vous aurez intérêt à définir d'autres méthodes print…(…) pour imprimer d'autres éléments utiles, comme des listes d'arbres (paramètres des fonctions) ou des noms.

Un canevas pour cette classe est à votre disposition.

Autres classes de support

PrinterTest.scala

Cet objet permet de tester la génération d'AST et votre imprimeur, à condition que l'interface de ceux-ci corresponde. A l'exécution

son premier paramètre est le fichier source du programme à analyser,
son second paramètre, optionnel, est le fichier de destination pour l'impression du résultat.

Ecole polytechnique fédérale de Lausanne

Laboratoire des méthodes de programmation