Journal Psychologie d'un parseur Javascript

Sommaire

• Un constat choquant
  • Pourquoi ça plante
• Un début de piste
• Comment analyse-t-on un expression Javascript ?
• Différences de comportement des moteurs Javascript
  • V8
  • SpiderMonkey
  • Rhino
  • JavascriptCore
• Dans d'autres langages
  • Java (JShell, OpenJDK)
  • C - Clang
  • C - GCC
  • C - Tiny C Compiler
• Mot de la fin

(attention : beaucoup de suppositions, peu de vérifications dans ce journal. Lisez pour le cheminement plus que pour le résultat…)

Un constat choquant

De manière tout à fait intéressante en Javascript :

++ ++ i;

Donne l'erreur suivante dans Node (V8):

SyntaxError: Invalid left-hand side expression in prefix operation`

Et, dans Firefox (SpiderMonkey):

SyntaxError: expected expression, got '++'

Alors que :

i ++ ++;

Donne l'erreur suivante dans les deux moteurs (à quelque chose près) :

SyntaxError: Unexpected token '++'

De quoi rester rêveur, vous ne trouvez pas ? L'erreur semble être symétrique, alors pourquoi donc une telle asymétrie dans les message d'erreur, une telle différence ? Abasourdissant, non ?

Pourquoi ça plante

Ah oui, au fait, présentons rapidement quelques bases de ce problème.

• ++i est une pré-incrémentation. Elle est censée prendre i, lui ajouter 1, enregistrer la valeur dans i et retourner le résultat de cette opération. --i fonctionne pareil, mais retire 1.
• ++ ++i devrait faire la même chose, puis… comme ++i n'est pas une référence, le premier ++ ne peut enregistrer son résultat nulle part. En fait, l'expression n'a pas vraiment de sens, à tel point que c'est une erreur de syntaxe.
• i++ est censé prendre i, lui ajouter 1, enregistrer la valeur dans i et retourner la valeur originale de i. i-- fait pareil mais retire 1.
• i++ ++ a à peu près le même sens que ++ ++i, c'est à dire aucun.

Donc ça plante. Mais pourquoi ça ne plante pas exactement de la même manière ?

Un début de piste

C'est certainement parce quand on analyse une expression Javascript, qu'on a besoin de pouvoir accepter plusieurs opérateurs préfixes, alors qu'on n'a pas besoin d'accepter plusieurs opérateurs suffixes.

Voyez plutôt ces expressions valides en Javascript :

+ ++i
- ++i
+ - + - i
- + - + i
+ + i
- - i
void typeof void + -- i

On peut chaîner des opérateurs préfixes à l'infini ! Alors qu'on ne peut pas en dire autant de l'opérateur suffixe.

Comment analyse-t-on un expression Javascript ?

Pour nous former une intuition pas trop pourrie de la situation, imaginons un peu comment on peut analyser une expression Javascript (ou Java, ou C, d'ailleurs, le problème est le même. Pour les gens qui ne connaissent pas ces langages, imaginez une expression arithmétique classique comme celles qu'on voit au collège, mais avec ces fameux opérateurs préfixes et suffixes).

Comment peut-on analyser une telle expression alors ? On pourrait aussi bien lire le code des différents moteurs Javascript, ou lire la doc, tant qu'à faire, Javascript étant un langage extrêmement bien spécifié avec une spécification largement exploitable. Mais déjà, lire ces codes ou même cette spec n'est pas trivial, et ensuite, pour des raisons totalement égoïstes, j'ai envie de réfléchir au problème d'analyser une expression Javascript avant de regarder les solutions existantes ou suggérées. Alors allons-y gaiement.

On a vu qu'il pouvait y avoir une infinité d'opérateurs préfixes. Ces opérateurs sont ensuite suivis d'une expression sans opérateur. Éventuellement, il y a un opérateur suffixe. Puis, l'expression s'arrête, ou alors il y a un opérateur infixe puis le début d'une nouvelle expression (c'est « récursif »).

Un pseudo code correspondant à cette idée, générant un arbre d'analyse syntaxique à partir d'une expression Javascript (sous forme de chaîne de caractères ou de token), pourrait être le suivant (attention, je ne garantis pas que c'est correct, je n'ai pas encore testé) :

# tokenStream est l'expression javascript en entrée qu'on analyse

# Cette liste va contenir les opérateurs et les expressions javascript sans opérateurs.
list := [];

begin:

# On récupère zéro, un ou plusieurs opérateurs préfixes
infinite loop {
    op := parsePrefixOp(tokenStream);
    if (op) {
        list.push(op);
    } else {
        break;
    }
}

# On récupère une expression JS sans opérateurs
list.push(parseOperatorFreeExpression(tokenStream))
# NOTE: S'il n'y en a pas, on lève une erreur de syntaxe et on s'arrête

# On récupère au plus un opérateur suffixe.
op := parseSuffixOp(tokenStream);
if (op) {
    list.push(op);
}

# NOTE: si on a trouvé un opérateur suffixe, on peut tout de suite lever une erreur ici si le dernier opérateur analysé est un opérateur ++ ou --, ou alors décider de traiter ça plus tard, lors de la résolution des priorité opératoires par exemple.
# On peut même avoir écrit le parseur d'une façon que si un -- ou un ++ est trouvé, un code différent, sans analyse des opérateurs suffixes, soit utilisé !

# On récupère au plus un opérateur infixe
op := parseInfixOp(tokenStream);
if (op) {
    list.push(op);

    # Si on en a trouvé un, on recommence
    goto begin;
}

# On est arrivé à la fin de la chaîne, on va résoudre les priorités opératoires et construire l'arbre d'analyse syntaxique en conséquence.
return resolveOperatorPriorities(list)

On peut commencer à voir pourquoi les erreurs sont différentes entre ++ ++ i et i ++ ++. Il y a fort à parier que l'erreur de syntaxe n'est pas levée exactement au même endroit.

Dans le cas i ++ ++, il est possible que le deuxième ++ ne soit même pas compris comme l'opérateur de post incrémentation : on ne les cherche pas à cet endroit puisqu'on ne cherche qu'un opérateur suffixe au maximum.

Alors que dans le cas ++ ++ i, il est fort probable qu'une sorte de boucle essaie de manger tous les opérateurs préfixes jusqu'à rencontrer une expression Javascript non préfixée. C'est seulement plus tard, quand le parseur va trouver qu'il y a quelque chose qui n'est pas « incrémentable » (un référence, quoi - qui peut d'ailleurs être entre parenthèse 🙃), qu'il va râler.

Différences de comportement des moteurs Javascript

Est-ce que les moteurs Javascript analysent les expressions de la même manière, d'ailleurs ?

On peut vite le découvrir sans lire leur code source (ce qui doit être très intéressant, mais ce n'est pas l'objet de ce journal). Dans le shell Javascript interactif de Node comme dans celui la console Web de Firefox, si vous ne terminez pas une instruction Javascript, l'interface vous laisse la continuer même après être passé à la ligne si l'interpréteur Javascript n'a pas encore vu d'erreur de syntaxe. Ce qui permet de deviner des choses sur leur manière d'analyser le code. Essayons avec -- -- i, tiens…

V8

Si vous tapez -- -- i dans Node et que vous passez à la ligne, pour lui, l'expression n'est pas encore terminée et il vous laisse taper un identificateur ou un opérateur avant de s'apercevoir qu'il y a anguille sous roche. Pire que ça, il vous laisse continuer encore un peu si vous tapez un opérateur suffixe. Autrement dit, l'expression n'est pas terminée pour lui après avoir tapé -- -- i --.

$ node
Welcome to Node.js v14.7.0.
Type ".help" for more information.
> -- -- i --
... ;
-- -- i --
      ^^^^

Uncaught SyntaxError: Invalid left-hand side expression in prefix operation

Et d'ailleurs, il donne une erreur sur i -- et pas avant. Tout porte à croire qu'il lève l'erreur lors de la résolution des priorités opératoires et qu'éventuellement, il parcourt sa liste de la fin vers le début.

SpiderMonkey

Si vous tapez -- --i puis entrée (en fait, vous devrez rajouter une espace avant l'entrée parce que l'autocomplétion propose if), vous vous prenez immédiatement un message d'erreur. SpiderMonkey n'essaierai même pas de lire une suite éventuelle de l'expression. D'ailleurs, si vous lui faites manger -- -- i --, il va continuer à planter sur le caractère 3, contrairement à V8 :

$ gjs
gjs> -- -- i --
typein:1:3 expected expression, got '--':
typein:1:3 -- -- i --
typein:1:3 ...^
  @<stdin>:1:42

On peut penser qu'il détecte assez tôt dans l'analyse de l'expression la présence d'un opérateur préfixe alors qu'un opérateur ++ ou—est déjà présent juste avant.

Rhino

Rhino, c'est le moteur Javascript écrit en Java, par Mozilla aussi, et qui a d'ailleurs été embarqué par Sun dans Java SE 6 pour ajouter des capacités de scripting à Java.

$ rhino
Rhino 1.7.7.1
js> -- -- i ++
js: "<stdin>", line 2: erreur de syntaxe
js: -- -- i ++
js: ....^

Bon bah à tous les coups, il se comporte à peu près pareil que SpiderMonkey dans ce cas. D'ailleurs, un commentaire dans le code de son parseur, un petit fichier de 4000 lignes, écrit à la main comme tous les bons vrais parseurs (sauf celui de PHP écrit avec une belle grammaire Yacc bien propre), dit « It is based on the SpiderMonkey C source files jsparse.c and jsparse.h in the jsref package ».

Et si le monde des moteurs Javascript vous passionne, le code de Rhino semble plutôt accessible, en tout cas probablement plus que ses potes, avec peu d'abstractions : c'est du code assez direct qui n'y va pas par 4 chemins.

JavascriptCore

Et le moteur JS de WebKit alors ?

$ seed
> -- ++ i ++
..
..SyntaxError The prefix-decrement operator requires a reference expression.

Lui aussi semble lever l'erreur assez tôt puisqu'il râle sur le premier opérateur…

Voilà. On dirait que V8 est un peu différent de ses potes dans sa manière d'analyser les expressions Javascript, en tout cas sur cet aspect.

Dans d'autres langages

Java (JShell, OpenJDK)

$ jshell                                                                                                                                       [0]
|  Welcome to JShell -- Version 11.0.8
|  For an introduction type: /help intro

jshell> int i = 0;
i ==> 0

jshell> ++ ++ i ++;
|  Error:
|  unexpected type
|    required: variable
|    found:    value
|  ++ ++ i ++;
|        ^--^

Ce n'est pas super clair, mais ça semble fonctionner au moins un peu comme V8.

C - Clang

$ clang t.c
t.c:1:24: error: expression is not assignable
int main() { int i; ++ ++ i ++; }
                       ^  ~~~~

Clang nous dit qu'il ne peut pas vraiment pré-incrémenter le résultat d'une post-incrémentation donc ça ressemble un peu au comportement de V8.

C - GCC

$ gcc t.c
t.c: In function ‘main’:
t.c:1:24: error: lvalue required as increment operand
    1 | int main() { int i; ++ ++ i ++; }
      |                        ^~

Là, j'ai vaguement l'impression qu'il s'attend à avoir une lvalue (c'est à dire un truc qui peut se placer à gauche d'un signe égal, une variable quoi) à l'endroit pointé, donc ça marcherait un peu comme SpiderMonkey : il veut un truc qu'il peut pré-incrémenter à la suite du premier opérateur de pré-incrémentation.

C - Tiny C Compiler

$ tcc t.c
t.c:1: error: lvalue expected

Bon, bah là on n'en saura pas plus.

Mot de la fin

On peut espérer que tous les parseurs d'un même langage sortent des arbres d'analyse syntaxique à peu près équivalent. En tout cas, dès qu'il y a des erreurs, on peut voir que les comportements diffèrent…

Au final, ne mettez pas des opérateurs en trop et ça va marcher.