tag:linuxfr.org,2005:/tags/parsing/publicLinuxFr.org : les contenus étiquetés avec « parsing »2022-01-27T11:22:18+01:00/favicon.pngtag:linuxfr.org,2005:Bookmark/42002022-01-27T11:22:18+01:002022-01-27T11:22:18+01:00 Announcing Parcel CSS: A new CSS parser, compiler, and minifier written in Rust!<a href="https://parceljs.org/blog/parcel-css/">https://parceljs.org/blog/parcel-css/</a> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/126718/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/users/gilcot/liens/announcing-parcel-css-a-new-css-parser-compiler-and-minifier-written-in-rust#comments">ouvrir dans le navigateur</a>
</p>
Gil Cot ✔https://linuxfr.org/nodes/126718/comments.atomtag:linuxfr.org,2005:Diary/393442020-09-16T05:04:16+02:002020-09-16T05:04:16+02:00Le saviez-vous?Licence CC By‑SA http://creativecommons.org/licenses/by-sa/4.0/deed.fr<p>Désolé, je m'ennuies un peu (ce qui explique le titre fainéant), j'ai donc décidé de vous partager ce point de savoir inutile:</p>
<p>Le standard X11 actuel, que l'on pourrais donc dire «moderne» supporte un certain nombre de formats de fichiers pour décrire une fonte.<br>
Parmi ces formats, l'on peut noter le format <a href="https://fr.wikipedia.org/wiki/Bitmap_Distribution_Format">bdf</a>.</p>
<p>Parmi les choses "à savoir", il semble que:</p>
<p>1) X11 se base sur la version 2.1 du format, alors que la version 2.2 du format, parue en 1993, permets une réduction non-négligeable de la taille du fichier décompressé (~10% sur le fichier qui m'a servi d'exemple) ainsi que du temps de parsing (de 0.25s à 0.20s). J'ai utilisé le fichier de fontes japonaises issu de ce <a href="http://unifoundry.com/unifont/index.html">site</a> que j'ai migré vers la 2.2 pour le fun (un coup de sed, et c'est réglé, vraiment). La raison? Cette mise à jour permets, notamment, de spécifier des paramètres par défaut qui s'appliquerons à chaque glyphe!</p>
<p>2) X11 semble ne pas avoir été heureux des fins de lignes, et a décidé qu'il était pertinent d'introduire une nuance dans le format de fichier pour un sujet aussi important.</p>
<p>3) La version 2.2 (de 1993 toujours) introduit le support des scripts qui ne se suivent pas en ligne! Mais en lisant la spec de la version 2.1, on échoue a comprendre ce qu'il y a en plus: DWIDTH est complété par DWIDHT1 et VVECTOR, mais l'intérêt est difficile à comprendre… vu que les offset pour calculer le prochain origin ont des valeurs X et Y!</p>
<p>4) la version 2.2 donne un example de la version… 2.1!</p>
<p>5) X11 utilisais soit un encodage perso en 1er champ, soit l'encodage d'adobe, aka postscript, lequel ne semble plus trop documenté. En pratique, je suis persuadé qu'il s'agit d'un encodage perso, donc, le X11BDF en plus d'être inutilement lent et peu performant, en plus ne respecte pas les formats!</p>
<p>Et pour ceux qui se demandent, oui, je m'amuse coder un parseur bdf. Ce format est raisonnablement simple à implémenter, et plus esthétique que le monospace PSF.<br>
Vu qu'il est implémenté en texte, j'ai même pu écrire une syntaxe bdf, que je partagerais peut-être, si vous êtes sages (même si tout le monde s'en fout en vrai) quand je l'aurais finit (en vrai ça complèterais pas mal mon quick-start, avec un cas d'usage réel)</p>
<p>Bonne nuit a ceux qui dorment pas encore :)</p>
<div><a href="https://linuxfr.org/users/freem/journaux/le-saviez-vous-88d5555e-00a8-49e5-892d-d0dcb4e2f41f.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/121617/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/users/freem/journaux/le-saviez-vous-88d5555e-00a8-49e5-892d-d0dcb4e2f41f#comments">ouvrir dans le navigateur</a>
</p>
freemhttps://linuxfr.org/nodes/121617/comments.atomtag:linuxfr.org,2005:Diary/393292020-09-09T23:46:48+02:002020-09-10T08:26:00+02:00Psychologie d'un parseur JavascriptLicence CC By‑SA http://creativecommons.org/licenses/by-sa/4.0/deed.fr<h2 class="sommaire">Sommaire</h2>
<ul class="toc">
<li>
<a href="#toc-un-constat-choquant">Un constat choquant</a><ul>
<li><a href="#toc-pourquoi-%C3%A7a-plante">Pourquoi ça plante</a></li>
</ul>
</li>
<li><a href="#toc-un-d%C3%A9but-de-piste">Un début de piste</a></li>
<li><a href="#toc-comment-analyse-t-on-un-expression-javascript">Comment analyse-t-on un expression Javascript ?</a></li>
<li>
<a href="#toc-diff%C3%A9rences-de-comportement-des-moteurs-javascript">Différences de comportement des moteurs Javascript</a><ul>
<li><a href="#toc-v8">V8</a></li>
<li><a href="#toc-spidermonkey">SpiderMonkey</a></li>
<li><a href="#toc-rhino">Rhino</a></li>
<li><a href="#toc-javascriptcore">JavascriptCore</a></li>
</ul>
</li>
<li>
<a href="#toc-dans-dautres-langages">Dans d'autres langages</a><ul>
<li><a href="#toc-java-jshell-openjdk">Java (JShell, OpenJDK)</a></li>
<li><a href="#toc-c---clang">C - Clang</a></li>
<li><a href="#toc-c---gcc">C - GCC</a></li>
<li><a href="#toc-c---tiny-c-compiler">C - Tiny C Compiler</a></li>
</ul>
</li>
<li><a href="#toc-mot-de-la-fin">Mot de la fin</a></li>
</ul>
<p>(attention : beaucoup de suppositions, peu de vérifications dans ce journal. Lisez pour le cheminement plus que pour le résultat…)</p>
<h2 id="toc-un-constat-choquant">Un constat choquant</h2>
<p>De manière tout à fait intéressante en Javascript :</p>
<pre><code class="js"><span class="o">++</span> <span class="o">++</span> <span class="nx">i</span><span class="p">;</span></code></pre>
<p>Donne l'erreur suivante dans Node (V8):</p>
<pre><code>SyntaxError: Invalid left-hand side expression in prefix operation`
</code></pre>
<p>Et, dans Firefox (SpiderMonkey):</p>
<pre><code>SyntaxError: expected expression, got '++'
</code></pre>
<p>Alors que :</p>
<pre><code class="js"><span class="nx">i</span> <span class="o">++</span> <span class="o">++</span><span class="p">;</span></code></pre>
<p>Donne l'erreur suivante dans les deux moteurs (à quelque chose près) :</p>
<pre><code>SyntaxError: Unexpected token '++'
</code></pre>
<p>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 ?</p>
<h3 id="toc-pourquoi-ça-plante">Pourquoi ça plante</h3>
<p>Ah oui, au fait, présentons rapidement quelques bases de ce problème.</p>
<ul>
<li>
<code>++i</code> est une pré-incrémentation. Elle est censée prendre <code>i</code>, lui ajouter 1, enregistrer la valeur dans <code>i</code> et retourner le résultat de cette opération. <code>--i</code> fonctionne pareil, mais retire 1.</li>
<li>
<code>++ ++i</code> devrait faire la même chose, puis… comme <code>++i</code> n'est pas une référence, le premier <code>++</code> 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.</li>
<li>
<code>i++</code> est censé prendre <code>i</code>, lui ajouter 1, enregistrer la valeur dans <code>i</code> et retourner la valeur originale de <code>i</code>. <code>i--</code> fait pareil mais retire 1.</li>
<li>
<code>i++ ++</code> a à peu près le même sens que <code>++ ++i</code>, c'est à dire aucun.</li>
</ul>
<p>Donc ça plante. Mais pourquoi ça ne plante pas exactement de la même manière ?</p>
<h2 id="toc-un-début-de-piste">Un début de piste</h2>
<p>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.</p>
<p>Voyez plutôt ces expressions valides en Javascript :</p>
<pre><code>+ ++i
- ++i
+ - + - i
- + - + i
+ + i
- - i
void typeof void + -- i
</code></pre>
<p>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.</p>
<h2 id="toc-comment-analyse-t-on-un-expression-javascript">Comment analyse-t-on un expression Javascript ?</h2>
<p>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).</p>
<p>Comment peut-on analyser une telle expression alors ? On pourrait aussi bien lire le code des différents moteurs Javascript, ou <a href="https://www.ecma-international.org/ecma-262/#sec-ecmascript-language-scripts-and-modules">lire la doc, tant qu'à faire</a>, 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. </p>
<p>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 »). </p>
<p>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é) :</p>
<pre><code># 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)
</code></pre>
<p>On peut commencer à voir pourquoi les erreurs sont différentes entre <code>++ ++ i</code> et <code>i ++ ++</code>. Il y a fort à parier que l'erreur de syntaxe n'est pas levée exactement au même endroit.</p>
<p>Dans le cas <code>i ++ ++</code>, il est possible que le deuxième <code>++</code> 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.</p>
<p>Alors que dans le cas <code>++ ++ i</code>, 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.</p>
<h2 id="toc-différences-de-comportement-des-moteurs-javascript">Différences de comportement des moteurs Javascript</h2>
<p>Est-ce que les moteurs Javascript analysent les expressions de la même manière, d'ailleurs ?</p>
<p>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 <code>-- -- i</code>, tiens…</p>
<h3 id="toc-v8">V8</h3>
<p>Si vous tapez <code>-- -- i</code> 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é <code>-- -- i --</code>.</p>
<pre><code>$ 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
</code></pre>
<p>Et d'ailleurs, il donne une erreur sur <code>i --</code> 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.</p>
<h3 id="toc-spidermonkey">SpiderMonkey</h3>
<p>Si vous tapez <code>-- --i</code> puis entrée (en fait, vous devrez rajouter une espace avant l'entrée parce que l'autocomplétion propose <code>if</code>), 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 <code>-- -- i --</code>, il va continuer à planter sur le caractère 3, contrairement à V8 :</p>
<pre><code>$ gjs
gjs> -- -- i --
typein:1:3 expected expression, got '--':
typein:1:3 -- -- i --
typein:1:3 ...^
@<stdin>:1:42
</code></pre>
<p>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.</p>
<h3 id="toc-rhino">Rhino</h3>
<p>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. </p>
<pre><code>$ rhino
Rhino 1.7.7.1
js> -- -- i ++
js: "<stdin>", line 2: erreur de syntaxe
js: -- -- i ++
js: ....^
</code></pre>
<p>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, <a href="https://github.com/mozilla/rhino/blob/master/src/org/mozilla/javascript/Parser.java">un petit fichier de 4000 lignes</a>, écrit à la main comme tous les bons vrais parseurs (<a href="https://github.com/php/php-src/blob/master/Zend/zend_language_parser.y">sauf celui de PHP</a> é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 ».</p>
<p>Et si le monde des moteurs Javascript vous passionne, <a href="https://github.com/mozilla/rhino/blob/master/src/">le code de Rhino</a> 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.</p>
<h3 id="toc-javascriptcore">JavascriptCore</h3>
<p>Et le moteur JS de WebKit alors ?</p>
<pre><code>$ seed
> -- ++ i ++
..
..SyntaxError The prefix-decrement operator requires a reference expression.
</code></pre>
<p>Lui aussi semble lever l'erreur assez tôt puisqu'il râle sur le premier opérateur…</p>
<p>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.</p>
<h2 id="toc-dans-dautres-langages">Dans d'autres langages</h2>
<h3 id="toc-java-jshell-openjdk">Java (JShell, OpenJDK)</h3>
<pre><code>$ 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 ++;
| ^--^
</code></pre>
<p>Ce n'est pas super clair, mais ça semble fonctionner au moins un peu comme V8.</p>
<h3 id="toc-c---clang">C - Clang</h3>
<pre><code>$ clang t.c
t.c:1:24: error: expression is not assignable
int main() { int i; ++ ++ i ++; }
^ ~~~~
</code></pre>
<p>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.</p>
<h3 id="toc-c---gcc">C - GCC</h3>
<pre><code>$ gcc t.c
t.c: In function ‘main’:
t.c:1:24: error: lvalue required as increment operand
1 | int main() { int i; ++ ++ i ++; }
| ^~
</code></pre>
<p>Là, j'ai vaguement l'impression qu'il s'attend à avoir une <code>lvalue</code> (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.</p>
<h3 id="toc-c---tiny-c-compiler">C - Tiny C Compiler</h3>
<pre><code>$ tcc t.c
t.c:1: error: lvalue expected
</code></pre>
<p>Bon, bah là on n'en saura pas plus.</p>
<h2 id="toc-mot-de-la-fin">Mot de la fin</h2>
<p>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…</p>
<p>Au final, ne mettez pas des opérateurs en trop et ça va marcher.</p>
<div><a href="https://linuxfr.org/users/raphj/journaux/psychologie-d-un-parseur-javascript.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/121547/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/users/raphj/journaux/psychologie-d-un-parseur-javascript#comments">ouvrir dans le navigateur</a>
</p>
raphjhttps://linuxfr.org/nodes/121547/comments.atomtag:linuxfr.org,2005:Diary/375492017-10-22T21:59:54+02:002017-10-22T21:59:54+02:00Tous les parsers JSON sont mauvaisLicence CC By‑SA http://creativecommons.org/licenses/by-sa/4.0/deed.fr<h2 class="sommaire">Sommaire</h2>
<ul class="toc">
<li><a href="#introduction">Introduction</a></li>
<li><a href="#%C3%89nigme">Énigme</a></li>
<li>
<a href="#comment-%C3%A9crire-un-parser">Comment écrire un parser</a><ul>
<li><a href="#probl%C3%A8me">Problème</a></li>
<li><a href="#implication">Implication</a></li>
</ul>
</li>
<li><a href="#conclusion">Conclusion</a></li>
</ul><h2 id="introduction">Introduction</h2>
<p>Ce weekend, je me suis intéressé au langage JSON, aux parsers JSON par défaut de plusieurs langages de programmation, et j'ai fait des découvertes intéressantes.</p>
<p>Je pense que le langage JSON n'est plus à présenter à personne, mais au cas où vous vivriez dans une grotte depuis 1999,<br>
petit résumé rapide: JSON est un format de données, très utilisé notamment sur le web, et qui a l'avantage d'être plutôt compact, assez lisible par les êtres humains, et surtout implémenté dans tous les langages de programmation courants.</p>
<p>Une valeur JSON peut être un nombre, un booléen, une chaîne de caractères, la valeur NULL, un tableau de valeurs JSON, ou un tableau associatif (aussi appelé Map, ou objet) associant des chaînes de caractères à des valeurs JSON.</p>
<p>Voici un petit exemple de document JSON:<br><code><br>
{"clef": "valeur", "un nombre": 42, "tableau": [1,2,3], "objet imbrique": {"a" : "b"} }<br></code><br>
Pour plus de détails, le site <a href="http://json.org/">json.org</a> donne la définition formelle du langage et de nombreux détails intéressants, dont une impressionnante liste d'implémentation dans différents langages.</p>
<h2 id="Énigme">Énigme</h2>
<p>Commençons par une énigme, un défi:<br>
Ce journal va parler d’un petit fichier json de 27Ko, qui est parfaitement valide selon la spécification de json, et qu’aucun des parsers json les plus courants n’arrive à parser. Pouvez-vous deviner comment construire un tel fichier ? Sur quel principe ?</p>
<h2 id="comment-écrire-un-parser">Comment écrire un parser</h2>
<p>Si vous ne trouvez pas, prenez quelques secondes pour imaginer comment vous implémenteriez un <em>parser</em><br>
pour JSON dans votre langage de programmation préféré. C’est-à-dire une fonction qui prend en entrée un flux de caractères représentant un objet JSON et retourne un objet facilement manipulable dans votre langage de programmation qui représente le même document. Allez-y, réfléchissez aux grandes lignes de votre programme…</p>
<p>Si vous avez déjà travaillé sur des compilateurs ou autres parsers complexes, vous avez peut-être pensé utiliser un <a href="https://fr.wikipedia.org/wiki/Compilateur_de_compilateur">générateur de compilateur</a>.</p>
<p>Sinon, vous avez probablement pensé à un programme qui a la même forme que <a href="https://github.com/python/cpython/blob/master/Lib/json/decoder.py">le parser JSON de la bibliothèque standard de python</a>:</p>
<ol>
<li>Une fonction principale qui peut parser n’importe quelle valeur JSON. Cette fonction peut parser toutes les valeurs brutes comme les nombres, les booléens ou la valeur nulle.</li>
<li>Mais lorsque cette fonction rencontre le caractère ‘[‘ (début d’un tableau), elle appelle une fonction spécialisée qui parse le contenu d’un tableau. De même pour le caractère ‘{‘, on créer une fonction capable de parser le contenu d’un objet.</li>
<li>La fonction qui parse le contenu d’un tableau va s’assurer que les valeurs sont bien séparées par des virgules, que le tableau est bien terminé par le caractère ‘]’, mais pour parser les valeurs contenues dans le tableau elles-mêmes, elle va faire appel à la fonction définie au début, qui peut parser n’importe quelle valeur JSON.</li>
</ol><p>Cette approche permet de structurer son code de manière claire et expressive, avec des fonctions spécialisées pour les types complexes de JSON. Il est facile de se représenter la manière dont le code fonctionne : si on a un objet dans un tableau, par exemple, alors notre fonction de parsing de tableau est appelée, puis elle appelle notre fonction de parsing d’objet.</p>
<h3 id="problème">Problème</h3>
<p>Cependant, cette approche a un inconvénient. C’est une approche dite récursive, où une fonction peut s’appeler elle-même (dès qu’une structure JSON est imbriquée dans une autre). Notre ordinateur a une pile d’exécution de taille limitée, c’est-à-dire que seul un nombre limité de fonctions peuvent être actives en même temps. Dès qu’une fonction en appelle une autre, cela occupe de la place dans la pile d’exécution, et ce jusqu’à ce que la fonction appelée retourne une valeur. Dans notre cas, quand nous voulons parser par exemple un tableau qui contient un tableau qui contient un tableau, nous occupons au minimum trois places dans la pile d’exécution. Comme sa taille est très limitée, au bout d’un certain nombre de tableaux imbriqués, on n’a plus de place dans la pile pour appeler une nouvelle fonction, et une erreur est levée.</p>
<h3 id="implication">Implication</h3>
<p>La réponse à l’énigme posée plus haut est donc très simple. Il suffit de créer un fichier json qui contient beaucoup de structures imbriquées. La manière la plus succincte de créer un tel fichier est donc simplement de concaténer un grand nombre de ‘[‘ avec un grand nombre de ‘]’. C’est-à-dire de créer un tableau qui contient un tableau qui contient […] qui contient un tableau vide.</p>
<p>Et combien de tableaux imbriqués faut-il pour faire planter un parser JSON ? ET bien dans certains langages, très peu.</p>
<p>J’ai créé un petit projet sur github pour mesurer les limites de différentes bibliothèques de parsing JSON dans différents langages de programmetion : <a href="https://github.com/lovasoa/bad_json_parsers">github.com/lovasoa/bad_json_parsers</a>.</p>
<p>Et les résultats sont très variés selon les langages, de 100 arrays imbriqués maximum en ruby (c’est-à-dire qu’il peut planter sur un fichier de tout juste 202 octets), à 13786 en C++ avec <a href="https://github.com/nlohmann/json">nlohmann::json</a>.</p>
<p>De tous les langages testés, seul haskell sort son épingle du jeu, puisqu’il optimise correctement les appels récursifs.</p>
<p>Je vous encourage à faire des tests avec votre langage/bibliothèque préférés et à poster vos résultats sur ce dépôt github !</p>
<h2 id="conclusion">Conclusion</h2>
<p>Qu’en pensez-vous ? Est-ce juste un cas limite inintéressant ? Ou faut-il réécrire la grande majorité des parsers JSON pour adopter une approche sans appels de fonction récursifs ?</p><div><a href="https://linuxfr.org/users/lovasoa/journaux/tous-les-parsers-json-sont-mauvais.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/112928/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/users/lovasoa/journaux/tous-les-parsers-json-sont-mauvais#comments">ouvrir dans le navigateur</a>
</p>
lovasoahttps://linuxfr.org/nodes/112928/comments.atomtag:linuxfr.org,2005:Post/349532015-02-01T19:29:23+01:002015-02-01T19:29:23+01:00échantillons de logs postfix<p>Bonjour à tous,</p>
<p>j'aurais besoin d'un ou plusieurs échantillons de quelques Mo de fichiers de logs type maillog (anonymisés au besoin) pour tester quelques scripts.</p>
<p>Merci d'avance pour votre aide !<br>
Papey</p><div><a href="https://linuxfr.org/forums/general-hors-sujets/posts/echantillons-de-logs-postfix.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/104674/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/forums/general-hors-sujets/posts/echantillons-de-logs-postfix#comments">ouvrir dans le navigateur</a>
</p>
Papeyhttps://linuxfr.org/nodes/104674/comments.atom