Accueil Nos publications Blog JVM Hardcore – Part 8 – Mon premier analyseur syntaxique – 2/2

JVM Hardcore – Part 8 – Mon premier analyseur syntaxique – 2/2

academic_duke Après avoir étudié le fonctionnement d’un type d’implémentation sur un analyseur syntaxique LL dans l’article précédent, nous allons enrichir notre grammaire pour pouvoir analyser une expression arithmétique complexe.

Le code est disponible sur Github (tag et branche)

Notons que le code associé à l’article est différent des précédents puisqu’il contient de multiples branches permettant de suivre pas à pas la construction de notre analyseur.

Tous les articles déjà publiés de la série portent le tag jvmhardcore.

Évolution de la grammaire

Pour rappel, dans l’article précédent nous nous étions arrêtés à la grammaire suivante (nous laisserons de côté les symboles stream et eof, bien qu’ils soient présents dans le code) :

expression = digit operator digit
operator = '+'
digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

Au cours de cet article, nous allons faire évoluer cette grammaire. Par conséquent, il arrivera parfois que certains symboles soient modifiés et d’autres ajoutés. Pour identifier simplement ces différents cas, la définition d’un symbole modifié sera suivi de (* Nouveau *) et celle d’un nouveau symbole de (* Modifié *).

EBNF : le texte entre les caractères (* et *) est un commentaire.

Multiples opérateurs

Branche part08_01

Nous pouvons très simplement ajouter d’autres opérateurs :

expression = digit operator digit
operator = '+' | '-' | '/' | '*' (* Modifié *)
digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

La modification du code n’a rien de très compliquée.

public int getOperator() {
  int character = this.next();

  if ( character == Ascii.PLUS_SIGN
    || character == Ascii.HYPHEN
    || character == Ascii.ASTERIX
    || character == Ascii.SLASH
      ) {
    return character;
  } else {
    throw new ParserException("Expected: '+' or '-' or '*' or '/'.");
  }
}

Source

Nombres

Branche part08_02

Nous permettons ensuite l’utilisation de nombres (positifs pour l’instant) :

expression = number operator number
number = digit {digit} (* Nouveau *)
operator = '+' | '-' | '/' | '*'
digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

EBNF : les caractères { et } indiquent une répétition optionnelle et illimitée. Le nombre peut donc être composé d’un seul chiffre ou de plusieurs.

Lors de la création d’une grammaire, le plus simple est de partir du symbole à modifier (expression dans note cas) et de faire les modifications sans penser à une quelconque factorisation, comme par exemple :

expression = digit {digit} operator digit {digit}

Un nombre (number) est donc un chiffre (digit) suivi de zéro ou de plusieurs chiffres.

Nous allons autoriser les nombres commençant par plusieurs 0, mais aussi composés uniquement de zéros.

Cette situation est l’exemple typique pour lequel un symbole ne correspond pas à une production. Il est inutile de déclencher un événement par chiffre. Ce qui nous intéresse est d’avoir le nombre complet.

Pour rester cohérent nous allons renommer la production Digit (de la branche précédente) en Number, le symbole et l’événementDIGIT en NUMBER et pour finir la méthode getDigit() en getNumber().

Il ne nous reste plus qu’à modifier la méthode getNumber() pour répondre à notre nouvelle grammaire :

public String getNumber() {
  int character = Ascii.NULL;

  while(isDigit(character = this.next())) {
    generator.appendChar(character);
  }

  if (!generator.isEmpty()) {
    this.rewind();
    return generator.toString();
  } else {
    throw new ParserException("Expected: At least one Digit [0-9].");
  }
}

Trois points importants sont à noter :

  • La méthode retourne à présent une chaîne de caractères et non plus un entier (qui correspondait au point de code du chiffre, et non au chiffre lui-même). Les tests unitaires et le code correspondant à l’événement NUMBER ont donc été modifiés en conséquence.
  • Nous ajoutons les caractères à un champ generator qui est un StringBuilder ayant des méthodes adaptées à un Tokenizer (cf. StringGenerator).
  • Avant de retourner le nombre analysé, nous faisons appel à la méthode rewind() qui va reculer d’un caractère le Reader (le dernier caractère lu qui n’est pas un chiffre)

Nombres à virgule

Branche part08_03

Pour pouvoir utiliser des nombres à virgule nous avons plusieurs solutions. La première consiste à différer la connaissance du type du nombre (entier ou nombre à virgule) au moment de la résolution de l’expression :

