Objekt-orientierte Parser-Kombinatoren in Python

Ich möchte Ihnen eine Technik zur Syntaxanalyse vorstellen, die zwar gar nicht so neu ist, aber immer wieder Aufmerksamkeit erregt. Zum Beispiel in der Smalltalk-Gemeinde durch einen Beitrag von Gilad Bracha zu Newspeak ("Executable Grammars in Newspeak"). In der Haskell-Welt machen Parser-Kombinatoren und die Forschung zu ihnen immer wieder von sich reden, siehe z.B. aktuell "Parser Combinators for Ambiguous Left-Recursive Grammars" von R.A. Frost, R. Hafiz und P. Callaghan, PADL 2008.

Im Folgenden setze ich voraus, dass Sie wissen, was ein Parser ist und Ihnen auch die EBNF zur Darstellung von Grammatiken bekannt ist. Wenn wir weiter unten von einer Parser-Funktion reden, dann meinen wir eine Funktion, die einen String entgegennimmt, diesen parst und ein geeignetes Ergebnis der Parse-Analyse zurückgibt.

Der Begriff des Kombinators kommt aus der Ecke der funktionalen Programmiersprachen. Ein Kombinator ist eine Funktion höherer Ordnung, eine Higher-Order Function (HOF), die selbst eine Funktion zurückgibt. Eine HOF ist eine Funktion, die Funktionen als Argumente entgegennimmt und gegebenenfalls eine Funktion zurückgibt. Von einem Kombinator wird dann gesprochen, wenn die HOF syntaktisch als Infix notiert werden kann. Anschaulich: Statt der bei Funktionen verbreiteten Prefix-Notation combinatorX(functionA,functionB) steht in der Infix-Notation der Kombinator in der Mitte: functionA combinatorX functionB. Damit wird hervorgehoben, dass der Kombinator, ähnlich einem Operator wie etwa "+", zwei Funktionen "kombiniert".

Ein Parser-Kombinator verknüpft Parser-Funktionen und liefert selber eine Parser-Funktion zurück. Nehmen wir an, wir haben eine Parser-Funktion token(), die Token erkennt. Angenommen, der Parser-Kombinator für Sequenzen oder Folgen von Parser-Funktionen kann mit einem Komma "," notiert werden. So lässt sich dann sehr kompakt ein Parser ausdrücken, der zwei Token-Parser als Sequenz kombiniert: token("Hell"),token("o"). Mit dieser Schreibweise kann die Struktur einer EBNF-Beschreibung einer Grammatik direkt als Kombination von Parser-Funktionen ausgedrückt werden. Die Funktionen bilden die Struktur einer EBNF-Beschreibung nach ("function follows form").

Da der Parser-Kombinator selber wieder ein Parser ist, können wir ihn mit einem String aufrufen: (token("Gut"),token("en"))("Guten Tag!")

In vielen Programmiersprachen ist es nicht so ohne weiteres möglich, die Syntax zur Schreibweise von Funktionen zu ändern. Eine Infix-Notation verbietet sich meist. So bleibt einem nur, Parser-Kombinatoren in der nicht ganz so eleganten Prefix-Notation zu nutzen. Ein sehr schönes Beispiel, wie man mit Python Parser-Kombinatoren bauen kann, liefert ein Autor namens "Stefan" (Kürzel "sma") im deutschen Python-Forum in dem Beitrag "Kleine Parser-Kombinator-Bibliothek" (16. Feb. 2008, 16:31). Wenn Sie diesen Beitrag lesen, werden Sie das Folgende besser verstehen.

Will man einen Parser-Kombinator konsequent objekt-orientiert anlegen, dann wird die Idee der Kombination von Parser-Funktionen abgelöst durch eine Kombination von Parser-Objekten, die wieder ein Parser-Objekt statt einer Parser-Funktion liefern. Die Kombination von Objekten, die wieder ein Objekt zurückliefern ist sehr elegant und einfach realisierbar durch Konstruktor-Methoden.

Werden wir konkret. Mit den folgenden zwei Parser-Klassen führen wir einen Token-Parser bzw. einen Parser für reguläre Ausdrücke ein. In Python kann man Objekte aufrufbar (callable) machen, indem man sie mit einer __call__-Methode ausstattet. Ein Objekt wird damit gleichermaßen zu einer "zustandsbehafteten Funktion". Die __repr__-Methode dient zur Überschreibung der standardmäßigen Selbstrepräsentation eines Objekts, vergleichbar mit der "toString"-Methode in anderen Sprachen.

