PetitParser

[Laurent Caillette]

"PetitParser for Java" 

https://github.com/petitparser/java-petitparser

est un générateur de parseur en Java. Il ne génère pas de code source, tout se fait directement par manipulation de classes représentant les éléments de grammaire.

Voici un exemple en pur Java, tiré de la documentation :

<<<

  final Parser id = letter().seq( letter().or( digit() ).star() ) ;

  final Result id = id.parse( "f12" ) ;

  final String message = "" + id1.get() ;

  LOGGER.info( "" + id2.get() ) ;      // ['f', ['1', '2']]

>>>

Le jar pèse `78 ko`. La license est de type MIT. PetitParser est de la famille PEG ("Parsing Expression Grammar"), c'est à dire qu'on exprime la grammaire de façon non-ambiguë en indiquant comment reconnaître les différents éléments. L'autre famille c'est CFG ("Context Free Grammar") où l'on fournit des règles qui "produisent" le texte à reconnaître.

Le fait de ne pas devoir générer de code source évite de complexifier la phase de construction. De plus ça permet de générer directement des règles à partir du code Java (comme les symboles dans une enum).

L'interface programmatique est très agréable. Il n'y a pas de séparation lexeur-parseur. Les parseurs sont composables à l'envie. Par exemple dans l'exemple ci-dessus ``letter()`` renvoie un parseur combiné ensuite avec un OU logique avec ``digit()``, et c'est encore un autre parseur (``star()``) qui assure la répétition. Un parseur fournit un point d'extension pour manipuler le résultat, qui est une liste des fragments reconnus. C'est de plus bas niveau que l'AST ("Abstract Syntax Tree") fourni par les générateurs du siècle dernier. On peut modifier les objets à la volée, par exemple pour remplacer une chaîne de caractères entourée de séparateurs par l'objet qu'elle représente.

PetitParser s'avère aussi facile à utiliser que les Expressions Régulières, mais avec des capacités infiniment supérieures ("infiniment" n'est pas exagéré du fait de la récursion). Je n'ai pas idée des performances des parseurs générés par PetitParser.

PetitParser a été initialement écrit en SmallTalk. Il a été porté en Java et en Dart.

=== Expériences

J'ai écrit une assez grosse "grammaire Wiki" 

https://github.com/caillette/novelang/blob/master/modules/parser-antlr/src/main/antlr3/org/novelang/parser/antlr/Novelang.g

avec "`ANTLR v3`"

http://antlr.org

. ANTLR se définit comme un générateur de parseur à partir d'une grammaire de type CFG. ANTLR est un générateur de code source, ce qui complexifie la phase de construction. Une fonctionnalité-clé de ANTLR c'est de supporter la génération vers plusieurs langages-cible. Mais dès qu'on succombe à la tentation d'embarquer du code dans la grammaire (et ça vient très vite) on perd cette fonctionnalité. Par ailleurs d'autres outils (transpileurs, LLVM) relativisent fortement l'intérêt de supporter explicitement plusieurs langages-cible. En faveur d'ANTLR on pourrait dire qu'ANTLR Studio fait de beaux diagrammes et que des fois c'est bien de pouvoir lire le code généré. Je n'ai pas testé la composition de grammaires, mais ça semble assez compliqué. Dans son papier "`LL(*)`: The Foundation of the ANTLR Parser Generator" 

http://www.antlr.org/papers/LL-star-PLDI11.pdf

l'auteur de ANTLR explique que cette complexité est le prix à payer pour détecter les ambiguïtés d'une grammaire. Effectivement ANTLR s'est toujours montré sans pitié de côté-là.

Après j'ai écrit une autre "grammaire, également de type Wiki"

https://github.com/caillette/szo/blob/master/js/pack.peg.txt

avec "PEG.js"

https://pegjs.org

et j'ai été impressionné par la vitesse à laquelle j'obtenais un résultat. Plus de lexer, plus d'AST, du code au milieu des règles, la première règle applicable est la bonne, et ça "juste fonctionne". 

Tout récemment j'ai écrit une "mini-grammaire" 

https://github.com/OTCdLink/Chiron-framework/blob/master/modules/chiron/evaluator/src/main/java/com/otcdlink/chiron/evaluator/EvaluatorParser.java

pour Chiron-evaluator, un mini-langage de requêtage pour des collections d'objets en mémoire. Mon choix s'est porté sur PetitParser parce que je n'avais pas besoin de performances monstrueuses et que PetitParser est le plus facile à embarquer, notamment du fait de l'absence de dépendances tierces.

=== Page de publicité : Chiron-evaluator

Chiron-evaluator repose sur la classe ``Evaluator``, qui évalue un prédicat sur un objet d'un type donné. Un ``Evaluator`` est composé d'opérateurs logiques ou de prédicats sur des champs de l'objet. Ces prédicats reposent sur des objets ``QueryField`` à sous-classer pour définir des champs requêtables. Une instance de ``QueryField`` a un paramètres de type pour la valeur de l'objet à évaluer, un extracteur pour sortir cette valeur de l'objet, un paramètre de type pour le paramètre de la requête, un ``Converter`` Guava pour la sérialisation-désérialisation dudit paramètre, et un paramètre de type pour l'opérateur. Ça veut dire qu'on peut utiliser tous les opérateurs qu'on veut. 

Prenons la forme textuelle d'un ``Evaluator`` sur un objet pour lequel on a défini des instances ``SOME_DATE`` et ``SOME_STRING`` d'un ``QueryField`` :

<<<

AND(

  someDate > '1969-12-31_23:59:59:999',

  someString ~= 'F?o'

)

>>>