number = repeatingDigit [dot] repeatingDigit
repeatingDigit = {digit}
dot = '.'

La seconde (celle que nous allons mettre en place) permet de déterminer le type du nombre lors de l’analyse syntaxique.

expression = number operator number
number = integer | float (* Modifié *)
integer = repeatingDigit (* Nouveau *)
float = oRepeatingDigit [dot] oRepeatingDigit (* Nouveau *)
repeatingDigit = digit repeatingDigit (* Modifié *)
oRepeatingDigit = {digit}  (* Nouveau *)
operator = '+' | '-' | '/' | '*'
digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
dot = '.' (* Nouveau *)

EBNF : les caractères [ et ] indiquent un élément optionnel.

Le o du symbole oRepeatingDigit signifie optionnel.

Les nombres à virgule que nous acceptons peuvent avoir les formes suivantes : 1.1, .567 ou 23. Mais aussi uniquement un point ‘.’ ce qui n’est absolument pas ce que nous souhaitons. Des commentaires ou une spécification informelle sont alors indispensables pour apporter des précisions.

(* au moins un chiffre doit être présent à droite ou à gauche du point
  (ex: 1.1, .567 ou 23.) *)
float = oRepeatingDigit [dot] oRepeatingDigit

Nous avons aussi la possibilité de complexifier la grammaire :

float = (repeatingDigit [dot] repeatingDigit)
        | (repeatingDigit [dot])
        | ([dot] repeatingDigit)

EBNF : Les caractères ( et ) indique un groupe. Le symbole number est composé du symbole sign suivit du symbole integer ou float.

Il reviendra à chacun de faire les choix lui semblant les plus appropriés, sachant que dans certains cas une grammaire trop complexe est beaucoup plus difficile à implémenter qu’une grammaire simple associée à une spécification informelle indiquant les diverses contraintes.

Malgré un impact important dans la grammaire, l’impact sur le code est limité.

Nous n’allons pas rajouter de production, mais uniquement modifier la production Number, ce qui signifie que nous n’ajouterons pas de symboles :

public static class Number implements Production<EventType, MathTokenizer> {
  public EventType produce(MathTokenizer tokenizer,
                           Production<EventType, MathTokenizer>[] table,
                           Stack<Production<EventType, MathTokenizer>> productionStack) {
    if (tokenizer.isFloat()) {
      return EventType.FLOAT;
    } else {
      return EventType.INTEGER;
    }
  }
}

Le tokenizer passé en paramètre de la méthode produce() dont nous n’avions pas d’utilité jusqu’à présent prend tout son sens dans cette situation. Nous souhaitons déterminer le prochain symbole à analyser par la méthode parse().

La règle est donc simple, une méthode de l’objet tokenizer peut être appelée dans une méthode produce() si elle ne consomme pas de caractères utiles à l’analyse. Nous obtenons donc deux cas :

  • la méthode effectue un test, elle appelle la méthode mark() du reader au début et la méthode reset() à la fin.
  • la méthode consomme des caractères inutiles à l’analyse (espaces ou commentaires). Nous verrons ce cas un peu plus loin.

Voyons l’implémentation de la méthode isFloat() :

public boolean isFloat() {
  this.mark();

  int character = Ascii.NULL;

  // Nombre de chiffres
  int counter = 0;

  // Compte le nombre de chiffres
  while (isDigit(character = this.next())) {
    counter++;
  }

  // Vérifie si le caractère suivant est un point
  if (Ascii.PERIOD != character) {
    this.reset();
    return false;
  }

  // S'il y a des chiffres avant le point, nous n'avons pas besoin de continuer,
  // il s'agit d'un nombre à virgule
  if (counter > 0) {
    this.reset();
    return true;
  }

  // Compte le nombre de chiffres après le point
  while (isDigit(character = this.next())) {
    counter++;
  }

  // S'il y a des chiffres après le point c'est un nombre à virgule
  if (counter > 0) {
    this.reset();
    return true;
  }

  // Il n'y a pas de chiffre avant et après le point
  this.reset();
  return false;
}

Pour l’instant, que l’événement soit un FLOAT ou un INTEGER n’a pas d’importance puisque nous mettons tout dans un tableau de chaînes de caractères :

public String[] parse() {
  // ...

  switch (eventType) {
    case FLOAT:
      this.tokens[counter++] = this.tokenizer.getFloat();
      break;
    case INTEGER:
      this.tokens[counter++] = this.tokenizer.getInteger();
      break;

    // ...
  }

  // ...
}

