Description de l'étape

Vous devez écrire un analyseur syntaxique (parser) correspondant à la spécification de Vier (grammaire syntaxique).

En général, il faudra modifier la grammaire avant de commencer l'implantation pour la rendre compatible avec la technique d'analyse (LL(1) pour la descente récursive). Cette grammaire modifiée doit être équivalente dans la mesure où un programme accepté par la grammaire de Vier doit l'être aussi par votre grammaire modifiée, et qu'un programme qui n'est pas accepté par la grammaire de Vier ne doit pas l'être par la vôtre.

Votre analyseur doit bénéficier des caractéristiques suivantes.

Soyez attentif au lexème “Null” qui n'existait pas ou s'appelait “Nothing” dans des versions précédentes de la spécification de Vier. Pensez à modifier l'analyseur lexical pour le traiter correctement.

Classe du parser

Dans le cas le plus simple, la seule classe sur laquelle vous aurez à travailler est celle de l'analyseur syntaxique lui-même. Pour cela, définissez une classe avec l'interface suivante. 

package vierc
class Parser(in: java.io.InputStream) extends Scanner(in) {
  def parse: Unit
}
parse
Une méthode qui va analyser (par rapport à la grammaire Vier) le flux de lexèmes du scanner. Si vous implantez un analyseur sans gestion d'erreurs et si le programme analysé est incorrect, cette méthode ne retourne pas (une erreur fatale termine l'application). Si vous utilisez la gestion d'erreurs (voir plus bas), la méthode retourne toujours, mais les erreurs détectées sont publiées, par exemple à l'aide la classe Report.

Un canevas pour cet objet est à votre disposition.

Autres classes de support

Report.scala
Cet objet fournit des services pour signaler des erreurs.
ParserTest.scala
Cet objet permet de tester votre analyseur syntaxique, à condition que l'interface de votre analyseur corresponde.

Bien entendu, votre scanner est nécessaire pour implanter cette étape, et doit être compilé en parallèle avec le parser.

Conseil d'implantation

Soyez rigoureux! Cette étape ne demande pas de créativité au niveau de l'implantation. Il suffit de traduire mécaniquement les règles de la grammaire par les règles vues au cours (transparent 4 du cours “Analyse syntaxique”). Normalement votre analyseurs marchera — presque — au premier essai, mais attention, seulement si vous êtes rigoureux dans la traduction.

Avant de pouvoir appliquer cette traduction, il faut que la grammaire soit LL(1). Assurez-vous que ce soit le cas dès le début. Il est plus facile de transformer une grammaire EBNF que de devoir appliquer la transformation aussi au code de votre analyseur.

Déverminer l'analyse

Du fait de la récursion profonde et complexe inhérente à l'analyse LL(1), il est souvent difficile de savoir ce qui se passe pendant l'analyse. Une solution élégante est d'appeler une méthode à l'entrée et à la sortie de chaque méthode correspondant à un non-terminal. Ces méthodes impriment simplement un arbre indenté correspondant à la récursion sur les non-terminaux de l'analyseur. Vous pouvez utiliser l'implantation suivantes. 

private val debug = true
private var level = 0
private def ruleIn(entry: String): Unit = if (debug) {
  for (i <- 0 until level) print("  ")
  println("-> " + entry + " [" + representation + "]")
  level += 1
}
private def ruleOut[T](exit: String, result: T): T =  {
  if (debug) {
    level -= 1
    for (i <- 0 until level) print("  ")
    result match {
      case result:Iterable[_] =>
        println("<- " + exit + " = " + result.mkString("; "))
      case result =>
        println("<- " + exit + " = " + result.toString)
    }
  }
  result
}

Notez le type de retour de “ruleOut”. Il deviendra relevant quand votre analyseur générera des arbres de syntaxe. Pour le moment, le résultat de chaque méthode d'analyse est simplement la valeur vide (“unit”, notée “()”)

Gérer les erreurs

Lorsque votre analyseur traverser un programme qui n'est syntaxiquement pas correct, il finira par se trouver dans un état où l'on sait que le programme n'est pas valide par rapport à la grammaire syntaxique de Vier parce que le lexème suivant ne peut apparaître à cet endroit. Il peut aussi arriver que votre analyseur lexical fournisse un flux de lexème qui contienne des BAD. Bien entendu, un tel flux ne peux pas représenter un programme correct, puisque le lexème BAD n'est présent nulle-part dans la grammaire syntaxique de Vier.

La solution la plus simple pour traiter ces cas est simplement de générer une erreur fatale dès que l'on détecte que le programme analysé n'est pas un programme valide. Cette solution est acceptable dans le cadre du projet et est suffisante pour obtenir tous les points.

Mais le but des phases d'analyse (lexicale, syntaxique et de type) d'un compilateur pour un langage typé et d'aider le programmeur en l'informant du plus grand nombre d'erreurs possible. Pour cela, l'analyse va continuer après une situation d'erreur en essayant de se synchroniser de nouveau avec la grammaire pour retrouver une partie du programme qui est correcte et sur laquelle il fait sens de continuer l'analyse (et de générer des erreurs). Dans le cas du lexème BAD, si la façon de générer ces tokens pendant l'analyse lexicale est sensée, il peut-être suffisant d'ignorer le lexème pour l'analyse. Le programme “restant” étant suffisamment correct pour que l'analyse génère des erreurs intéressantes. Pour les erreurs syntaxiques, la gestion des erreurs est plus délicate et souvent assez ad-hoc. Le cours propose quelques pistes à ce sujet et vos assistants sont à votre disposition pour discuter d'autres solutions.

Nous invitons donc les élèves intéressés à améliorer la gestion des erreurs pour continuer l'analyse même après une erreur.