Sommaire
- Besoin initial, trouver la lib!
- SQLParse VS Grako
- Générer un parseur
- Utiliser le parseur
- Analyse sémantique
- Conclusion
Depuis quelques jours, je découvre une lib Python, grako. Et je dois dire, elle est assez magique !
Besoin initial, trouver la lib!
Le besoin initial s'est présenté au boulot : on doit écrire un DSL pour interroger un ensemble de systèmes fournissant chacun de la donnée à leurs manières.
La première chose faite, c'est d'écrire la grammaire eBNF de ce DSL. Histoire de prévoir comment on va parser le bazar.
La seconde chose faite, et c'est devenu un réflexe maintenant quand je code en Python, est de chercher si ce que je veux faire n'existe pas déjà (je n'aime pas réinventer la roue). C'est la que je tombe sur sqlparse et Grako.
SQLParse VS Grako
SQLParse permet de parser une requête SQL et de retourner une liste de token, à nous de faire l'analyse sémantique et de donner du sens à l'ensemble. Bien mais limité par rapport au DSL que l'on a écrit.
Grako permet de parser une grammaire eBNF (qu'ils ont étendu à leur sauce), et de générer le code d'un parseur qui va retourner un AST (Abstract Syntax Tree) représentant le texte parsé.
Au premier abord, Grako est plus souple, mais ça ne s'arrête pas là!
Elle fournit également des outils pour faire l'analyse sémantique. Deux en fait, mais d'abord voyons comment générer notre parseur.
Générer un parseur
L'exemple simple est d'écrire une calculatrice, la grammaire (simplifiée) :
expression = ("(" contenu_expression ")") | contenu_expression ;
contenu_expression = multiplication | division | addition | soustraction | terme ;
addition = (expression | terme) "+" (terme | expression) ;
soustraction = (expression | terme) "-" (terme | expression) ;
multiplication = (expression | terme) "*" (terme | expression) ;
division = (expression | terme) "/" (terme | expression) ;
terme = [ "-" | "+" ] { chiffre }+ [ "." { chiffre }+ ] ;
chiffre = /[0-9]/ ;
Il existe un outil en ligne de commande pour générer le code, mais ici ce qui nous intéresse c'est de le faire directement en Python.
Donc en zieutant le code de cet outil en ligne de commande on obtient :
# -*- coding: utf-8 -*-
from grako.parser import GrakoGrammarGenerator
from grako.codegen import pythoncg
with open('grammar.bnf') as f:
parser = GrakoGrammarGenerator('Math', filename=f.name)
model = parser.parse(f.read())
code = pythoncg(model)
print(code)
La variable code contient ici le code généré, on va trouver ainsi la définition de notre parseur : MathParser
.
De mon côté, j'ai choisi de créer un module Python dynamiquement, afin d'avoir le parseur généré complètement au runtime :
from six import exec_ # compatibilité python2 et python3
import imp
import sys
module = imp.new_module('math_parser')
exec_(code, module.__dict__)
sys.modules['math_parser'] = module
Et je peux désormais accéder à module.MathParser
!
Utiliser le parseur
Si j'essaye de parser une expression mathématique en l'état :
parser = module.MathParser()
ast = parser.parse('45 + 98 / (76 * 2)', rule_name='expression')
print(ast)
J'obtiens un AST pas très exploitable :
[['4', '5'], '+', ['9', '8'], '/', '(', [['7', '6'], '*', ['2']], ')']
Heureusement, Grako étend la syntaxe de la grammaire et permet de nommer les différents patterns :
expression = ("(" contenu_expression ")") | contenu_expression ;
contenu_expression = multiplication | division | addition | soustraction | terme ;
addition = left:(expression | terme) op:"+" right:(terme | expression) ;
soustraction = left:(expression | terme) op:"-" right:(terme | expression) ;
multiplication = left:(expression | terme) op:"*" right:(terme | expression) ;
division = left:(expression | terme) op:"/" right:(terme | expression) ;
terme = value:([ "-" | "+" ] { chiffre }+ [ "." { chiffre }+ ]) ;
chiffre = /[0-9]/ ;
Cela donne comme résultat :
AST({'left': AST({'left': AST({'value': ['4', '5']}), 'right': AST({'value': ['9', '8']}), 'op': '+'}), 'right': ['(', AST({'left': AST({'value': ['7', '6']}), 'right': AST({'value': ['2']}), 'op': '*'}), ')'], 'op': '/'})
Et avec un petit coup de json.dumps(model, indent=4)
:
{
"left": {
"left": {
"value": [
"4",
"5"
]
},
"op": "+",
"right": {
"value": [
"9",
"8"
]
}
},
"op": "/",
"right": [
"(",
{
"left": {
"value": [
"7",
"6"
]
},
"op": "*",
"right": {
"value": [
"2"
]
}
},
")"
]
}
Les choses s'améliorent nettement, on voit quand même que la priorité des opérateurs n'est pas réellement respectée, c'est que la grammaire n'est pas bonne, en la corrigeant :
expression = addition | soustraction | terme ;
addition = left:terme op:"+" right:expression ;
soustraction = left:terme op:"-" right:expression ;
terme = multiplication | division | facteur ;
multiplication = left:facteur op:"*" right:terme ;
division = left:facteur op:"/" right:terme ;
facteur = ("(" expression ")") | nombre ;
nombre = value:([ "-" | "+" ] { chiffre }+ [ "." { chiffre }+ ]) ;
chiffre = /[0-9]/ ;
On obtient :
AST({'left': AST({'value': ['4', '5']}), 'op': '+', 'right': AST({'left': AST({'value': ['9', '8']}), 'op': '/', 'right': ['(', AST({'left': AST({'value': ['7', '6']}), 'op': '*', 'right': AST({'value': ['2']})}), ')']})})
En JSON :
{
"left": {
"value": [
"4",
"5"
]
},
"op": "+",
"right": {
"left": {
"value": [
"9",
"8"
]
},
"op": "/",
"right": [
"(",
{
"left": {
"value": [
"7",
"6"
]
},
"op": "*",
"right": {
"value": [
"2"
]
}
},
")"
]
}
}
Et voilà, problème corrigé, sans modifier une ligne de code.
Analyse sémantique
Méthode 1 : Notre propre classe
Le constructeur de notre parser peut prendre en paramètre une instance de classe qui va s'occuper de faire l'analyse :
parser = module.MathParser(semantics=MySemantics())
Cette classe va avoir une méthode par règle, ces méthodes seront appelées dès que les règles seront rencontrées, par exemple :
class MySemantics(object):
def nombre(self, ast):
return float(''.join(ast.value))
Ce qui aura pour résultat :
AST({'op': '+', 'right': AST({'op': '/', 'right': ['(', AST({'op': '*', 'right': 2.0, 'left': 76.0}), ')'], 'left': 98.0}), 'left': 45.0})
Et :
{
"left": 45.0,
"op": "+",
"right": {
"left": 98.0,
"op": "/",
"right": [
"(",
{
"left": 76.0,
"op": "*",
"right": 2.0
},
")"
]
}
}
Si on ajoute l'évaluation des expressions et des facteurs :
class MySemantics(object):
def nombre(self, ast):
return float(''.join(ast.value))
def facteur(self, ast):
if isinstance(ast, list):
result = ast[1] # on ignore les parenthèses
else:
result = ast
return result
def expression(self, ast):
if not isinstance(ast, float):
result = eval('{0} {1} {2}'.format(
ast.left,
ast.op,
ast.right
))
else:
result = ast
return result
On obtient le résultat de notre calcul, que l'on peut vérifier :
parser = module.MathParser(semantics=MySemantics())
model = parser.parse('45 + 98 / (76 * 2)', rule_name='expression')
assert model == (45 + 98 / (76 * 2))
Pour résumer, on a : une grammaire, une classe sémantique liée à notre grammaire.
Méthode 2 : Le NodeWalker
La seconde méthode repose sur le parcours de l'AST après que ce dernier ait été produit avec une classe sémantique particulière :
from grako.model import ModelBuilderSemantics
parser = module.MathParser(semantics=ModelBuilderSemantics())
model = parser.parse('45 + 98 / (76 * 2)', rule_name='expression')
La classe grako.model.NodeWalker
va permettre de parcourir ce model
, il convient donc de la surclasser :
from grako.model import NodeWalker
class MyWalker(NodeWalker):
def walk_ExpressionNode(self, node):
print(node)
w = MyWalker()
w.walk(model)
Le NodeWalker
va essayer de trouver une méthode nommée walk_<nom de la règle>
, or actuellement, aucune de nos règles n'ont de nom, corrigeons cela :
expression::ExpressionNode = value:(addition | soustraction | terme) ;
addition::AdditionNode = left:terme op:"+" right:expression ;
soustraction::SoustractionNode = left:terme op:"-" right:expression ;
terme::TermeNode = value:(multiplication | division | facteur) ;
multiplication::MultiplicationNode = left:facteur op:"*" right:terme ;
division::DivisionNode = left:facteur op:"/" right:terme ;
facteur::FacteurNode = value:("(" expression ")") | value:nombre ;
nombre::NombreNode = value:([ "-" | "+" ] { chiffre }+ [ "." { chiffre }+ ]) ;
chiffre = /[0-9]/ ;
Je vous passe le gros JSON produit cette fois-ci, mais on a tout de suite beaucoup d'informations sur comment a été parsée notre expression.
Le défaut du NodeWalker
, c'est que dès qu'il trouve une règle, il s'arrête là, ici notre méthode walk_ExpressionNode
n'a été appelée que pour le node racine, pas pour les noeuds enfants.
Pour remédier à cela, on va plutôt utiliser une classe dérivée de NodeWalker
:
from grako.model import DepthFirstWalker
class MyWalker(DepthFirstWalker):
def walk_ExpressionNode(self, node, children_retvals):
# ici, children_retvals est une liste contenant la valeur de retour des méthodes walk_<nodename> des noeuds enfants
print(node)
Cette fois ci, le JSON résultant est encore plus gros, étant donné qu'il parcourt en profondeur.
Lors du parcours, on peut ajouter des valeurs aux noeuds, ce qui est pratique lorsque les noeuds parents vont effectuer leurs traitements.
Cette fois-ci, notre classe ressemble à cela :
class MyWalker(DepthFirstWalker):
def walk_NombreNode(self, node, children_retvals):
return float(''.join(node.value))
def walk_FacteurNode(self, node, children_retvals):
node.result = children_retvals[0]
return node.result
def walk_TermeNode(self, node, children_retvals):
node.result = children_retvals[0]
return node.result
def walk_AdditionNode(self, node, children_retvals):
node.result = node.left.result + node.right.result
return node.result
def walk_SoustractionNode(self, node, children_retvals):
node.result = node.left.result - node.right.result
return node.result
def walk_MultiplicationNode(self, node, children_retvals):
node.result = node.left.result * node.right.result
return node.result
def walk_DivisionNode(self, node, children_retvals):
node.result = node.left.result / node.right.result
return node.result
def walk_ExpressionNode(self, node, children_retvals):
node.result = children_retvals[0]
return node.result
NB: Les noeuds AdditionNode
, SoustractionNode
, MultiplicationNode
et DivisionNode
n'utilisent pas children_retvals
car l'ordre n'est pas forcément respecté lors du parcours de l'arbre (les noeuds sont des dictionnaires, donc les clés n'ont pas d'ordre).
Et au final, on peut valider notre résultat à nouveau :
parser = module.MathParser(semantics=ModelBuilderSemantics())
model = parser.parse('45 + 98 / (76 * 2)', rule_name='expression')
w = MyWalker()
result = w.walk(model) # la méthode walk retourne la valeur du dernier walk_<nodename> appelé
assert result == (45 + 98 / (76 * 2))
Encore une fois, une grammaire et une classe sémantique liée à cette grammaire, c'est tout.
Conclusion
Je vais avoir beaucoup recours à cette librairie, tellement elle est simple à utiliser. Le seul inconvénient reste que la génération du code prend du temps (pour une grammaire complexe, ça augmente vite).
Il faut donc faire attention a ce qu'on ne le fasse qu'une seule fois au lancement de l'application.
Malgré cela, elle répond parfaitement à pas mal de besoins. Beau travail messieurs les devs de Grako <3
# Grammaire en boucle infinie ?
Posté par Guillaum (site web personnel) . Évalué à 4.
Comment la grammaire peut ne pas donner une boucle infinie ?
Si tu veux parser
45
avecexpression
, il vas échouer sur le test de la présence de(
et donc vas passer danscontenu_expression
puis dansmultiplication
puis dansexpression
et ainsi de suite.[^] # Re: Grammaire en boucle infinie ?
Posté par David Delassus (site web personnel) . Évalué à 1.
En passant dans
multiplication
, il va voir que le"*"
est absent, de même pourdivision
,addition
, etsoustraction
. Ainsi il rentre dansterme
et c'est validé.https://link-society.com - https://kubirds.com - https://github.com/link-society/flowg
[^] # Re: Grammaire en boucle infinie ?
Posté par Guillaum (site web personnel) . Évalué à 4.
multiplication = (expression | terme) "*" (terme | expression) ;
donc la première chose qu'il test c'est(expression | terme)
avant de tester"*"
, et donc ma peur de la récursion.J'ai raté une étape ?
[^] # Re: Grammaire en boucle infinie ?
Posté par Lucas . Évalué à 8. Dernière modification le 04 juillet 2016 à 12:15.
Il utilise la méthode packrat parsing comme expliqué sur la page d’accueil de Grako qui permet justement de ne pas boucler infiniment sur les grammaires récursives gauche tout en gardant une analyse descendante.
[^] # Re: Grammaire en boucle infinie ?
Posté par Guillaum (site web personnel) . Évalué à 4.
Merci.
# Pyparsing & Parsimonious
Posté par G.bleu (site web personnel) . Évalué à 4.
Sommaire
Super journal, mais pourquoi n'a-t'il pas déjà été promu en dépêche ;-)
Tombant d'autant plus à pic que Grako vient de sortir une version 3.9.3 le 30 juin dernier.
Personnellement j'avais essayé parcimonious et pyparsing.
Contrairement à Grako qui génère du code python à utiliser dans son application, parsimonious et pyparsing
sont à utiliser comme une lib standard dans laquelle on définie une grammaire chargée à l'exécution.
C'est en fait ce que tu fais via l'intégration de l'outil en ligne de commande Grako à ton code, je pense
même que ça mériterai que tu soumettes une PR pour ajouter cette fonctionnalité à la lib de base.
Pyparsing
Pyparsing (passé en 2.1.5 le 13 juin dernier, décidement c'est le mois !) fourni un moyen pythonique de définir sa grammaire :
Qui retourne
On remarque les
suppress
pour exclure un token de l'ast ainsi quesetResultsName
qui est l'équivalent de la syntaxe de nommage de Grako.On peut voir aussi l'utilisation de l'objet
Forward
permettant de faire référence à un élément avant sa définition.Une option intéressante est de pouvoir utiliser la méthode
setParseAction
permettant de déclencher une fonction prenant le nœud du tokenen argument. Cela permet de customiser l'ast, voir de faire son évaluation pendant cette phase.
Toutefois d'un point de vu ressenti personnel, je trouve qu'on galère beaucoup pour écrire sa grammaire justement à cause de ce problème de forward.
Dans mon exemple j'utilise des
ZeroOrMore
pour éviter d'utiliser de la récursion (les forwards donc) qui en général nefait rien d'autre que des erreurs de parsing plus ou moins abscons.
De plus on perd la compatibilité avec la syntaxe BNF ce qui rend les choses plus compliqués si on veut réimplémenter dans un autre langage.
Parcimonious
Parcimonious avait une syntaxe plus proche d'une bnf :
Le résultat est très verbeux :
Contrairement à pyparsing, pas d'équivalent à
suppress
ici, mêmes les espaces sont présent dans l'ast(ici sous la forme de la règle
ws
).Il faut donc gérer ça dans le visitor parcourant l'ast :
Niveau débuggage, c'est là encore pas très confortable, exemple:
Là il faut comprendre qu'on a une liste de nœuds, simplement leurs
__repr__
retournent une string contenant un retour à la ligne et pas de séparation claire !J'aurai préféré un truc du style :
Je devrais leur faire une PR mais vu que le projet n'a pas évolué depuis 2 ans…
Bilan
Je n'ai été qu'à moitié convaincu par ces deux lib, je pense que pyparsing est pas mal pour les petites grammaire
en raison de son API et de sa capacité à évaluer les nœuds tout en les parsants.
Parsimonious de son côté me semble trop simple et son développement semble stoppé (pas de maj depuis 2ans), à éviter donc.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.