Comment écrire un parser en python avec ply

Posté par: maria | dans Geek-ish, Science | Il y a 3 mois, 2 semaines | 0 comments

Les parseurs ça peut être fatiguant à écrire, et surtout, un exercice difficile.

À chaque fois que j'ai besoin d'écrire un parseur (et ça arrive régulièrement), j'utilise ply, une librairie de lex/yacc Python. Si tu ne sais pas ce que c'est que le lex/yacc, ça sera le sujet d'articles dans le futur proche.

Dans cet article je vais expliquer comment parser un fichier de sortie de ply : parsetab.py. Le but est de récupérer la grammaire dans le  _lr_productions et de sortir de LaTeX, dans un environnement grammar pour donner  ça après compilation.

Installer ply

Il faut exécuter ceci dans son environnement virtuel :

pip install ply

Lexing

Tokens

La première étape est de faire le lexing. Nous devons définir une classe, appelons la MyLexer, et de définir les tokens.

import ply.lex as lex

class MyLexer:
"""
A lexing class for parsetab.py files.
"""
tokens = [
"GRAMMARRULE", # The grammar rule
"LPAREN", # Left parenthesis
"RPAREN", # Right parenthesis
]

States

Ça fait pas beaucoup de tokens pour un tel fichier. C'est parce que nous allons définir un nouvel état exclusif appelé data:

states = [
("data", "exclusive"),
]

Un état exclusif surcharges le comportement du lexer de telle manière qu'il ne ressortira que les tokens de l'état.

Expressions régulières pour les tokens

L'étape suivante est de définir nos tokens, en particulier les tokens qui vont être ignorés.

Tokens ignorés

Parmis les tokens à ignorer il y a :

t_ignore = " \n"                    # Ignores spaces and \n, except if they are defined in following rules
t_ignore_COMMENT = r"\#.*" # Ignores the python comments (useful for the beginning of the file
t_ignore_LRMETHOD = r"_lr_method.*" # Ignores the _lr_method = … lineParsing

Il faut définir les tokens qui vont être ignorés, en particulier dans l'état initial, pour tout ce qu'il y a dans le fichier d'entrée qui n'est pas utile.

Tokens de data

Définissons les tokens de data qui sont utiles. Le premier doit matcher exactement la règle de grammaire. On peut la définir comme ça (si je ne me suis pas trompée) :

t_grammar_GRAMMARRULE = r"(\"|\')[A-Za-z][a-zA-Z0-9_\']*\ ->\ .+?(?=,)"

Il faut également définir ces tokens :

t_grammar_LPAREN = r"\("
t_grammar_RPAREN = r"\)"

Changer d'état

Puisque nous avons deux états (initial et data) il faut que l'on puisse changer d'un état à l'autre :

@staticmethod
def t_begin_data(t):
r"_lr_productions\ =\ \["
t.lexer.push_state("data")

@staticmethod
def t_data_end(t):
r"\]"
t.lexer.pop_state()

Gestion d'erreur

Les erreurs sont courantes lorsqu'on tokenise, puisque les expressions régulières ne sont pas parfaites du premier coup, parce que l'on peut avoir oublier certaines parties du fichier… Pour une gestion très basique des erreurs :

@staticmethod
def t_error(t):
print("Illegal character in INITIAL state '%s'" % t.value[0])
t.lexer.skip(1)

@staticmethod
def t_data_error(t):
print("Illegal character in GRAMMAR state '%s'" % t.value[0])
t.lexer.skip(1)

Lors du passage en production, il pourrait être judicieux de définir des classes d'erreurs.

__init__

def __init__(self, **kwargs):
self.lexer = lex.lex(module=self, **kwargs)

Fonctions de tokenisation

Afin de tester le code, il peut être utile de disposer des fonctions suivantes :

def tokenize(self, data):
"""
Tokenize input data to stdout for testing purposes.
"""
self.lexer.input(data)
while True:
tok = self.lexer.token()
if not tok:
break
print(tok)


def tokenize_file(self, filepath):
"""
Tokenize input file to stdout for testing purposes.
:param fspec: Input file to parse.
"""
with open(filepath, "r") as content:
data = content.read()
return self.tokenize(data)

Parsing

Définir la classe

Pour fonctionner, le parseur a besoin de la liste des tokens.

import ply.yacc as yacc
from lexer import MyLexer

class MyParser:
"""
Parses parsetab.py files
"""
def __init__(self, the_lexer=None):
if the_lexer is None:
the_lexer = MyLexer()
self._lexer = the_lexer
self.tokens = self._lexer.tokens
self._parser = yacc.yacc(module=self)

Règles de la grammaire

Ceci fait, les règles de la grammaire doivent être définies :

@staticmethod
def p_relevantdata(p):
"""RelevantData : DataLines"""
p[0] = p[1]

