Journal Génération de code (Python) avec Grako

Posté par  (site web personnel) . Licence CC By‑SA.
Étiquettes :
37
3
juil.
2016

Sommaire

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  (site web personnel) . Évalué à 4.

    Comment la grammaire peut ne pas donner une boucle infinie ?

    Si tu veux parser 45 avec expression, il vas échouer sur le test de la présence de ( et donc vas passer dans contenu_expression puis dans multiplication puis dans expression et ainsi de suite.

  • # Pyparsing & Parsimonious

    Posté par  (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 :

    from pyparsing import Forward, Combine, Word, Optional, Literal, ZeroOrMore, nums
    
    expression = Forward()
    
    nombre = Combine(Word("+-"+nums, nums) + Optional(Literal('.') + nums)).setName('nombre')
    facteur = (Literal("(").suppress() + expression + Literal(")").suppress()).setName('facteur') | nombre
    
    terme = ZeroOrMore(facteur.setResultsName('left') + Word('* /').setResultsName('op')) + facteur.setResultsName('right')
    expression << ZeroOrMore(terme.setResultsName('left') + Word('+ -').setResultsName('op')) + terme.setResultsName('right')
    
    ast = expression.parseString("45 + 98 / (76 * 2)")
    print(ast.asDict())

    Qui retourne

    {
        'left': '76',
        'op': '* ',
        'right': {
            'left': '76',
            'op': '* ',
            'right': '76'
        }
    }
    

    On remarque les suppress pour exclure un token de l'ast ainsi que setResultsName 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 token
    en 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 ne
    fait 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 :

    RAW_GRAMMAR = """
    expression = addition / soustraction / terme
    addition = terme ws "+" ws expression
    soustraction = terme ws "-" ws expression
    terme = multiplication / division / facteur
    multiplication = facteur ws "*" ws terme
    division = facteur ws "/" ws terme
    facteur = ("(" ws expression ws ")") / nombre
    nombre = ~"[-+]"? chiffre+ ("." chiffre+)?
    chiffre = ~"[0-9]"
    ws = ~"\\s*"
    
    parser = Grammar(RAW_GRAMMAR)
    ast = parser.parse("45 + 98 / (76 * 2)")
    print(ast)

    Le résultat est très verbeux :

    <Node called "expression" matching "45 + 98 / (76 * 2)">
        <Node called "addition" matching "45 + 98 / (76 * 2)">
            <Node called "terme" matching "45">
                <Node called "facteur" matching "45">
                    <Node called "nombre" matching "45">
                        <Node matching "">
                        <Node matching "45">
                            <RegexNode called "chiffre" matching "4">
                            <RegexNode called "chiffre" matching "5">
                        <Node matching "">
            <RegexNode called "ws" matching " ">
            <Node matching "+">
            <RegexNode called "ws" matching " ">
            <Node called "expression" matching "98 / (76 * 2)">
                <Node called "terme" matching "98 / (76 * 2)">
                    <Node called "division" matching "98 / (76 * 2)">
                        <Node called "facteur" matching "98">
                            <Node called "nombre" matching "98">
                                <Node matching "">
                                <Node matching "98">
                                    <RegexNode called "chiffre" matching "9">
                                    <RegexNode called "chiffre" matching "8">
                                <Node matching "">
                        <RegexNode called "ws" matching " ">
                        <Node matching "/">
                        <RegexNode called "ws" matching " ">
                        <Node called "terme" matching "(76 * 2)">
                            <Node called "facteur" matching "(76 * 2)">
                                <Node matching "(76 * 2)">
                                    <Node matching "(">
                                    <RegexNode called "ws" matching "">
                                    <Node called "expression" matching "76 * 2">
                                        <Node called "terme" matching "76 * 2">
                                            <Node called "multiplication" matching "76 * 2">
                                                <Node called "facteur" matching "76">
                                                    <Node called "nombre" matching "76">
                                                        <Node matching "">
                                                        <Node matching "76">
                                                            <RegexNode called "chiffre" matching "7">
                                                            <RegexNode called "chiffre" matching "6">
                                                        <Node matching "">
                                                <RegexNode called "ws" matching " ">
                                                <Node matching "*">
                                                <RegexNode called "ws" matching " ">
                                                <Node called "terme" matching "2">
                                                    <Node called "facteur" matching "2">
                                                        <Node called "nombre" matching "2">
                                                            <Node matching "">
                                                            <Node matching "2">
                                                                <RegexNode called "chiffre" matching "2">
                                                            <Node matching "">
                                    <RegexNode called "ws" matching "">
                                    <Node matching ")">
    

    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 :

    class Visitor(NodeVisitor):
    
        def visit_expression(self, n, vc):
            return vc[0]
    
        def visit_addition(self, n, vc):
            left, _, _, _, right = vc
            return left + right
    
        def visit_soustraction(self, n, vc):
            left, _, _, _, right = vc
            return left - right
    
        def visit_term(self, n, vc):
            return vc[0]
    
        def visit_multiplication(self, n, vc):
            left, _, _, _, right = vc
            return left * right
    
        def visit_division(self, n, vc):
            left, _, _, _, right = vc
            return left / right
    
        def visit_facteur(self, n, vc):
            if len(vc) == 1:
                return vc[0]
            else:
                return vc[2]
    
        def visit_nombre(self, n, vc):
            return float(n.text)
    
        def generic_visit(self, n, vc):
            return vc[0] if vc else n
    
    
    Visitor().visit(ast)

    Niveau débuggage, c'est là encore pas très confortable, exemple:

    >>> print(vc)
    [s = '(76 * 2)'
    Node('', s, 0, 1), s = '(76 * 2)'
    RegexNode('ws', s, 1, 1), 152.0, s = '(76 * 2)'
    RegexNode('ws', s, 7, 7), s = '(76 * 2)'
    Node('', s, 7, 8)]

    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 :

    [<s = '(76 * 2)', Node('', s, 0, 1)>,
    <s = '(76 * 2)', RegexNode('ws', s, 1, 1)>,
    152.0,
    <s = '(76 * 2)', RegexNode('ws', s, 7, 7)>,
    <s = '(76 * 2)', Node('', s, 7, 8)>]

    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.