Source

La méthode getInteger() est tout simplement la méthode getNumber() de la branche précédente renommée.

Quant à la méthode getFloat() son implémentation est la suivante :

public String getFloat() {
  int character = Ascii.NULL;

  while (isDigit(character = this.next())) {
    generator.appendChar(character);
  }

  // getFloat() est appelée après isFloat()
  // par conséquent nous n'avons pas besoin de vérifier
  // si le caractère est un point
  generator.appendChar(character);

  while (isDigit(character = this.next())) {
    generator.appendChar(character);
  }

  this.rewind();
  return generator.toString();
}

Nombres signés

Branche part08_04

Continuons l’enrichissement de notre grammaire en ajoutant la possibilité d’avoir des nombres signés.

expression = number operator number
number = sign (integer | float) (* Modifié *)
integer = repeatingDigit
float = oRepeatingDigit [dot] oRepeatingDigit
repeatingDigit = digit repeatingDigit
oRepeatingDigit = {digit}
sign = '+' | '-' | ''  (* Nouveau *)
operator = '+' | '-' | '/' | '*'
digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
dot = '.'

Le symbole sign peut être un caractère vide, ce qui évite de le définir en tant que symbole optionnel :

number = [sign] (integer | float)
sign = '+' | '-'

La modification du code est très simple. Seule la classe MathTokenizer est impactée. Nous devons rajouter quelques lignes aux méthodes suivantes :

isFloat() :

    int character = this.next();

    // Ignore le signe
    if (character != Ascii.PLUS_SIGN && character != Ascii.HYPHEN) {
        this.rewind();
    }

getInteger() et getFloat() :

int character = this.next();

if (character == Ascii.PLUS_SIGN) {
  // Ignore
} else if (character == Ascii.HYPHEN) {
  generator.appendChar(character);
} else {
  this.rewind();
}

Espaces

Branche part08_05

Jusqu’à présent, nous avons imposé la saisie de caractères ayant un sens dans une expression arithmétique. Or pour plus de clarté et pour que nous puissions saisir l’expression sur plusieurs lignes, nous devons autoriser la saisie de caractères d’espacement, que ce soit le caractère espace (0x20) ou les retours à la ligne (0x0A, 0x0D, etc.)

expression = ws number ws operator ws number ws (* Modifié *)
number = sign (integer | float)
integer = repeatingDigit
float = oRepeatingDigit [dot] oRepeatingDigit
repeatingDigit = digit repeatingDigit
oRepeatingDigit = {digit}
sign = '+' | '-' | ''
operator = '+' | '-' | '/' | '*'
digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
dot = '.'
ws = ? caractères d'espacement ? (* Nouveau *)

Pour permettre la saisie de caractère d’espacement, la grammaire n’a été que légèrement modifiée. Il a suffi de rajouter un nouveau symbole terminal (ws) et de le placer entre chaque opérande de l’expression.

L’impact dans le code est lui aussi minime. Nous commençons par ajouter une production pour le nouveau symbole (Whitespaces).

public static class Whitespaces implements Production<EventType, MathTokenizer> {
  public EventType produce(MathTokenizer tokenizer,
                           Production<EventType, MathTokenizer>[] table,
                           Stack<Production<EventType, MathTokenizer>> productionStack) {
    tokenizer.consumeUnprintables();
    return null;
  }
}

Le seul objectif de la production Whitespaces est de consommer des caractères d’espacement. Elle n’ajoute rien à la pile de productions et ne retourne aucun événement. Il s’agit en réalité du troisième et dernier mécanisme possible de la méthode produce().

Pour résumer le comportement de la méthode produce() est le suivant en fonction du symbole que sa production représente :

  • si une production représente un symbole terminal, la produce() empile des productions dans la pile de production et retourne null
  • si une production représente un symbole terminal, la produce() retourne un événement
  • si une production représente un symbole terminal, la produce() consomme des caractères et retourne null

Notons que nous avons aussi utilisé la méthode consumeUnprintables() de la classe Tokenizer qui consume tous les caractères entre NULL (0x00) et SPACE (0x20) et pas seulement les caractères d’espacement. Ceci n’a vraiment pas d’importance puisque tous ces caractères n’ont aucun intérêt pour nous et qu’il est par conséquent préférable de les ignorer que de lever une exception.

Nous ajoutons ensuite le nouveau symboles WS à notre table de production dans la méthode initProductionTable() de la classe MathParser.