@staticmethod
def p_datalines(p):
"""DataLines : DataLine
| DataLines DataLine"""
if len(p) == 2:
p[0] = [p[1]]
else:
p[0] = p[1] + [p[2]]

@staticmethod
def p_grammarrule(p):
"""DataLine : LPAREN GRAMMARRULE RPAREN"""
# Let's discard the parenthesis, we don't need those
p[0] = p[2]

Gestion d'erreurs

Voici une rapide gestion d'erreurs. En production, il serait judicieux de lever des erreurs.

@staticmethod
def p_error(p):
    """
    Error handling.
    """
    if p:
        print("Syntax error at token ", p)
        parser.errok()
    else:
        print("Syntax error at EOF")

Utiliser le parseur

Les fonctions suivantes sont nécessaire pour utiliser le parseur :

def parse(self, data):
"""
Parses input data.
"""
return self._parser.parse(data)

def parse_file(self, filepath):
"""
Parses data stored in file.
"""
with open(filepath, "r") as content:
data = content.read()
result = self._parser(data)
return result

AST et ré-écriture

Trop bien \o/ mais ce n'est pas très utile. Il nous faut un AST pour représenter les données et être capable de les ré-écrire en code LaTeX.

Classe Node basique

Une chose après l'autre, il nous faut une classe de nœud. En voici une très basique :

class Node:
    """
    Really really basic Node Class

    Takes into parameter either a list of children
or a single child
    """

    def __init__(self, children=None):
        self.pretty = "Basic Node"
        if not children:
            self.children = []
        elif hasattr(children, "__len__"):
            self.children = children
        else:
            self.children = [children]

    def __str__(self):
        return "Node"

    def __repr__(self):
        return self.pretty

Création des nœuds nécessaires et fonction rewrite()

On en est à la partie intéressante : il faut qu'on réfléchisse à comment il faut implémenter les fonctions rewrite() de chaque nœud défini. Il faut que cela produise du code LaTeX valide (et, si possible, lisible pour un être humain). Voici comment je l'ai implémenté (il faut avoir une connaissance de l'environnement grammar du paquet syntax de LaTeX):

class RelevantDataNode(Node):
    """
    A node that contains all grammar rules.
    """
    pretty = "Relevant Data"

    def rewrite(self):
        code = "\\documentclass{article}\n"
        code += "\\usepackage{syntax}\n"
        code += "\\begin{document}\n"
        code += "\\begin{grammar}\n"
        previous_left = "S"
        for child in self.children:
            if child.left_member() == previous_left:
                code += child.rewrite_end()
            else:
                previous_left = child.left_member()
                code += child.rewrite_full()
        code += "\\end{grammar}\n\\end{document}\n"
        return code


class GrammarRuleNode(Node):
    """
    A node that contains a grammer rule.
    """
    pretty = "Grammar Rule"

    def left_member(self):
        return self.children.strip("'").strip('"').split(" ")[0]

    def rewrite_full(self):
        data = self.children.strip("'").strip('"').split(" ")
        if data[0].isupper() and data[0] != "S'":
            code = '\n\n    "%s" ::=' % data[0]
        else:
            code = '\n\n    <%s> ::= ' % data[0]
        for child in data[2:]:
            if child.isupper():
                code += ' "%s"' % child
            else:
                code += " <%s>" % child
        code += "\n"
        return code

    def rewrite_end(self):
        data = self.children.strip("'").strip('"').split(" ")
        code = "        \\alt"
        for child in data[2:]:
            if child.isupper():
                code += ' "%s"' % child
            else:
                code += " <%s>" % child
        code += "\n"
        return code

De retour au parseur !

Au début, il faut importer l'AST :

import ast as AST

Il nous faut ensuite redéfinir certaines p_ fonctions pour renvoyer des nœuds :

@staticmethod
def p_relevantdata(p):
"""RelevantData : DataLines"""
p[0] = AST.RelevantDataNode(p[1])

@staticmethod
def p_grammarrule(p):
"""DataLine : LPAREN GRAMMARRULE RPAREN"""
# Let's discard the parenthesis, we don't need those
p[0] = AST.GrammarRuleNode(p[2])

Lançons le tout !

Il faut appeler dans ipython :

import myyacc

parser = myyacc.MyParser()
ast = parser.parse_file("/tmp/parsetab.py")
code = ast.rewrite()
with open("/tmp/grammar.tex", "w") as grammar:
grammar.write(code)

Il ne reste plus qu'à compiler le grammar.tex et de regarder si on obtient un résultat correct !

Commentaires

Pas de commentaires actuellement

Nouveau commentaire

requis

requis (non publié)

optionnel

captcha

Proudly propulsed by Django framework.
Code available Here.