Kleine Parser-Kombinator-Bibliothek

[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: Alles auswählen

def token(t):
  def _(s):
    if s.startswith(t): return (s[len(t):], t)
    return None
  return _

So benutzt man den Parser:

Code: Alles auswählen

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

Dieser Parser verknüpft zwei andere Parser und wählt den zweiten, wenn
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 _

Dieser Parser wendet einen Parser null- oder mehrmals an:

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 _

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

Code: Alles auswählen

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: Alles auswählen

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: 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'[^ .()]+')

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: Alles auswählen

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

Code: Alles auswählen

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

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

Code: Alles auswählen

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

So benutzt man den Parser:

Code: Alles auswählen

>>> 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: Alles auswählen

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

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

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

Immer noch zu viele Tupel. `sequence` erzeugt immer noch ein Tupel, dass
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 _

Und können jetzt eine hoffentlich lesbare Grammatik definieren, die einen
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] 

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.