import re, types

class Parser(object): pass

class Token(Parser):
    def __init__(self,token,annotation=None):
        self.token, self.annotation = token, annotation
        assert isinstance(annotation,types.StringType) or annotation == None
    def __call__(self,text):
        if text.startswith(self.token):
            return Node(self,self.token), text[len(self.token):]
        return None, text
    def __repr__(self):
        return "Token('" + str(self.token) + "')"

class RegExp(Parser):    
    def __init__(self,regexp,annotation=None):
        self.regexp, self.annotation  = re.compile(regexp), annotation
        assert isinstance(annotation,types.StringType) or annotation == None
    def __call__(self,text):
        match = self.regexp.match(text)
        if match: return Node(self,match.group()),text[match.end():]
        return None, text
    def __repr__(self):
        return "RegExp(" + str(self.regexp.pattern) + ")"

Schauen wir uns einmal den Gebrauch der Token-Klasse über die Kommandozeile an:

>>> Token("Hey")
Token('Hey')
>>> Token("Hey")("Hey!")
(Hey, '!')
>>> Token("Hey")("Heu")
(None, 'Heu')
>>>

Der Token-Parser liefert immer ein Tupel zurück. Der erste Teil des Tupels ist None, wenn der Parser nicht erfolgreich ist. Bei Erfolg wird ein Knoten-Objekt zurückgegeben. Der zweite Teil des Tupels ist der String-Anteil, den es noch zu parsen gilt. Bei Erfolg ist es der Rest-String (hier "!"), bei Misserfolg der gesamte übergebene String ("Heu").

Hier, der Vollständigkeit halber, der Code zu Node, den Sie der Parser-Klasse voranstellen müssen:

class Node(object):
    def __init__(self,parser,result):
        self.parser = parser
        self.result = result
    def __repr__(self): # reconstruct the parsed input
        if self.result == None: return ""
        if isinstance(self.result,types.TupleType):
            assert all([isinstance(e,Node) for e in self.result])
            return "".join([str(element) for element in self.result])
        return str(self.result)      

Nun wird es interessant. Kommen wir zu den Kombinatoren der Parser-Objekte um Sequenzen bzw. Alternativen abzubilden:

class NaryOperator(Parser):
    def __init__(self,annotation="",*parsers):
        assert all([isinstance(parser,Parser) for parser in parsers])
        assert isinstance(annotation,types.StringType)
        self.parsers, self.annotation = parsers, annotation

class Sequence(NaryOperator):    
    def __init__(self,annotation,*parsers):
        NaryOperator.__init__(self,annotation,*parsers)
        assert len(self.parsers) >= 1
    def __call__(self,text):
        results = ()
        text_ = text
        for parser in self.parsers:
            node, text_ = parser(text_)
            if not node: return None, text
            results += (node,)
        assert len(results) == len(self.parsers)
        return Node(self,results), text_
    def __repr__(self):
        return "("+",".join([str(parser) for parser in self.parsers])+")"
        
class Alternative(NaryOperator):
    def __init__(self,annotation,*parsers):
        NaryOperator.__init__(self,annotation,*parsers)
        assert len(self.parsers) >= 1
    def __call__(self,text):
        for parser in self.parsers:
            node, text_ = parser(text)
            if node: return Node(self,node), text_
        return None, text
    def __repr__(self):
        return "("+"|".join([str(parser) for parser in self.parsers])+")"

Sie sehen, dass ich die Annotation von Parser-Objekten erlaube, womit später die Verarbeitung des erzeugten Parsebaums vereinfacht wird. Das soll hier aber nicht unser Thema sein. Schauen wir uns den Gebrauch der Parser-Kombinatoren an:

>>> s = Sequence("",Token("Gut"),Token("en"))
>>> s
(Token('Gut'),Token('en'))
>>> s("Guten Tag!")
(Guten, ' Tag!')
>>> s("Was ein Tag!")
(None, 'Was ein Tag!')
>>> a = Alternative("",Token("Gut"),Token("en"))
>>> a
(Token('Gut')|Token('en'))
>>> a("Guten Tag!")
(Gut, 'en Tag!')
>>> a("Tag!")
(None, 'Tag!')

Parser-Kombinatoren sind also tatsächlich selbst wiederum Parser -- genau so soll es sein!

