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

Sommaire

• Besoin initial, trouver la lib!
• SQLParse VS Grako
• Générer un parseur
• Utiliser le parseur
• Analyse sémantique
  • Méthode 1 : Notre propre classe
  • Méthode 2 : Le NodeWalker
• 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