IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

Tutoriel sur la compréhension de la machine virtuelle Java

Image non disponible


précédentsommairesuivant

VIII. Mon premier analyseur syntaxique

Pour pouvoir transformer un fichier .pjb en bytecode, il est tout d'abord nécessaire de décomposer la source en objets manipulables en Java (ou tout autre langage). Dans cette partie et les deux suivantes, nous allons partir d'un exemple un peu plus simple permettant de décrire les concepts rudimentaires d'un analyseur syntaxique (parser) et d'un interpréteur. Il s'agira des premiers analyseur et interpréteur de cette série qui à la fin en comptera plusieurs.

L'objectif n'étant pas d'être exhaustif, nous verrons un seul type d'analyseur - un analyseur LL, qui analyse une chaîne de caractères de gauche à droite (Left to right) et construit un arbre syntaxique en commençant par l'élément racine (Leftmost derivation) - que nous allons créer manuellement.

Nous allons donc créer une pseudocalculatrice permettant de résoudre des opérations de ce type :

 
Sélectionnez
1.57 + 17) / 15) + 10 * -7 - -8

Le code est disponible sur Github (tag et branche)

VIII-A. Grammaire

Comme pour les langues naturelles, les langages informatiques et les opérations arithmétiques ont besoin d'une grammaire permettant de définir des règles syntaxiques. Ici le sens est sans importance, ce qui compte est de pouvoir extraire des mots (nommés symboles terminaux).

Pour définir une syntaxe, nous pouvons utiliser une spécification informelle en français (ou toute autre langue) ou une spécification formelle dans un format standardisé. La spécification informelle a un problème de taille, elle est libre d'interprétation, et généralement ce n'est pas ce que l'on souhaite. Il est par conséquent nécessaire d'avoir une spécification ne laissant aucune place à l'interprétation. Néanmoins, il est possible - et c'est généralement le cas - de décrire une spécification formelle à l'aide d'un langage naturel, comme c'est le cas de la JLS (Java Language Specification).

Nous allons opter pour une spécification formelle en utilisant un métalangage nommé EBNF (Extended Backus-Naur Form) qui est extrêmement simple à comprendre.

VIII-A-1. Décomposer une addition

Partons de l'opération ci-dessous :

 
Sélectionnez
2+5

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

 
Sélectionnez
1.
2.
3.
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 :

 
Sélectionnez
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 :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
@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

VIII-A-2. Reader

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.

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
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.

VIII-A-3. Tokenizer

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 :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
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 :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
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) :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
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.

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
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).

VIII-A-4. Esquisse du fonctionnement de l'analyseur

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 :

 
Sélectionnez
1.
2.
3.
4.
5.
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

À chaque symbole terminal de notre grammaire correspond un événement :

 
Sélectionnez
1.
2.
3.
4.
public enum EventType {
  DIGIT,
  OPERATOR;
}
VIII-A-4-b. Symbols

À chaque symbole (terminal et non terminal) de notre grammaire correspond une constante numérique du même nom :

 
Sélectionnez
1.
2.
3.
4.
5.
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

À chaque symbole de notre grammaire correspond ce que l'on appelle une production. Une production est modélisée par un objet Java (que nous verrons plus loin) contenant une seule méthode nommée produce() et retournant un événement de type EventType.

Si une production correspond à un symbole terminal, la méthode produce() retourne l'événement correspondant. Et si une production correspond à un symbole non terminal, elle retourne null.

  • La production Digit retourne EventType.DIGIT.
  • La production Operator retourne EventType.OPERATOR.
  • La production Expression retourne null.
VIII-A-4-d. Table de productions

L'ensemble des symboles de la grammaire est contenu dans un tableau, appelé table de productions. Les trois symboles que nous avons définis précédemment constituent les trois index du tableau. Et à ces index sont associées les productions correspondantes.

 
Sélectionnez
1.
2.
3.
4.
5.
protected void initProductionTable() {
  this.table[EXPRESSION] = new Productions.Expression();
  this.table[DIGIT] = new Productions.Digit();
  this.table[OPERATOR] = new Productions.Operator();
}

La table de productions est propre au tokenizer et ne varie pas au cours de l'exécution.

Les classes Expression, Digit et Operator implémentent l'interface Production :

 
Sélectionnez
1.
2.
3.
4.
5.
public interface Production<E, T extends Tokenizer> {
  E produce(T tokenizer,
            Production<E, T>[] table,
            Stack<Production<E, T>> productionStack);
}

Source