Lassen Sie uns noch ein paar einwertige Parser-Kombinatoren hinzufügen, damit wir alles zusammen haben, um eine Grammatik vollständig beschreiben zu können:

class UnaryOperator(Parser):
    def __init__(self,parser,annotation=None):
        assert isinstance(parser,Parser)
        assert isinstance(annotation,types.StringType) or annotation == None
        self.parser, self.annotation = parser, annotation

class Optional(UnaryOperator):
    def __call__(self,text):
        node, text = self.parser(text)
        if node: return Node(self,node), text
        return Node(self,None), text
    def __repr__(self):
        return str(self.parser) + "?"

class ZeroOrMore(UnaryOperator):
    def __call__(self,text):
        results = ()
        while True:
            node, text = self.parser(text)
            if not node: break
            results += (node,)
        return Node(self,results), text
    def __repr__(self):
        return str(self.parser) + "*"

class OneOrMore(UnaryOperator):
    def __call__(self,text):
        results = ()
        text_ = text
        while True:
            node, text_ = self.parser(text_)
            if not node: break
            results += (node,)
        if results == (): return None, text
        return Node(self,results), text_
    def __repr__(self):
        return str(self.parser) + "+"

Ein Konsolenbeispiel zu OneOrMore:

>>> OneOrMore(Token('a'))('aaabbbccc')
(aaa, 'bbbccc')
>>> OneOrMore(Token('a'))('bbbccc')
(None, 'bbbccc')

Wir sind fast am Ziel! Wenn Sie eine Grammatik aufschreiben, in der es rekursive Bezüge gibt, werden Sie auf ein Problem stoßen. Probieren Sie mal Folgendes:

group   = Sequence("group",Token("{"),doc,Token("}"))
config  = Sequence("config",Token("["),doc,Token("]"))
comment = Sequence("comment",RegExp(r'%.*\n'))

doc = ZeroOrMore(Alternative("doc",comment,config,group))

Sie können nicht in "group" auf "doc" verweisen, bevor Sie "doc" eingeführt haben! Würden Sie die Regel von "doc" dem "group" voranstellen, hätten Sie dasselbe Problem, nur anders herum.

Eine Lösung ist, eine Delay-Klasse einzuführen, mit der Sie ein Parser-Objekt anlegen und seine "Logik" per set-Methode nachrüsten. In einer OO-Umgebung ist das eine sehr einfache Lösung, in einer funktionalen Programmierumgebung müssten Sie sich etwas anderes einfallen lassen.

class Delay(Parser):
    def set(self,parser,annotation=None):
        assert isinstance(parser,Parser)
        assert isinstance(annotation,types.StringType) or annotation == None
        self.parser = parser
        self.annotation = annotation
    def __call__(self,text):
        return self.parser(text)
    def __repr__(self):
        if self.parser.annotation:
            return "{"+ str(self.parser.annotation) + "}"
        return "{" + self.parser.__class__.__name__ + "}"

Nun können wir die aus dem letzten Post vorgestellte einfache Grammatik für LateX ("Eine einfache Grammatik für LaTeX") mit unserem objekt-orientierten Parser-Kombinator beschreiben und mit ihr arbeiten:

doc = Delay()

text = RegExp(r"[^\\\{\}\[\]%]+","text")

group   = Sequence("group",Token("{"),doc,Token("}"))
config  = Sequence("config",Token("["),doc,Token("]"))
comment = Sequence("comment",RegExp(r'%.*\n'))

commandToken = RegExp(r"\\\\?[^\\\{\}\[\]%\s]*","commandToken")

commandConfig = Sequence("commandConfig",Optional(comment),config)
commandGroup  = Sequence("commandGroup" ,Optional(comment),group)

command = Sequence("command",
                   commandToken,
                   Optional(commandConfig,"head"),
                   ZeroOrMore(commandGroup,"tail"))
                   
doc.set(ZeroOrMore(Alternative("doc",command,comment,config,group,text)))

Ein erster Härtetest einer jeden Grammatik ist, ob der geparste Input als Output wieder erzeugt werden kann. Wenn Sie Spaß daran haben, probieren Sie es einmal mit einem LaTeX-File.

(Eine Anmerkung am Rande: Die Konstruktortechnik, hier zur Kombination von Parser-Objekten verwendet, habe ich schon einmal kurz erwähnt in dem Blogbeitrag "Uniform Syntax")