Das deutsche Python-Forum

[sma]

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:

Code: (Python)
1 2 3 4 5	def token(t):   def _(s):     if s.startswith(t): return (s[len(t):], t)     return None   return _

So benutzt man den Parser:

Code: (Python)
1 2 3 4	>>> token("foo")("foobar") ('bar', 'foo') >>> token("foo")("baz") >>>

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

Code: (Python)
1 2 3 4 5 6 7 8 9	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 _

Dieser Parser verknüpft zwei andere Parser und wählt den zweiten, wenn
der erste versagt hat (man erkennt eine Oder-Verknüpfung):

Code: (Python)
1 2 3 4 5 6	def alternate(p1, p2):   def _(s):     r1 = p1(s)     if r1: return r1     return p2(s)   return _

Dieser Parser wendet einen Parser null- oder mehrmals an:

Code: (Python)
1 2 3 4 5 6 7 8	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 _

Manchmal ist es auch praktisch, wenn es egal ist, ob ein Parser versagt:

Code: (Python)
1 2 3 4 5 6	def optional(p):   def _(s):     r = p(s)     if r: return r     return (s, None)   return _

Betrachten wir ein einfaches Beispiel. Diese EBNF-Grammatik beschreibt
Lisp-S-Expressions:

Code:

expr = atom | "(" {expr} ["." expr] ")"

Um ein Atom (eine Folge von Zeichen außer `(`, `)` und `.` sowie Leerzeichen)
zu parsen, kann ich den folgenden Parser benutzen:

Code: (Python)
1 2 3 4 5 6 7 8 9	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'[^ .()]+')

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.

Code:

expr = ws (atom | "(" {expr} [ws "." expr] ws ")")

Code: (Python)
1	def ws(): return regexp(r'\s*')

Nun kann ich einen Parser für die Lisp-Grammatik bauen:

Code: (Python)
1 2 3 4 5 6 7 8 9 10 11	expr = sequence(     ws(),     alternate(       atom(),       sequence(         token("("),         repeat0(expr),         optional(sequence(ws(), token("."), expr)),         ws(),         token(")"))))

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:

Code: (Python)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19	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(")")))))

So benutzt man den Parser:

Code: (Python)
1 2	>>> expr("(a b (c))") ('', (('(', ('a', ' ', 'b', ' ', ('(', ('c',), ')')), ')'),))

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:

Code: (Python)
1 2 3 4 5 6	def ignore(p):   def _(s):     r = p(s)     if r: return (r[0], None)     return None   return _

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:

Code: (Python)
1 2 3 4 5 6 7 8 9 10	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 _

Wir können jetzt wir den AST der Grammatik ausdünnen:

Code: (Python)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

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',)],),)],),)

Immer noch zu viele Tupel. `sequence` erzeugt immer noch ein Tupel, dass
ich nicht haben will. Definieren wir noch:

Code: (Python)
1 2 3 4 5 6	def unwrap(p):   def _(s):     r = p(s)     if r: return (r[0], r[1][0])     return r   return _

Und können jetzt eine hoffentlich lesbare Grammatik definieren, die einen
String in S-Ausdrücke bestehend aus Python-Listen verwandelt:

Code: (Python)
1 2 3 4 5 6 7 8 9 10 11 12 13 14	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]

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.