L'opérateur ``~=`` correspond à une expression régulière. Si on voulait requêter sur un intervalle de date il suffirait de créer un opérateur ``in`` (par exemple) et un ``Converter`` qui sache lire un intervalle. Et après c'est le compilateur qui vérifie qu'on ne raconte pas de bêtise. L'``EvaluatorParser`` utilise la définition des opérateurs pour sa grammaire.

L'``Evaluator`` est un objet immuable avec des opérateurs pour le composer avec d'autres ``Evaluator``.

On peut contextualiser un ``Evaluator`` avec une fonction qui va transformer chaque paramètre de requête. Ça permet de prendre en compte des valeurs "magiques". Comme le type du paramètre peut être différent de celui de la valeur dans l'objet évalué on peut embarquer un sous-langage avec des valeurs comme ``now`` ou ``nextBusinessDay``. Il y a un test qui remplace un ``null`` par la date-heure courante.

Fin de la page de publicité.

=== Considérations sur PEG

Il y a des discussions sur les ambiguïtés permises par PEG. Les parseurs PEG ne sont pas ambigus mais un humain qui lit la grammaire pourra voir plusieurs règles applicables à un même texte. La règle appliquée est la première définie. Donc si l'humain se plante dans son évaluation des priorités il écrira du code qui ne fait pas ce qu'il croit. 

Personnellement j'estime qu'il y a plein d'endroits où on peut faire de pires erreurs sans que ça soulève débat. Je pense que les gens qui ont passé une partie de leur vie à écrire des générateurs de parseurs CFG ont un biais défavorable envers PEG. C'est la même attitude qu'avec la preuve de programme : "Oooh mais tel langage n'est pas //prouvable//, beurk, il ne faut pas l'utiliser." Mais si on utilise un langage prouvable, ça ne veut pas dire qu'on se donne toujours la peine d'en faire la preuve, ni que la spécification prouvée soit la bonne. Autrement dit l'intelligence ne s'arrête pas au choix de l'outil. De toutes façons même avec ANTLR qui est champion dans la détection d'ambiguïté il faut écrire beaucoup, beaucoup de tests pour vérifier qu'on a bien écrit ce qu'on croit. 

Les gens qui parlent de l'introduction d'ambiguïtés dangereuses avec des règles PEG ne fournissent pas d'exemple, mais admettons que ce soit possible. Est-ce que ça peut entraîner des failles de sécurité ? Tout dépend de ce qu'on fait des données derrière. Dans du code natif qui s'exécute avec tous les droits, c'est bien de ne pas s'appuyer sur un parseur généré avec du PEG pour contrôler, par exemple, qu'un utilisateur distant télécharge seulement les fichiers autorisés. Maintenant si on a du code confiné dans une JVM qui vérifie les accès mémoire, et qu'on contrôle l'accès aux données en-dehors du parseur je prétends que PEG n'introduit pas de risque supplémentaire.

Donc ce qu'on peut retenir c'est que pour qui veut générer un parseur, les générateurs PEG permettent d'obtenir un résultat utilisable beaucoup plus rapidement que ceux basés sur CFG. Si on souhaite un haut niveau de formalisme PEG n'est pas la solution, mais encore faut-il être sûr qu'on ait vraiment besoin de ce formalisme. 

Par exemple, j'ai un serveur qui reçoit des requêtes sous forme textuelle avant de les parser pour obtenir un ``Evaluator``. Je lui ajoute avec un ``ET`` logique les contraintes liées à la sécurité avec un ``Evaluator`` qui ne sort pas de l'``EvaluatorParser``.

=== Produits concurrents

Comme parseurs PEG embarquables dans du code Java, on a également "Parboiled"

http://parboiled.org

et "JParsec"

https://github.com/jparsec/jparsec

. Les deux utilisent une bibliothèque de génération de bytecode (ASM et CGlib respectivement), donc ça doit aider pour les performances du parseur généré. 

Le développement de Parboiled a l'air à l'arrêt, l'auteur se concentrant sur "Parboiled 2"

http://parboiled2.org

, très beau mais limité à Scala.

En gouglant j'ai trouvé un "article" 

https://www.heretical.io/posts/2018-02-03-parsers/

où l'auteur raconte qu'il a écrit le même parseur avec Parboiled puis JParsec. Il conseille JParsec, qui offre de meilleures capacités de composition de grammaires.

Quelqu'un a déjà utilisé Parboiled ou JParsec ?

[Thomas Queste]

Hello,

On avait utilisé Jparsec avec succès il y a quelques années pour exprimer une requête textuelle (title = 'foo' and size > 200) et la transformer en requête Mongodb. Ca marchait bien. Je n’ai plus le code en tête, mais ça n’avait pas posé de problème à Arnaud (Bailly) qui l’avait implémenté.

--
Vous recevez ce message, car vous êtes abonné au groupe Google Groupes "techos".
Pour vous désabonner de ce groupe et ne plus recevoir d'e-mails le concernant, envoyez un e-mail à l'adresse techos+un...@googlegroups.com.
Pour envoyer un message à ce groupe, envoyez un e-mail à l'adresse tec...@googlegroups.com.
Visitez ce groupe à l'adresse https://groups.google.com/group/techos.
Pour obtenir davantage d'options, consultez la page https://groups.google.com/d/optout.

-- 
Thomas Queste

[Henri Tremblay]

Si vous voulez jouer, vous pouvez essayer GraalVM et Truffle: https://www.graalvm.org/docs/graalvm-as-a-platform/implement-language/

[Laurent Caillette]

Salut Henri,

Pour le langage fait maison tu as dégaîné l'arme nucléaire, là ! Détail : derrière le SimpleLanguageParser on trouve une belle grammaire ANTLR v4, mais c'est juste un choix spécifique à l'exemple. L'important c'est qu'ils montrent qu'avec le compilateur AOT on a un "Hello World" qui s'exécute en 4 ms, c'est du délire.