Direkt zum Hauptbereich

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")

Beliebte Posts aus diesem Blog

Lidl und der Kassen-Bug

Es gibt Fehler, im Informatiker-Jargon "Bugs", die etwas anrühriges haben. Ich bat den Menschen an der Kasse bei Lidl um einen Moment Geduld und meine Kinder um Ruhe, um nicht den wunderbaren Moment zu verpassen, bei dem es passierte. Der Lidl-Mensch fluchte kurz auf -- und ich war entzückt! "Einen Moment, davon muss ich ein Foto machen!" Und dann machte ich noch eines. Ich bin heute extra für diesen Fehler zu Lidl gepilgert -- ich wollte es mit eigenen Augen sehen. Gestern hat mir ein Student (vielen Dank Herr Breyer) von diesem Fehler in einer EMail berichtet. Ein richtig schöner Fehler, ein Klassiker geradezu. Ein Fehler, den man selten zu Gesicht bekommt, so einer mit Museumswert. Dafür wäre ich sogar noch weiter gereist als bis zum nächsten Lidl. Der Fehler tritt auf, wenn Sie an der Kasse Waren im Wert von 0 Euro (Null Euro) bezahlen. Dann streikt das System. Die kurze Einkaufsliste dazu: Geben Sie zwei Pfandflaschen zurück und Lidl steht mit 50 Cent bei Ihne

Syntax und Semantik

Was ist Syntax, was ist Semantik? Diese zwei Begriffe beschäftigen mich immer wieder, siehe zum Beispiel auch " Uniform Syntax " (23. Feb. 2007). Beide Begriffe spielen eine entscheidende Rolle bei jeder Art von maschinell-verarbeitbarer Sprache. Vom Dritten im Bunde, der Pragmatik, will ich an dieser Stelle ganz absehen. Die Syntax bezieht sich auf die Form und die Struktur von Zeichen in einer Sprache, ohne auf die Bedeutung der verwendeten Zeichen in den Formen und Strukturen einzugehen. Syntaktisch korrekte Ausdrücke werden auch als "wohlgeformt" ( well-formed ) bezeichnet. Die Semantik befasst sich mit der Bedeutung syntaktisch korrekter Zeichenfolgen einer Sprache. Im Zusammenhang mit Programmiersprachen bedeutet Semantik die Beschreibung des Verhaltens, das mit einer Interpretation (Auslegung) eines syntaktisch korrekten Ausdrucks verbunden ist. [Die obigen Begriffserläuterungen sind angelehnt an das Buch von Kenneth Slonneger und Barry L. Kurtz: Formal Syn

Mit Prof. Handke im Gespräch: Vom Workbook zum Inverted Classroom

Aus dem Netz in Handkes Büro Es gibt diese schönen Momente, da führen soziale Medien zu sozialen Begegnungen im echten Leben. Ich twittere im Nachgang zur #BiDiWe16, ein Dialog mit Jürgen Handke ergibt sich, er schickt mir seine Telefonnummer, ich rufe sofort durch, wir verabreden uns. Drei Tage nach der #BiDiWe16 sitze ich bei Handke im Büro, das gleichzeitig sein beachtlich ausgestattetes Aufnahmestudio beherbergt. Es ist Freitagmorgen, 9. September 2016. Jürgen Handke ist mir kein Fremder. Ich habe zwei seiner ICM-Konferenzen besucht, auf der #BiDiWe16 in Berlin hielt er die Keynote. Er hat für seine Lehre Preise erhalten, zuletzt 2015 den Ars Legendi-Preis für exzellente Hochschullehre. Zugegeben, ich hadere mit dem Konzept des Inverted Classroom -- auch Flipped Classroom genannt. Meine Erfahrungen mit der Programmierausbildung von Informatik-Studierenden des 1. und 2. Semesters lassen mich zweifeln. Videos habe ich auch schon produziert, aber vor allem das selbstgesteuerte