Chacun des tokens est inséré dans une liste selon l'ordre dans lequel il a été analysé. Voyons par exemple l'analyse syntaxique de l'expression suivante :

3 + 4 * 7

Elle a pour résultat la liste suivante (l'élément le plus à gauche étant le premier élément de la liste) :

3, +, 4, *, 7

La notation d'une telle expression est dite infixée, c'est-à-dire que les opérateurs sont placés entre les opérandes utilisés pour effectuer l'opération. Il s'agit de la notation qui nous est la plus familière. Mais ce n'est pas la seule permettant de représenter une expression arithmétique.

La notation préfixée place les opérateurs avant les opérandes utilisés pour effectuer l'opération. Si l'on transforme l'expression infixée précédente nous obtenons l'expression suivante :

+ 3 * 4 7

Le Lisp et les langages qui en sont inspirés, tels que Scheme, utilisent une pseudo notation préfixée. Dans ce cas, on parle de pseudo notation préfixée, puisque pour ces langages, un opérateur est une fonction d'arité indéfinie (c'est-à-dire acceptant un nombre variable de paramètres) alors qu'en arithmétique, quelle que soit la notation, un opérateur n'opère que sur deux opérandes.

La dernière notation que nous allons voir est la notation postfixée. Elle place les opérateurs après les opérandes sur lesquels l'opération est effectuée.

3 4 7 * +

Chaque opérande pouvant être une expression :

1 2 + 3 4 + *
(1 2 +) (3 4 +) *

Les expressions préfixées et postfixées sont non ambiguës : avec ou sans les parenthèses l'interprétation est la même contrairement à une expression infixée, pour laquelle la priorité des opérateurs * et / sur les opérateurs + et - a un impact sur la résolution de l'expression :

(1 + 2) * (3 + 4)

est différent de :

1 + 2 * 3 + 4

La notation postfixée est utilisée par tous les langages basés sur une pile, tels que le Forth, le PostScript, ou - ce qui nous intéresse - le Java.

L'algorithme permettant d'évaluer une expression postfixée en utilisant une pile de nombres est le suivant :

• lire l'expression de gauche à droite, un nombre ou un opérateur à la fois ;

  • lorsque l'on rencontre un nombre, on l'empile ;

  • lorsque l'on rencontre un opérateur :

    • on dépile deux nombres du sommet de la pile,
    • on effectue l'opération (en se rappelant que le premier élément dépilé est le second opérande),
    • on empile le résultat pour qu'il soit utilisé par l'opération suivante.

Si l'expression est correcte, le résultat est le dernier élément présent dans la pile.

Voyons un exemple. Pour l'expression postfixée ci-dessous :

2 7 5 - * 8 5 - *

