Tutoriel sur la compréhension de la machine virtuelle Java

Pour rappel, dans la partie précédente 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 cette partie, 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 suivie de (* Nouveau *) et celle d'un nouveau symbole de (* Modifié *).

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

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

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

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, 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érents, nous allons renommer la production Digit (de la branche précédente) en Number, le symbole et l'événement DIGIT 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).

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 ) indiquent un groupe. Le symbole number est composé du symbole sign suivi 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 l'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();
}

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

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ères 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 productions 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 consomme 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 symbole 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();
}

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 un 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;
}

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 la partie suivante.

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

• ajout des symboles OR_LEFT_PARENTHESIS, OR_RIGHT_PARENTHESIS, LEFT_PARENTHESIS et RIGHT_PARENTHESIS ;
• ajout des événements LEFT_PARENTHESIS et RIGHT_PARENTHESIS ;
• ajout des méthodes getNext(), isLeftParenthesis() et isRightParenthesis() dans la classe MathTokenizer ;
• ajout des productions OrLeftParenthesis, OrRightParenthesis, LeftParenthesis et RightParenthesis ;
• modification des productions Expression et OrRightExpression ;
• modification des méthodes parse() et initProductionTable() de la classe MathParser.

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;
}
 
// À 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

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 cette partie ainsi que la précédente 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é, tels 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

En cours de cette partie et de la précédente, nous avons vu comment fonctionne un analyseur syntaxique LL basé sur des événements, et nous pouvons constater qu'une fois le cœur 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.

Après deux parties dédiées à 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.