@Override
protected void initProductionTable() {
  // ...
  this.table[Symbols.WS] = new Productions.Whitespaces();
}

Nombre d’opérandes variable

Branche part08_06

Nous allons maintenant lever la limite de trois opérandes dans notre expression :

expression = ws number orRightExpression ws (* Modifié *)
orRightExpression = {ws operator ws number} (* Nouveau *)
number = sign (integer | float)
integer = repeatingDigit
float = oRepeatingDigit [dot] oRepeatingDigit
repeatingDigit = digit repeatingDigit
oRepeatingDigit = {digit}
sign = '+' | '-' | ''
operator = '+' | '-' | '/' | '*'
digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
dot = '.'
ws = ? caractères d'espacement ?

Avec notre grammaire modifiée, nous allons pouvoir écrire des expressions de ce type :

37. + -.2 - 4.3 * 68

mais aussi seulement :


-256

Cette fois, nous avons complètement modifié la manière de représenter une expression. Une expression a au moins une opérande qui est un nombre et optionnellement un ou plusieurs groupes constitués d’un opérateur suivi d’un nombre.

Le préfixe or dans le nom du symbole orRightExpression signifie, optionnel et répétitif.

Avant de continuer voyons pourquoi nous n’avons pas écrit simplement :

expression = ws number {ws operator ws number} ws

Pour définir une grammaire ceci est tout à fait correct. Tout comme pour d’autres symboles tels que number que nous avons implémentés précédemment, mais puisque nous n’avions pas besoin de créer une production, ce cas particulier n’a pas été abordé.

Si l’on souhaite pouvoir implémenter la grammaire, sans aucune modification, à l’aide d’un analyseur syntaxique LL, une telle écriture n’est tout simplement pas possible.

Tout d’abord, si un symbole contient une partie optionnelle, elle doit être impérativement assignée à un symbole qui lui est propre, puisque nous avons besoin d’effectuer un test nous permettant de savoir s’il est présent ou non, et donc si nous devons le rajouter dans la pile de productions :

public static class OrRightExpression implements Production<EventType, MathTokenizer> {
  public EventType produce(MathTokenizer tokenizer,
                           Production<EventType, MathTokenizer>[] table,
                           Stack<Production<EventType, MathTokenizer>> productionStack) {

    tokenizer.consumeWhitespaces();

    if (tokenizer.isOperator()) {
      productionStack.push(table[Symbols.OR_RIGHT_EXPRESSION]);
      productionStack.push(table[Symbols.NUMBER]);
      productionStack.push(table[Symbols.WS]);
      productionStack.push(table[Symbols.OPERATOR]);
    }

    return null;
  }
}

Source

Nous modifions ensuite la production Expression. Ces productions n’ayant rien de notable nous ne nous attarderons pas dessus. Tout comme le nouveau symbole OR_RIGHT_EXPRESSION ou la méthode initProductionTable() de la classe MathParser. Notons qu’en raison du fait que nous pouvons avoir des expressions ayant un nombre d’opérandes variable, la méthode parse(), ne retourne plus un tableau de chaînes de caractères, mais une java.util.LinkedList de chaînes de caractères.

Il ne nous reste donc plus qu’à voir la méthode isOperator() qui ne mérite pas plus d’explications :

public boolean isOperator() {
  final int character = this.next();
  this.rewind();
  return isOperator(character);
}

public boolean isOperator(int character) {
  return character == Ascii.PLUS_SIGN
          || character == Ascii.HYPHEN
          || character == Ascii.ASTERIX
          || character == Ascii.SLASH;
}

Forcer la priorité

Branche part08_07

Pour terminer nous allons introduire la possibilité d’utiliser des parenthèses pour changer la priorité de la résolution de notre expression :

expression = orLeftParenthesis ws number orRightExpression ws (* Modifié *)
orRightExpression = {ws operator rLeftParenthesis number orRightParenthesis ws} (* Modifié *)
orLeftParenthesis = {ws leftParenthesis} (* Nouveau *)
orRightParenthesis = {ws rightParenthesis} (* Nouveau *)
number = sign (integer | float)
integer = repeatingDigit
float = oRepeatingDigit [dot] oRepeatingDigit
repeatingDigit = digit repeatingDigit
oRepeatingDigit = {digit}
sign = '+' | '-' | ''
operator = '+' | '-' | '/' | '*'
digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
dot = '.'
ws = ? caractères d'espacement ?
leftParenthesis = '(' (* Nouveau *)
rightParenthesis = ')' (* Nouveau *)