E est un type d'événement et T un tokenizer. En ce qui concerne les paramètres de la méthode produce() :

  • tokenizer permet de vérifier les caractères suivants sans les consommer (nous verrons ceci plus en détail dans la partie suivante, puisque nous ne l'utiliserons pas dans celui-ci) ;
  • table est la table de productions. Ce paramètre est utile pour les productions empilant des productions ;
  • productionStack est la pile sur laquelle seront empilées les productions.
VIII-A-4-e. Pile de productions

À présent, voyons comment, à l'aide de tous les éléments que nous venons de voir, nous pouvons récupérer un événement.

Le cœur de notre analyseur est basé sur une pile. Cette pile contient les productions attendues, ou en d'autres termes les symboles attendus. En reprenant notre exemple, le symbole de début expression correspond à ce que l'on souhaite analyser. Ce symbole est constitué de trois symboles correspondant aux symboles attendus. Nous savons que lorsque nous analysons une expression, nous souhaitons rencontrer un chiffre, puis un opérateur et un autre chiffre.

La pile contenant les productions est nommée simplement pile de productions.

À l'initialisation de l'analyseur, la pile de productions contient uniquement la production représentant le symbole de début : Expression, puisque notre analyseur cherche à analyser une expression. C'est à partir de cette production que notre analyse débute.

L'invocation de la méthode produce() d'une production représentant un symbole non terminal (tel que expression) provoque l'empilement - dans la pile de productions - des productions le définissant (c'est-à-dire pour le symbole expression : Digit, Operator et Digit) et retourne null.

Lors de l'analyse de notre expression d'exemple 2+5 les changements d'état de la pile de productions peuvent être décrits de la manière suivante :

  1. L'élément au sommet de la pile de productions (Expression) est dépilé. La méthode produce() de la production est appelée :

    1. la production Expression représentant un symbole non terminal, les productions Digit, Operator et Digit sont empilées sur la pile de productions. À présent la pile de productions contient les productions suivantes Digit, Operator et Digit,
    2. La méthode produce() retourne null ;
  2. L'élément au sommet de la pile de productions (Digit) est dépilé. La méthode produce() de la production est appelée et retourne l'événement EventType.DIGIT;
  3. L'élément au sommet de la pile de productions (Operator) est dépilé. La méthode produce() de la production est appelée et retourne l'événement EventType.OPERATOR ;
  4. L'élément au sommet de la pile de productions (Digit) est dépilé. La méthode produce() de la production est appelée et retourne l'événement EventType.DIGIT;
  5. La pile est vide, nous n'attendons plus aucun caractère, l'analyse syntaxique est dont terminée.

Empiler des productions implique qu'au moment de l'exécution de la méthode produce() aucun token n'est à récupérer par la méthode parse() et donc nous retournons null, ce qui signifie qu'aucun caractère ne sera lu.

VIII-A-4-f. Next Event

Finalement, notre analyseur syntaxique dépend principalement d'une méthode dépilant des productions et les exécutant.

Nous pouvons décrire la méthode getNextEvent() de la manière suivante :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
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()

La méthode produce() effectue l'une des deux actions décrites précédemment :

  • retourner un événement ou
  • empiler des productions dans la pile.

Voyons à présent l'implémentation de la méthode getNextEvent() :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
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;
}

Source

Pour conclure cette présentation de notre analyseur, notons que seulement deux éléments sont variables au cours de son exécution :

  • la pile de productions et
  • le tableau de tokens retourné par la méthode parse().

VIII-B. Parser

Ce qui nous intéresse dans cette partie est le mécanisme de décomposition analytique. Le principe d'un analyseur LL, nommé aussi analyseur descendant, est de lire chaque caractère de gauche à droite en revenant parfois en arrière sur des caractères déjà analysés, et de savoir plus ou moins à l'avance les symboles qu'il doit rencontrer. En d'autres termes, pour notre grammaire, nous savons que nous devons appeler dans l'ordre les méthodes getDigit(), getOperator() et une deuxième fois getDigit().

