Tutoriel sur la compréhension de la machine virtuelle Java

Partons de l'opération ci-dessous :

2+5

En utilisant le format EBNF nous pouvons la traduire de la manière suivante :

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

expression, operator et digit sont des symboles. expression est un symbole non terminal puisque contenant d'autres symboles. Étant le point d'entrée de la grammaire, il est le symbole de début. operator et digit sont des symboles terminaux puisque contenant des caractères entre apostrophes (') - du texte. Le caractère pipe (|) signifie ou.

Pour utiliser notre grammaire dans un analyseur, il est nécessaire d'attribuer un symbole pour chaque élément de texte et de ne pas les mixer avec d'autres symboles non terminaux (on parle de symboles atomiques) par exemple :

expression = digit '+' digit

En français on obtient : une expression est égale au chiffre un ou deux ou trois … ou huit ou neuf, plus, le chiffre un ou deux ou trois … ou huit ou neuf.

Pour éviter de passer trop de temps sur la théorie, nous allons tout de suite passer à la pratique.

En suivant le principe du TDD, nous souhaitons valider notre analyseur par le test suivant :

@Test
public void parse0() {
  final String string = "2+5";
  final InputStream inputStream = new ByteArrayInputStream(string.getBytes());
  final MathParser parser = new MathParser(inputStream);
  final String[] tokens = parser.parse();
 
  Assert.assertArrayEquals(new String[] { "2", "+", "5" }, tokens);
}

Source

Le premier composant d'un analyseur syntaxique est un lecteur (reader). Le but d'un lecteur est de lire une chaîne de caractères (dans un fichier, une String, etc.) caractère par caractère, par exemple 2+5.

Nous souhaitons aussi avoir de la flexibilité en pouvant relire le caractère précédent - unread() - ou le dixième précédent - unread(int chars) -. Mais aussi pouvoir marquer une position - mark() - pour y revenir ultérieurement sans avoir à compter les caractères lus - reset(). Et pour finir, un bon analyseur est un analyseur ayant des messages d'erreur clairs indiquant la ligne - getLine() - et la colonne - getColumn() - à laquelle l'erreur se trouve.

public interface Reader {
  int read();
  int unread();
  void unread(int chars);
  void mark();
  void reset();
  int getLine();
  int getColumn();
}

Source

La première chose marquante est que les méthodes read() et unread() retournent des entiers et non des caractères. En Java, le type char est en réalité un entier non signé de 16 bits représentant le point de code d'un caractère dans une table de codage. Or comme nous l'avons vu, la JVM manipule par défaut des int. Utiliser des types de taille inférieure, sans une bonne raison (par exemple la lecture d'un fichier sous forme de bytes ou comme nous le verrons la création d'un fichier .class) n'est d'aucune utilité. De plus, pour manipuler des tables de codage telles que l'Unicode, il est nécessaire d'utiliser des types ayant une taille de 32 bits.

Nous ne nous attarderons pas sur l'implémentation de la classe InputStreamReader, ni les tests unitaires associés (InputStreamReaderTest). La seule particularité vient du fait que chaque élément (de type int) de l'InputStream - passé en paramètre du constructeur de la classe InputStreamReader - est ajouté à un tableau de int lors de l'initialisation de la classe à l'aide de la méthode init(). De plus, pour éviter d'avoir à traiter plusieurs types de retour à la ligne, le caractère CR (0x0d) et le groupe CRLF (0x0d et 0x0a) sont remplacés par le caractère unique LF (0x0a).

Mais ce n'est qu'une possibilité. L'architecture de l'analyseur a été conçue de manière à ce que l'on puisse changer les différentes classes d'implémentation très simplement pour essayer d'autres solutions.

Notons que l'interface Reader n'a rien à voir avec la classe abstraite java.io.Reader. Tout comme la classe InputStreamReader et java.io.InputStreamReader.

Un Tokenizer s'appuie sur un Reader pour extraire les symboles terminaux (comme digit et operator).

La classe abstraite TokenizerReadernull fait le lien avec un Reader et un nom de fichier pouvant être null. Dans le cas où plusieurs fichiers sont analysés et qu'une erreur est constatée, nous souhaitons savoir duquel elle provient :

final private String filename;
final private Reader reader;
 
public Tokenizer(final String filename, final Reader reader) {
  this.reader = reader;
  this.filename = filename;
}

Elle possède des méthodes évitant à l'implémentation de faire appel directement au Reader :

protected int next() {
    return this.reader.read();
}
 
protected int rewind() {
    return this.reader.unread();
}
 
protected void mark() {
    this.reader.mark();
}
 
protected void reset() {
    this.reader.reset();
}
 
protected int peek() {
    int character = this.next();
    this.rewind();
    return character;
}

Et permet d'identifier la fin d'un flux (nommé par convention fin de fichier) :

public void checkEndOfFile() {
    int character = this.next();
 
    if (character != Ascii.EOF) {
        throw new ParserException("Expected: End of file.");
    }
}

La classe Tokenizer possède aussi des méthodes standards :

• consumeUnprintables() : consomme les caractères entre NULL (0x00) et SPACE (0x20) ;
• isDigit(int character) : le caractère en paramètre est-il un chiffre ?
• isAsciiLetter(int character) : le caractère en paramètre est-il une lettre ASCII ([0x41 ; 0x5a] U [0x61 ; 0x7a]) ?

Et pour finir une classe interne nommée ParserException qui standardise les messages d'erreur.

Il nous suffit donc d'hériter de la classe Tokenizer pour avoir toutes les méthodes utilitaires, ainsi que la classe d'exception.

La classe MathTokenizer sera utilisée pour extraire les symboles terminaux d'expressions de type 2+5.

public class MathTokenizer extends Tokenizer {
 
  public MathTokenizer(String filename, Reader reader) {
    super(filename, reader);
  }
 
  public int getDigit() {
    int character = this.next();
 
    if (isDigit(character)) {
      return character;
    } else {
      throw new ParserException("Expected: Digit [0-9].");
    }
  }
 
  public int getOperator() {
    int character = this.next();
 
    if (character == Ascii.PLUS_SIGN) {
      return character;
    } else {
      throw new ParserException("Expected: '+'");
    }
  }
}

Source

Les méthodes getDigit() et getOperator() seront appelées lorsque l'on s'attendra à lire un chiffre ou un opérateur dans la chaîne de caractères analysée. Si le symbole attendu n'est pas obtenu, une exception (de type ParserException) sera levée indiquant une erreur dans la syntaxe de l'expression.

L'interface ASCII contient tous les caractères ASCII - ayant du sens aujourd'hui - sous la forme de constantes (les noms utilisés sont les noms plus ou moins officiels).

En partant du test vu précédemment, nous pouvons résumer le fonctionnement de notre analyseur syntaxique de la manière suivante : à partir d'une chaîne de caractères représentant une expression (2+5 pour garder notre exemple), notre analyseur produit un tableau d'objets de type String (contenant les différents tokens extraits de la chaîne de caractères lors de l'analyse - {« 2 », « + », « 5 »}), en s'appuyant sur un tokenizer possédant des méthodes permettant d'extraire les symboles terminaux, lui-même s'appuyant sur un lecteur permettant de lire une chaîne de caractères, caractère par caractère.

Un élément important à noter est que l'analyseur syntaxique génère un événement à chaque fois qu'il rencontre un symbole terminal. Cet événement sera ensuite utilisé par une méthode parse() pouvant être décrite de la manière suivante :

Tant que l'expression n'est pas complètement lue (boucle)
1. récupérer l'événement suivant
2. pour l'événement X, appeler la méthode getX() du tokenizer (qui retourne un token)
3. ajouter le token au tableau de tokens
Retourner le tableau de tokens

VIII-A-4-a. Eventtype▲

public enum EventType {
  DIGIT,
  OPERATOR;
}

VIII-A-4-b. Symbols▲

public class Symbols {
  final public static int EXPRESSION = 0;
  final public static int DIGIT = 1;
  final public static int OPERATOR = 2;
}

VIII-A-4-c. Production▲

VIII-A-4-d. Table de productions▲

protected void initProductionTable() {
  this.table[EXPRESSION] = new Productions.Expression();
  this.table[DIGIT] = new Productions.Digit();
  this.table[OPERATOR] = new Productions.Operator();
}

public interface Production<E, T extends Tokenizer> {
  E produce(T tokenizer,
            Production<E, T>[] table,
            Stack<Production<E, T>> productionStack);
}

VIII-A-4-e. Pile de productions▲

VIII-A-4-f. Next Event▲

Tant que la pile n'est pas vide (boucle)
1. dépiler une production
2. appeler la méthode produce()
Si l'événement n'est pas nul
  On le retourne à la méthode parse(), qui déclenche
  la lecture de caractères dans la chaîne en cours d'analyse
Sinon d'autres productions ont été empilées
On poursuit la boucle
Lorsque la pile est vide, cela signifie qu'il n'y a plus rien à lire.
Nous retournons par conséquent null à la méthode parse()

protected E getNextEvent() {
  while (!this.productionStack.isEmpty()) {
    // Récupère la production au sommet de la pile
    final Production production = this.productionStack.pop();
 
    // Appelle la méthode produce() de la production récupérée
    final E event = production.produce(this.tokenizer,
                                       this.table,
                                       this.productionStack);
 
    // Si la production retourne non null
    // (production représentant un symbole terminal)
    // on retourne l'événement
    if (event != null) {
        return event;
    }
  }
 
  return null;
}