Le calcul est le suivant (l'élément le plus à droite est le sommet de la pile) :

Caractère lu : état de la pile avant -> après
 
2 : [vide] -> 2
7 : 2 -> 2, 7
5 : 2, 7 ->  2, 7, 5
- : 2, 7, 5 - > 2, 2 (7 - 5 = 2)
* : 2, 2 -> 4 (2 * 2 = 4)
8 : 4 -> 4, 8
5 : 4, 8 -> 4, 8, 5
- : 4, 8, 5 -> 4, 3 (8 - 5 = 3)
* : 4, 3 -> 12 (4 * 3 = 12)

Nous pouvons constater simplement que la JVM résout des expressions postfixées en reprenant l'expression précédente :

.class org/isk/jvmhardcore/bytecode/partnine/Postfix
  .method compute()I
    iconst_2
    bipush 7
    iconst_5
    isub
    imul
    bipush 8
    iconst_5
    isub
    imul
    ireturn
  .methodend
.classend

Source

Le test unitaire nous confirme le résultat que nous avions obtenu en effectuant le calcul à la main :

@Test
public void compute() {
  final int result = Postfix.compute();
  Assert.assertEquals(12, result);
}

Source

Voyons à présent comment résoudre une expression postfixée en Java, à partir d'une liste de type java.util.LinkedList contenant des nombres de type java.lang.Number (la superclasse des classes Integer et Double) et des opérateurs de type org.isk.jvmhardcore.math.common.Operator :

public enum Operator {
  PLUS, MINUS, TIMES, DIVIDE;
}

Nous allons donc implémenter une méthode prenant en argument une LinkedList représentant une expression postfixée et retournant une valeur de type java.lang.Integer ou java.lang.Double en fonction du type des opérandes de l'expression.

public <T>T resolve(LinkedList<Object> postfixExpression) {
 
}

Utiliser un type de retour générique (<T>T) nous permet d'éviter de convertir la valeur en Integer ou en Double.

Si l'on reprend l'algorithme, nous avons besoin d'une pile contenant les nombres.

public class MathSolver {
  private final Stack<Number> processingStack;
 
  public MathSolver() {
    this.processingStack = new Stack<>();
  }
}

L'implémentation de la méthode resolve() est triviale, puisque nous itérons sur les éléments de la liste. Si l'élément est de type Operator nous effectuons un calcul, sinon nous l'empilons. Et pour finir, nous dépilons le dernier élément de la pile (le résultat) pour le retourner.

public <T> T resolve(LinkedList<Object> postfixExpression) {
  this.processingStack.clear();
 
  for (Object object : postfixExpression) {
    if (object instanceof Operator) {
      this.compute((Operator) object);
    } else {
      this.processingStack.push((Number) object);
    }
  }
 
  return (T) this.processingStack.pop();
}

La méthode compute(), quant à elle, dépile deux éléments du sommet de la pile et effectue l'opération en fonction de l'opérateur.

private void compute(Operator operator) {
  final Number right = this.processingStack.pop();
  final Number left = this.processingStack.pop();
 
  switch (operator) {
    case PLUS:
      this.add(left, right);
      break;
 
    // case pour chaque opérateur
  }
}

Les trois autres opérateurs fonctionnent sur le même principe.

Les méthodes add(), subtract() et multiply() sont construites sur le même principe :

• nous vérifions le type des opérandes (comme nous l'avons vu dans la partie Mathématiques et Conversions, en Java les opérateurs arithmétiques prennent deux opérandes du même type, en raison du comportement identique des instructions associées) ;
• nous effectuons l'opération ;
• et nous ajoutons le résultat à la pile de nombres (sous la forme d'un Number).

Pour l'exemple, le choix a été fait de distinguer deux types de nombres (Integer et Double), à l'instar de l'analyseur syntaxique. Bien évidemment dans un cas réel, le choix devrait être fait en fonction du besoin.

L'addition, la soustraction et la multiplication retournent une valeur de type Integer si les deux opérandes sont des entiers, sinon une valeur de type Double. La division retourne une valeur de type Integer uniquement si le reste de la division des deux entiers est égal à zéro. Dans tous les autres cas, elle retourne une valeur de type Double.

private void add(Number left, Number right) {
  Number n = null;
 
  if (left instanceof Integer && right instanceof Integer) {
    n = left.intValue() + right.intValue();
  } else {
    n = left.doubleValue() + right.doubleValue();
  }
 
  this.processingStack.push(n);
}

Ceci fonctionne puisque le résultat d'une addition, d'une soustraction et d'une multiplication est du même type que ses opérandes. En revanche, pour la division ce n'est pas le cas. Si l'on divise deux entiers comme 5 et 2, le résultat (sans perte d'information) sera un nombre à virgule, alors que 4 divisé par 2 aura pour résultat 2. Bien qu'en mathématique 2 soit égal à 2,0, en informatique ce n'est pas le cas puisque, comme nous l'avons déjà vu, un entier n'est pas représenté en mémoire de la même manière qu'un nombre à virgule. Encore une fois, le besoin sera déterminant dans le choix de l'implémentation de la méthode divide().

private void divide(Number left, Number right) {
  Number n = null;
 
  if (left instanceof Integer && right instanceof Integer
      && (left.intValue() % right.intValue()) == 0) {
    n = left.intValue() / right.intValue();
  } else {
    n = left.doubleValue() / right.doubleValue();
  }
 
  this.processingStack.push(n);
}

Source

Nous pouvons ensuite effectuer quelques tests unitaires :

public class MathSolverTest {
  private static MathSolver SOLVER;
 
  @BeforeClass
  public static void init() {
    SOLVER = new MathSolver();
  }
 
  private LinkedList<Object> postfixExpression(final Object ... objects) {
    final LinkedList<Object> list = new LinkedList<>();
 
    for (Object o : objects) {
      list.add(o);
    }
 
    return list;
  }
 
  private void test(final LinkedList<Object> postfixExpression,
                    final int expectedResult) {
    final int result = SOLVER.resolve(postfixExpression);
    Assert.assertEquals(expectedResult, result);
  }
 
  private void test(final LinkedList<Object> postfixExpression,
                    final double expectedResult) {
    final double result = SOLVER.resolve(postfixExpression);
    Assert.assertEquals(expectedResult, result, 0.001);
  }
 
  @Test
  public void resolve21() {
    // 2 + 5 - 2
    this.test(this.postfixExpression(2, 5, Operator.PLUS, 2, Operator.MINUS), 5);
  }
 
  @Test
  public void resolve22() {
    // ((2 + 5) * 2) - 2
    this.test(
        this.postfixExpression(
            2, 5, Operator.PLUS, 2, Operator.TIMES, 2, Operator.MINUS),
        12);
  }
}

Source

Nous avons donc d'un côté un analyseur syntaxique créant une liste de chaînes de caractères représentant une expression infixée et, de l'autre, un interpréteur prenant en paramètre une liste de java.lang.Number et de org.isk.jvmhardcore.math.common.Operator représentant une expression postfixée.

Mais avant de transformer notre expression infixée en expression postfixée, nous devons :

• modifier les méthodes getInteger(), getFloat() et getOperator() de la classe MathTokenizer, pour qu'elles retournent respectivement un Integer, un Double et un ParsingOperator ;
• et supprimer la méthode getNext() retournant un caractère sous la forme d'un int, par la méthode getParenthesis() retournant un ParsingOperator.

Le type ParsingOperator nous permet de représenter les quatre opérateurs arithmétiques, mais aussi les parenthèses, sous un seul type pour que la transformation soit simplifiée.

enum ParsingOperator {
  PLUS(0),
  MINUS(0),
  TIMES(1),
  DIVIDE(1),
  LEFT_PARENTHESIS(100),
  RIGHT_PARENTHESIS(100);
}

Nous verrons dans la partie suivante la signification de ces différentes valeurs.

Cette énumération n'ayant aucun sens à l'extérieur de l'analyseur syntaxique, elle est définie dans la classe MathParser, et n'est accessible qu'à l'intérieur du package org.isk.jvmhardcore.math.parser.

Maintenant que nous avons typé tous les tokens, nous devons changer la notation utilisée pour représenter les expressions.

La première chose à prendre en compte est que la notation infixée a des règles de précédence :

• une expression entre parenthèses est prioritaire par rapport à tous les opérateurs arithmétiques ou à une expression entre parenthèses englobantes : dans l'expression 2 * ((2 + 7) - 4), l'expression (2 + 7) est prioritaire sur la soustraction, elle-même prioritaire sur la multiplication ;
• la multiplication et la division sont prioritaires par rapport à l'addition et à la soustraction.

Les expressions arithmétiques étant associatives à gauche, si deux opérateurs sont de priorité identique, l'opération la plus à gauche est effectuée en premier.

Ces règles de précédence sont représentées dans l'énumération ParsingOperator par les valeurs 0, 1 et 100. De fait, si l'on compare les opérateurs PLUS, qui a pour valeur 0, et TIMES, qui a pour valeur 1, alors PLUS < TIMES. Néanmoins, les parenthèses n'étant pas des opérateurs, elles devront être traitées d'une manière différente des opérateurs arithmétiques - comme nous allons le voir - et pour cette raison elles ont pour valeur 100.

De plus, pour pouvoir effectuer la transformation il nous faut une pile d'opérateurs et une liste contenant l'expression postfixée.

Ces quelques prérequis pris en considération, voyons l'algorithme :

• lire l'expression de gauche à droite ;

  • lorsque l'on rencontre un nombre, on l'ajoute à la liste ;
  • lorsque l'on rencontre un opérateur, s'il est de précédence inférieure à l'opérateur au sommet de la pile, on dépile l'opérateur au sommet de la pile, on l'ajoute à la liste et on empile l'opérateur rencontré ;
  • lorsque l'on rencontre une parenthèse ouvrante, on l'empile ;
  • lorsque l'on rencontre une parenthèse fermante, on dépile tous les opérateurs et on les ajoute à la liste jusqu'à ce que l'on dépile une parenthèse ouvrante. (Les parenthèses seront toutes deux ignorées puisqu'inutiles dans une expression postfixée) ;
  • lorsque l'on arrive à la fin de l'expression, on ajoute la totalité des opérateurs de la pile dans la liste, dans l'ordre de dépilage.

Commençons par un exemple simple : 3 * 2. Comme précédemment, pour la pile l'élément le plus à droite est le sommet de la pile. Pour la liste l'élément le plus à gauche est le premier élément de la liste.

Caractère lu : état de la pile avant -> après | état de la liste avant -> après
 
3: [vide] -> [vide] | [vide] -> 3
*: [vide] -> *      | 3 -> 3
2: *      -> *      | 3 -> 3, 2
fin: *    -> [vide] | 3, 2 -> 3, 2, *

Rajoutons un opérateur de priorité inférieure et un opérande : 3 * 2 + 5

Caractère lu : état de la pile avant -> après | état de la liste avant -> après
 
3: [vide] -> [vide] | [vide] -> 3
*: [vide] -> *      | 3 -> 3
2: * -> *           | 3 -> 3, 2
+: * -> +           | 3, 2 -> 3, 2, *
5: + -> +           | 3, 2, * -> 3, 2, *, 5
fin: + -> [vide]    | 3, 2, *, 5 -> 3, 2, *, 5, +

Pour terminer, voyons une expression plus complexe : (2 * (2 + 5) - (10 - 8)) + 3. Pour rester concis, hormis pour la première ligne, seul l'état de la pile « après » est indiqué (l'état « avant » étant l'état « après » de la ligne précédente).

Caractère lu : état de la pile -> après | état de la liste -> après
 
(:      [vide] -> (         | [vide] -> [vide]
2:      -> (                | [vide] -> 2
*:      -> (, *             | -> 2
(:      -> (, *, (          | -> 2
2:      -> (, *, (          | -> 2, 2
+:      -> (, *, (, +       | -> 2, 2
5:      -> (, *, (, +       | -> 2, 2, 5
):      -> (, *             | -> 2, 2, 5, +
-:      -> (, -             | -> 2, 2, 5, +, *
(:      -> (, -, (          | -> 2, 2, 5, +, *
10:     -> (, -, (          | -> 2, 2, 5, +, *, 10
-:      -> (, -, (, -       | -> 2, 2, 5, +, *, 10
8:      -> (, -, (, -       | -> 2, 2, 5, +, *, 10, 8
):      -> (, -,            | -> 2, 2, 5, +, *, 10, 8, -
):      -> [vide]           | -> 2, 2, 5, +, *, 10, 8, -, -
+:      -> +                | -> 2, 2, 5, +, *, 10, 8, -, -
3:      -> +                | -> 2, 2, 5, +, *, 10, 8, -, -, 3
fin:    -> [vide]           | -> 2, 2, 5, +, *, 10, 8, -, -, 3, +

Cet exemple peut être validé par le test unitaire suivant :

public class MathParserTest {
 
  private LinkedList<Object> expected(final Object ... objects) {
    final LinkedList<Object> list = new LinkedList<>();
 
    for (Object o : objects) {
      list.add(o);
    }
 
    return list;
  }
 
  private void test(final String expression, final LinkedList<Object> expected) {
    final InputStream inputStream =
            new ByteArrayInputStream(expression.getBytes());
    final MathParser parser = new MathParser(inputStream);
    final LinkedList<Object> tokens = parser.parse();
    Assert.assertEquals(expected, tokens);
  }
 
  @Test
  public void expressionWithParenthesis5() {
    this.test("(2 * (2 + 5) - (10 - 8)) + 3",
        this.expected(
            2, 2, 5, Operator.PLUS, Operator.TIMES,
            10, 8, Operator.MINUS, Operator.MINUS, 3, Operator.PLUS));
  }
}

Source

En l'état le test est en erreur, puisque nous n'avons pas encore effectué les modifications dans la classe MathParser.

Pour commencer, nous renommons le champ tokens de type LinkedList en postfixExpression, contenant à présent des objets de type java.lang.Object, puis nous rajoutons une pile d'opérateurs :

final private LinkedList<Object> postfixExpression;
final private Stack<ParsingOperator> operatorStack;
 
public MathParser(final InputStream inputStream) {
  super(inputStream, Symbols.number());
 
  this.postfixExpression = new LinkedList<>();
  this.operatorStack = new Stack<>();
}

Nous modifions ensuite le switch/case de la méthode parse() :

switch (eventType) {
  case FLOAT:
    this.postfixExpression.add(this.tokenizer.getFloat());
    break;
  case INTEGER:
    this.postfixExpression.add(this.tokenizer.getInteger());
    break;
  case OPERATOR:
    this.processOperator(this.tokenizer.getOperator());
    break;
  case LEFT_PARENTHESIS:
    this.operatorStack.push(this.tokenizer.getParenthesis());
    break;
  case RIGHT_PARENTHESIS:
    this.processRightParenthesis(this.tokenizer.getParenthesis());
    break;
  case EOF:
    this.tokenizer.checkEndOfFile();
    this.processEndOfFile();
    done = true;
    break;

En reprenant l'algorithme, nous ajoutons les nombres à la liste (postfixExpression) et ajoutons les parenthèses ouvrantes à la liste des opérateurs (operatorStack). Le traitement des autres événements est déporté dans des méthodes dédiées.

Commençons par la méthode processOperator().

private void processOperator(ParsingOperator parsingOperator) {
  if (!this.operatorStack.isEmpty()
    && parsingOperator.le(this.operatorStack.peek())) {
    this.postfixExpression.add(ParsingOperator.getClean(this.operatorStack.pop()));
  }
 
  this.operatorStack.push(parsingOperator);
}

Nous testons si l'opérateur au sommet de la pile est de priorité supérieure à l'opérateur courant. Si c'est le cas, il est dépilé, converti en Operator (ParsingOperator.getClean()) et ajouté à la liste. Dans tous les cas, l'opérateur courant est ajouté à la pile d'opérateurs.

La méthode le() de l'énumération ParsingOperator exclut les parenthèses des règles de précédence, puisqu'il ne s'agit pas d'un opérateur et que c'est l'ensemble de l'expression entre parenthèses qui est prioritaire.

public boolean le(ParsingOperator po) {
  return po.value != 100 && this.value <= po.value;
}

Si l'opérateur est une parenthèse ouvrante (les parenthèses fermantes n'étant jamais ajoutées à la pile d'opérateurs), elle ne doit pas être dépilée. Une expression entre parenthèses étant une sous-expression, quel que soit le premier opérateur de cette sous-expression, nous devons considérer que la pile d'opérateurs est vide.

Seul le traitement d'une parenthèse fermante (processRightParenthesis()) impliquera le dépilage d'une parenthèse ouvrante.

private void processRightParenthesis(ParsingOperator rightParenthsesis) {
  while (!this.operatorStack.isEmpty()
       && this.operatorStack.peek() != ParsingOperator.LEFT_PARENTHESIS) {
    this.postfixExpression.add(ParsingOperator.getClean(this.operatorStack.pop()));
  }
 
  if (this.operatorStack.isEmpty()
    || this.operatorStack.pop() != ParsingOperator.LEFT_PARENTHESIS) {
    throw new MathException("Missing left parenthesis.");
  }
}

Si l'on rencontre une parenthèse fermante, tous les opérateurs sont dépilés un par un, convertis en Operator et ajoutés à la liste, et ceci jusqu'à ce qu'une parenthèse ouvrante soit rencontrée (ou pour parer aux erreurs, jusqu'à ce que la pile soit vide).

Finalement, nous vérifions que la boucle s'est bien arrêtée parce qu'une parenthèse ouvrante a été rencontrée, et non parce que la pile était vide (cas d'une expression avec une parenthèse fermante sans parenthèse ouvrante).

Notez que nous dépilons la parenthèse, puisqu'elle ne nous est plus utile.

Lorsque l'analyse de l'expression est terminée, comme pour le traitement d'une parenthèse fermante, nous dépilons tous les opérateurs de la pile un par un, les convertissons en Operator et les ajoutons à la liste.

private void processEndOfFile() {
  while (!this.operatorStack.isEmpty()) {
    this.postfixExpression.add(ParsingOperator.getClean(this.operatorStack.pop()));
  }
}

Si dans la pile est présente une parenthèse ouvrante (l'expression a une parenthèse ouvrante qui n'a pas de parenthèse fermante), la méthode ParsingOperator.getClean() lève une exception.

Les deux exceptions (liées à une asymétrie entre les parenthèses ouvrantes et fermantes) levées dans la classe MathParser, n'utilisent pas l'exception ParserException, mais MathException. De ce fait, nous n'avons ni le numéro de ligne, ni le numéro de colonne. Dans le cas de l'exception levée dans la méthode processRightParenthesis() nous pourrions trouver le moyen d'utiliser l'exception ParserException, en revanche pour celle de la méthode ParsingOperator.getClean(), cela n'apporterait aucune information de plus à l'utilisateur, puisque nous devons analyser toute l'expression pour nous rendre compte qu'il manque une parenthèse fermante. Une solution serait d'associer à un token une ligne et une colonne. Néanmoins, dans le cas présent ce serait ajouter une complexité inutile.

Ceci conclut notre série consacrée aux analyseurs syntaxiques et à l'implémentation d'un interpréteur plutôt simple. Le matériel traité dans ces trois articles nous sera utile prochainement lorsque nous créerons un assembleur permettant de générer du bytecode à partir d'un fichier .pjb, et plus tard encore lorsque nous créerons des compilateurs.

Dans le chapitre suivant, nous achèverons notre excursion hors de l'univers du bytecode en nous intéressant à l'Unicode et à son intégration dans le monde Java.