Cette dernière version de notre grammaire n’introduisant aucune nouveauté, nous ne nous attarderons pas dessus. Néanmoins, nous constatons, à nouveau que des incohérences peuvent apparaître à cause des parenthèses. La grammaire ne nous interdit aucunement de ne pas avoir autant de parenthèses ouvrantes que de parenthèses fermantes. Il conviendra donc de gérer ce cas au niveau du code, et nous verrons ceci dans l’article suivant.

Le code n’ayant rien de particulier, nous nous contenterons de résumer les modifications :

Voyons néanmoins quelques tests unitaires nous permettant de balayer les différents types d’expressions pouvant être analysés par notre analyseur syntaxique.

// Construit une liste
private LinkedList<String> expected(final String ... strings) {
  final LinkedList<String> list = new LinkedList<>();

  for (String s : strings) {
    list.add(s);
  }

  return list;
}

// A partir d'une expression à analyser,
// teste si la liste générée est égale à la liste attendue.
private void test(final String expression, final LinkedList<String> expected) {
  final InputStream inputStream = new ByteArrayInputStream(expression.getBytes());
  final MathParser parser = new MathParser(inputStream);
  final LinkedList<String> tokens = parser.parse();
  Assert.assertEquals(expected, tokens);
}

@Test
public void expressionWithParenthesis5() {
    this.test("(2 * (2 + 5) - (10 - 8)) + 3",
              this.expected("(", "2", "*", "(", "2", "+", "5", ")",
                            "-", "(", "10", "-", "8", ")", ")", "+", "3"));
}

@Test
public void expressionWithParenthesis6() {
  this.test("4 - (2 + 5) - 2",
            this.expected("4", "-", "(", "2", "+", "5", ")", "-", "2"));
}

Source

Récapitulatif de la syntaxe EBNF

Terminons par un récapitulatif des différents opérateurs EBNF.

Il est important de noter que bien qu’il y ait un standard, il n’est jamais complètement respecté, et cet article ainsi que le précédent ne dérogent pas à la règle. L’essentiel est de définir – avant d’utiliser une grammaire – précisément le sens des différents opérateurs utilisés. Il me semble qu’il n’y a aucun besoin de rajouter de nouveaux opérateurs, en revanche certains n’ont pas de réelle utilité, tel que le point virgule (;) qui indique la fin de la définition d’un symbole :

expression = number operator number;

ou bien l’opérateur de concaténation (une virgule ,)

expression = number, operator, number
Notation Description Exemple
= définition d’un symbole expression = number operator number
| choix sign = '+' | '-' | ''
[ ... ] option float = [number] [dot] [number]
{ ... } répétition number = digit {digit}
( ... ) groupe expression = number (plus | minus) number
' ... ' chaîne terminale dot = '.'
" ... " chaîne terminale quote = "'"
(* ... *) commentaire (* ceci est un commentaire *)
? ... ? séquence spéciale ? Tous les caractères ASCII ?
- exception string = '"' {character - '"'} '"'

En cours de cet article et du précédent, nous avons vu comment fonctionne un analyseur syntaxique LL basé sur des événements, et nous pouvons constater qu’une fois le coeur de l’analyseur en place, adapter le code pour une nouvelle grammaire est plutôt simple.

En réalité, le plus compliqué est de créer la grammaire. Cette complexité peut être amoindrie en utilisant un cycle incrémental :

  • ajout d’éléments à une grammaire
  • implémentation des nouveaux éléments
  • création des tests unitaires

Néanmoins, un cas peut poser problème. Si nous souhaitons prendre en compte les retours à la ligne comme en YAML ou Python, il sera nécessaire de connaître l’indentation, par exemple dans le tokenizer, ce qui permet de savoir dans quel bloc on se trouve. Et il faudra aussi prendre en compte les différents types d’indentation. Est-ce qu’une tabulation est identique à plusieurs espaces et si oui, combien ?

Pour conclure, notons qu’avec Java 8 et les lambdas, l’interface Production est une parfaite candidate pour devenir une interface fonctionnelle, c’est-à-dire une interface n’ayant qu’une méthode abstraite n’étant pas héritée de la classe java.lang.Object.

What’s next

Après deux articles dédiés à la création d’un analyseur syntaxique, nous allons pouvoir finaliser notre calculatrice, qui n’est rien de plus qu’une forme d’interpréteur.