Kleine Parser-Kombinator-Bibliothek
Verfasst: Samstag 16. Februar 2008, 15:31
For fun habe ich eine kleine combinator-parser-Bibliothek erstellt,
die ich hier vorstellen möchte. Ein Parser ist eine Funktion, die
einen String nimmt und entweder ein Tupel mit dem verbleibenden String und
einem abstrakten Syntaxbaum zurückliefert wenn ein Stück Syntax erkannt
wurde oder `None` als Zeichen des Versagens liefert.
Indem man verschiedene Parser kombiniert, kann man Sätze einer
Sprache erkennen, die einer bestimmten Grammatik genügen. Wählt man die
Namen der Parser gut, liest sich das ganze wie eine der üblichen
Grammatikbeschreibungssprachen, zum Beispiel EBNF.
Dieser Parser erkennt einen bestimmten String:
So benutzt man den Parser:
Der folgende Parser verknüpft zwei andere Parser und versagt, wenn der erste
oder zweite Parser versagt. Andernfalls liefert er den Rest der Eingabe und
kombiniert beide ASTs (man erkennt die typische Und-Verknüpfung):
Dieser Parser verknüpft zwei andere Parser und wählt den zweiten, wenn
der erste versagt hat (man erkennt eine Oder-Verknüpfung):
Dieser Parser wendet einen Parser null- oder mehrmals an:
Manchmal ist es auch praktisch, wenn es egal ist, ob ein Parser versagt:
Betrachten wir ein einfaches Beispiel. Diese EBNF-Grammatik beschreibt
Lisp-S-Expressions:
Um ein Atom (eine Folge von Zeichen außer `(`, `)` und `.` sowie Leerzeichen)
zu parsen, kann ich den folgenden Parser benutzen:
Ein Problem sind jedoch Leerzeichen, die üblicherweise implizit ignoriert
werden. Dies leisten die aktuellen Parser nicht. Entweder mache ich sie
explizit, wie in der folgenden Grammatik, oder ich ändere die Parser, damit
sie nicht aus Strings aufsetzen, sondern einem Stom von Token.
Nun kann ich einen Parser für die Lisp-Grammatik bauen:
Kann ich? Nein. `expr` ist rekursiv und das funktioniert deshalb so nicht.
Hier ist ein Workaround, denn eine rein funktionale Lösung ist mir zu
aufwendig:
So benutzt man den Parser:
Wirklich benutzbar ist das Ergebnis aber nicht. Der "AST" ist unleserlich.
Der `token`-Parser gibt das Token als Beitrag zum AST zurück, gleiches
machen `regexp` und damit auch `atom` und `ws`. Der `sequence`-Parser baut
ein Tupel mit alle Ergebnissen (generalisiert für mehr als zwei Parser).
`alternate` liefert eines der beiden Ergebnisse, `optional` liefert das
Ergebnis oder `None`. Viele Tupel, wenig Übersicht.
Definieren wir, dass ein AST von None ignoriert werden soll. Der folgende
Parser ignoriert dann sein Ergebnis und wir können ihn benutzen, um damit
andere Parser zu wrappen:
Definieren wir `sequence` jetzt wie folgt, um im Ergebnis die zu
ignorierenden Ergebnisse auszulassen. Außerdem kommt diese Version von
`sequence` mit mehr als zwei Argumenten klar:
Wir können jetzt wir den AST der Grammatik ausdünnen:
Immer noch zu viele Tupel. `sequence` erzeugt immer noch ein Tupel, dass
ich nicht haben will. Definieren wir noch:
Und können jetzt eine hoffentlich lesbare Grammatik definieren, die einen
String in S-Ausdrücke bestehend aus Python-Listen verwandelt:
Ich überlasse es dem Leser, das "unwrap" so zu ändern, dass das optionale
Argument am Ende einer Liste korrekt geparst wird.
Stefan
PS: Ja, mir sind Pysec und PyParsing bekannt.
die ich hier vorstellen möchte. Ein Parser ist eine Funktion, die
einen String nimmt und entweder ein Tupel mit dem verbleibenden String und
einem abstrakten Syntaxbaum zurückliefert wenn ein Stück Syntax erkannt
wurde oder `None` als Zeichen des Versagens liefert.
Indem man verschiedene Parser kombiniert, kann man Sätze einer
Sprache erkennen, die einer bestimmten Grammatik genügen. Wählt man die
Namen der Parser gut, liest sich das ganze wie eine der üblichen
Grammatikbeschreibungssprachen, zum Beispiel EBNF.
Dieser Parser erkennt einen bestimmten String:
Code: Alles auswählen
def token(t):
def _(s):
if s.startswith(t): return (s[len(t):], t)
return None
return _
Code: Alles auswählen
>>> token("foo")("foobar")
('bar', 'foo')
>>> token("foo")("baz")
>>>
oder zweite Parser versagt. Andernfalls liefert er den Rest der Eingabe und
kombiniert beide ASTs (man erkennt die typische Und-Verknüpfung):
Code: Alles auswählen
def sequence(p1, p2):
def _(s):
r1 = p1(s)
if r1:
r2 = p2(r1[0])
if r2:
return (r2[0], (r1[1], r2[1]))
return None
return _
der erste versagt hat (man erkennt eine Oder-Verknüpfung):
Code: Alles auswählen
def alternate(p1, p2):
def _(s):
r1 = p1(s)
if r1: return r1
return p2(s)
return _
Code: Alles auswählen
def repeat0(p):
def _(s):
def a(s, r):
r0 = p(s)
if r0: return a(r0[0], r + [r0[1]])
return (s, r)
return a(s, [])
return _
Code: Alles auswählen
def optional(p):
def _(s):
r = p(s)
if r: return r
return (s, None)
return _
Lisp-S-Expressions:
Code: Alles auswählen
expr = atom | "(" {expr} ["." expr] ")"
zu parsen, kann ich den folgenden Parser benutzen:
Code: Alles auswählen
def regexp(r):
def _(s):
m = re.match("^" + r, s)
if m: return (s[m.end():], s[:m.end()])
return None
return _
def atom():
return regexp(r'[^ .()]+')
werden. Dies leisten die aktuellen Parser nicht. Entweder mache ich sie
explizit, wie in der folgenden Grammatik, oder ich ändere die Parser, damit
sie nicht aus Strings aufsetzen, sondern einem Stom von Token.
Code: Alles auswählen
expr = ws (atom | "(" {expr} [ws "." expr] ws ")")
Code: Alles auswählen
def ws(): return regexp(r'\s*')
Code: Alles auswählen
expr = sequence(
ws(),
alternate(
atom(),
sequence(
token("("),
repeat0(expr),
optional(sequence(ws(), token("."), expr)),
ws(),
token(")"))))
Hier ist ein Workaround, denn eine rein funktionale Lösung ist mir zu
aufwendig:
Code: Alles auswählen
class forward:
def set(self, p):
self.p = p
def __call__(self, s):
return self.p(s)
expr = forward()
expr.set(
sequence(
ws(),
alternate(
atom(),
sequence(
token("("),
repeat0(expr),
optional(sequence(ws(), token("."), expr)),
ws(),
token(")")))))
Code: Alles auswählen
>>> expr("(a b (c))")
('', (('(', ('a', ' ', 'b', ' ', ('(', ('c',), ')')), ')'),))
Der `token`-Parser gibt das Token als Beitrag zum AST zurück, gleiches
machen `regexp` und damit auch `atom` und `ws`. Der `sequence`-Parser baut
ein Tupel mit alle Ergebnissen (generalisiert für mehr als zwei Parser).
`alternate` liefert eines der beiden Ergebnisse, `optional` liefert das
Ergebnis oder `None`. Viele Tupel, wenig Übersicht.
Definieren wir, dass ein AST von None ignoriert werden soll. Der folgende
Parser ignoriert dann sein Ergebnis und wir können ihn benutzen, um damit
andere Parser zu wrappen:
Code: Alles auswählen
def ignore(p):
def _(s):
r = p(s)
if r: return (r[0], None)
return None
return _
ignorierenden Ergebnisse auszulassen. Außerdem kommt diese Version von
`sequence` mit mehr als zwei Argumenten klar:
Code: Alles auswählen
def sequence(*ps):
def _(s):
t = ()
for p in ps:
r = p(s)
if not r: return None
s = r[0]
if r[1] is not None: t += r[1:]
return (s, t)
return _
Code: Alles auswählen
expr = forward()
expr.set(
sequence(
ignore(ws()),
alternate(
atom(),
sequence(
ignore(token("(")),
repeat0(expr),
optional(sequence(ignore(ws()), ignore(token(".")), expr)),
ignore(ws()),
ignore(token(")"))))))
print expr("a")[1]
>>> ('a',)
print expr("()")[1]
>>> (([],),)
print expt("(a)")[1]
>>> (([('a',)],),)
print expr("(a b (c))")[1]
>>> (([('a',), ('b',), (([('c',)],),)],),)
ich nicht haben will. Definieren wir noch:
Code: Alles auswählen
def unwrap(p):
def _(s):
r = p(s)
if r: return (r[0], r[1][0])
return r
return _
String in S-Ausdrücke bestehend aus Python-Listen verwandelt:
Code: Alles auswählen
ws = ignore(ws())
rep = repeat0
opt = optional
def tokenize(p): return ignore(token(p)) if isinstance(p, str) else p
def seq(*ps): return unwrap(sequence(*(tokenize(p) for p in ps)))
expr = forward()
expr.set(
seq(
ws,
alternate(
atom(),
seq("(", rep(expr), opt(seq(ws, ".", expr)), ws, ")"))))
print expr("(a b (c))")[1]
Argument am Ende einer Liste korrekt geparst wird.
Stefan
PS: Ja, mir sind Pysec und PyParsing bekannt.