URL: https://linuxfr.org/users/linkdd/journaux/generation-de-code-python-avec-grako Title: Génération de code (Python) avec Grako Authors: David Delassus Date: 2016年07月03日T16:12:58+02:00 License: CC By-SA Tags: python, bnf, peg et packrat_parsing Score: 37 Depuis quelques jours, je découvre une lib Python, [grako](https://bitbucket.org/apalala/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](https://fr.wikipedia.org/wiki/Extended_Backus-Naur_Form) 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](https://github.com/andialbrecht/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 (**A**bstract **S**yntax **T**ree) 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 : ```python # -*- 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 : ```python 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 : ```python 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)`` : ```json { "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 : ```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 : ```python 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 : ```python 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 : ```json { "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 : ```python 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 : ```python 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 : ```python 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 : ```python 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_``, 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`` : ```python 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_ 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 : ```python 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 : ```python 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_ 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

AltStyle によって変換されたページ (->オリジナル) /