Néanmoins, pour que notre analyseur soit évolutif et facilement testable, nous utilisons une table de productions (aussi nommée table d'analyse).

Comme mentionné précédemment, chaque entrée de la table de productions est un symbole de la grammaire, auquel nous faisons aussi référence par le terme de production.

À la table de productions est associée une pile de productions à venir (champ d'instance nommé productionStack) dont les éléments sont dépilés dans la méthode nommée getNextEvent() et empilés dans les méthodes produce() des productions représentant des symboles non terminaux :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
// A est l'objet racine que crée l'analyseur
// E est un type d'événement
// T est un tokenizer
public abstract class Parser<A, E, T extends Tokenizer> {
  final public T tokenizer;
  final public Production<E, T>[] table;
  final public Stack<Production<E, T>> productionStack;
 
  public Parser(final InputStream inputStream, final int productionSize) {
    this(null, inputStream, productionSize);
  }
 
  public Parser(final String filename,          // Nom du fichier analysé
                final InputStream inputStream,  // Flux analysé
                final int productionSize) {     // Nombre de symboles
                                                // dans la table de productions
    this.tokenizer = this.newTokenizer(filename, inputStream);
    this.table = new Production[productionSize];
    this.productionStack = new Stack<>();
 
    this.initProductionTable();
    // this.table[0] correspond au symbole de début "expression"
    this.productionStack.push(this.table[0]);
  }
 
  // ...
 
  protected abstract void initProductionTable();
}

Source

Voyons à présent les implémentations :

 
Sélectionnez
public class Productions {
  // expression = digit operator digit
  public static class Expression implements Production<EventType, MathTokenizer> {
    public EventType produce(MathTokenizer tokenizer,
                             Production<EventType, MathTokenizer>[] table,
                             Stack<Production<EventType, MathTokenizer>>
                                                            productionStack) {
      productionStack.push(table[Symbols.DIGIT]);
      productionStack.push(table[Symbols.OPERATOR]);
      productionStack.push(table[Symbols.DIGIT]);
 
      return null;
    }
  }
 
  // digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
  public static class Digit implements Production<EventType, MathTokenizer> {
    public EventType produce(MathTokenizer tokenizer,
                             Production<EventType, MathTokenizer>[] table,
                             Stack<Production<EventType, MathTokenizer>>
                                                            productionStack) {
      return EventType.DIGIT;
    }
  }
 
  // operator = '+'
  public static class Operator implements Production<EventType, MathTokenizer> {
    public EventType produce(MathTokenizer tokenizer,
                             Production<EventType, MathTokenizer>[] table,
                             Stack<Production<EventType, MathTokenizer>>
                                                            productionStack) {
      return EventType.OPERATOR;
    }
  }
}

Source

Dans le cas présent, nous avons une production par symbole. La production représentant le symbole non terminal expression ajoute bien les autres productions - comme défini dans la grammaire - dans la pile et les productions représentant les symboles terminaux digit et operator retourne l'événement associé.

Pour finir, nous devons voir comment est appelée la méthode getNextEvent(), qui comme nous l'avons déjà vu, appelle la méthode produce(), le cœur de notre analyseur :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
public class MathParser extends Parser<String[], EventType, MathTokenizer> {
  final private LinkedList<Object> postfixExpression;
  final private Stack operatorStack;
 
  public MathParser(final InputStream inputStream) {
    super(inputStream, Symbols.number());
 
    this.postfixExpression = new LinkedList<>();
    this.operatorStack = new Stack<>();
  }
 
  public String[] parse() {
    EventType eventType = null;
 
    boolean done = false;
    while (!done) { // Nous verrons plus loin comment done devient true
      eventType = this.getNextEvent();
 
      switch (eventType) {
        case DIGIT:
          this.tokens[counter++] =
              String.valueOf(Character.toChars(this.tokenizer.getDigit()));
          break;
        case OPERATOR:
          this.tokens[counter++] =
              String.valueOf(Character.toChars(this.tokenizer.getOperator()));
          break;
        default:
          System.err.println("Unexpected event.");
          break;
      }
    }
 
    return this.tokens;
  }
 
  protected void initProductionTable() {
    this.table[EXPRESSION] = new Productions.Expression();
    this.table[DIGIT] = new Productions.Digit();
    this.table[OPERATOR] = new Productions.Operator();
  }
 
  // ...
}

En reprenant le test unitaire défini au début de cette partie :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
@Test
public void parse() {
  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);
}

La méthode parse() est la méthode faisant/délégant l'action de décomposition analytique. Comme défini dans notre test, elle retourne bien un tableau de String. La méthode parse() récupère des événements en appelant la méthode getNextEvent(), effectue une validation syntaxique en appelant les méthodes getDigit() et getOperator() du tokenizer qui lèvent une exception si la syntaxe est incorrecte et retourne un tableau contenant des tokens sous la forme de chaînes de caractères.

VIII-C. End of file

Nos avons donc presque fini. Il ne reste qu'une interrogation! Quand se termine la boucle de la méthode parse() ?

 
Sélectionnez
while(!done) {
    // ...
}

Il nous faut une solution pour que la variable done passe un jour à true. Or avec notre table de production actuelle, nous allons appeler indéfiniment la méthode getNextEvent() qui après un certain temps (à partir du quatrième appel) retournera toujours null.

La solution la plus simple est de rajouter un niveau à notre grammaire :

 
Sélectionnez
1.
2.
3.
stream = expression eof
// ...
eof = ? fin du flux ?

EBNF : les points d'interrogation permettent de définir dans une langue naturelle un symbole terminal dont l'implémentation n'a pas d'importance, ou dont une simple phrase résume le besoin, exemple : ? tous les caractères UTF-8 ?.

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
public class Productions {
  // stream = expression eof
  public static class Stream implements Production<EventType, MathTokenizer> {
    public EventType produce(MathTokenizer tokenizer,
                             Production<EventType, MathTokenizer>[] table,
                             Stack<Production<EventType, MathTokenizer>>
                                                            productionStack) {
      productionStack.push(table[Symbols.EOF]);
      productionStack.push(table[Symbols.EXPRESSION]);
 
      return null;
    }
  }
 
  // ...
 
  // eof = ? fin du flux ?
  public static class EndOfFile implements Production<EventType, MathTokenizer> {
    public EventType produce(MathTokenizer tokenizer,
                             Production<EventType, MathTokenizer>[] table,
                             Stack<Production<EventType, MathTokenizer>>
                                                            productionStack) {
      return EventType.EOF;
    }
  }
}

Source

 
Sélectionnez
1.
2.
3.
4.
5.
public enum EventType {
  EOF,
  DIGIT,
  OPERATOR;
}

Source

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
public class Symbols {
  final public static int STREAM = 0;
  final public static int EOF = 1;
  final public static int EXPRESSION = 2;
  final public static int DIGIT = 3;
  final public static int OPERATOR = 4;
}

Source

Note : le lien ci-dessus pointe vers une classe Symbols légèrement différente. Pour éviter d'avoir à changer la valeur des constantes de classe (EXPRESSION, DIGIT, etc.) à chaque modification de notre grammaire, elles sont initialisées au chargement de la classe. Une fois que l'écriture de l'analyseur sera terminée, nous pourrons les fixer.

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
public class MathParser extends Parser<String[], EventType, MathTokenizer> {
 
  // ...
 
  protected void initProductionTable() {
    this.table[STREAM] = new Productions.Stream();
    this.table[EOF] = new Productions.EndOfFile();
    this.table[EXPRESSION] = new Productions.Expression();
    this.table[DIGIT] = new Productions.Digit();
    this.table[OPERATOR] = new Productions.Operator();
  }
}

Source

Vous constaterez que rajouter un élément à notre grammaire n'impacte que très légèrement notre code. De plus, étant donné que l'on utilise une pile, dans les méthodes produce() les productions sont insérées dans l'ordre inverse de leur définition dans la grammaire :

 
Sélectionnez
stream = expression eof

donne :

 
Sélectionnez
1.
2.
productionStack.push(table[EOF]);
productionStack.push(table[EXPRESSION]);

Nous pouvons donc terminer l'implémentation de la méthode parse() :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
@Override
public String[] parse() {
  EventType eventType = null;
 
  boolean done = false;
  while (!done) {
    eventType = this.getNextEvent();
 
    switch (eventType) {
      case DIGIT:
        this.tokens[counter++] =
            String.valueOf(Character.toChars(this.tokenizer.getDigit()));
        break;
      case OPERATOR:
        this.tokens[counter++] =
            String.valueOf(Character.toChars(this.tokenizer.getOperator()));
        break;
      case EOF:
        this.tokenizer.checkEndOfFile();
        done = true;
        break;
      default:
        System.err.println("Unexpected event.");
        break;
    }
  }
 
  return this.tokens;
}

Source

Pour exécuter le test unitaire (à la racine du projet mathparser) :

 
Sélectionnez
1.
2.
$ ant
$ ant test -DtestClass=org.isk.jvmhardcore.mathparser.MathParserTest -DtestMethod=parse0

VIII-D. What's next ?

Dans cette partie nous avons vu le cœur d'un analyseur syntaxique. Nous allons pouvoir dès la semaine prochaine enrichir notre grammaire en explorant le reste de la syntaxe EBNF. Et pour finir, au lieu de retourner un tableau de chaînes de caractères, la méthode parse() retournera un type d'objet plus adapté à la résolution de notre expression arithmétique.


précédentsommairesuivant

Copyright © 2016 SOAT. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.