Parser Combinators | Bierpiloten-Blog

Eher durch Zufall bin ich letztens auf einen auch sehr interessanten Ansatz für einen Parsing Algorithmus gekommen, der mal so gar nichts mit dem was ich bisher so gemacht habe zu tun hat: Parser Combinators.

Die Idee dahinter: Man definiert Anstatt einer Grammatik mehrere, ineinander verschachtelte Mini-Parser, wobei ein Parser entweder ein Zeichen absorbiert (LIT, CCL) oder aber mehrere Parser entsprechend so Kombiniert, das man damit Alternativen (OR), Sequenzen (AND, SEQ) und semantische Operationen (JOIN) umsetzen kann. Der Aufruf der Funktionen definiert dann also die syntaktikalische Struktur, und es werden entsprechende Ergebnisse zurückgeliefert.

Sehr schön ist das ganze z.B. hier von Daniel Holden erklärt. Auf Basis dieses Blog-Eintrags habe ich mal einen Ansatz für eine Parser Combinator Library in Python in unter 100 Zeilen programmiert.

#-*- coding: utf-8 -*-
# Python Parser Combinators

def LIT(c):
	return lambda s: (c, s[len(c):]) if s.startswith(c) else None

def CCL(r):
	return lambda s: (s[0], s[1:]) if s[0] in r else None

def OR(a, b):
	return lambda s: a(s) or b(s) or None

def AND(a, b):
	def fn(a, b, s):
		res1 = a(s)
		if res1 is None:
			return None

		res2 = b(res1[1])
		if res2 is None:
			return None

		return [res1[0], res2[0]], res2[1]

	return lambda s: fn(a, b, s)

def SEQ(*args):
	assert len(args) > 0

	def fn(pl, s):
		ret = []
		for p in pl:
			res = p(s)
			if res is None:
				return None

			ret.append(res[0])
			s = res[1]

		return ret, s

	return lambda s: fn(args, s)

def POS(p):
	def fn(p, s):
		ret = []

		while s:
			res = p(s)
			if res is None:
				break

			ret.append(res[0])
			s = res[1]

		if not ret:
			return None

		return ret, s

	return lambda s: fn(p, s)

def JOIN(p):
	def fn(p, s):
		res = p(s)
		if res is None:
			return None

		return "".join(res[0]), res[1]

	return lambda s: fn(p, s)

par = {}

def CALL(n):
	global par
	return lambda s: par[n](s)

def SYM(n, p):
	global par
	par[n] = p
	return p

num = SYM("num", JOIN(POS(CCL("0123456789"))))
factor = SYM("factor", OR(num, SEQ(LIT("("), CALL("expr"), LIT(")"))))
term = SYM("term", OR(SEQ(factor, LIT("*"), CALL("term")), factor))
expr = SYM("expr", OR(SEQ(term, LIT("+"), CALL("expr")), term))

s = "1337+42*23+5"
print("> %s" % s)

while True:
	s = s or raw_input("> ")
	if not s:
		break

	r = expr(s)
	print("< %r" % r[0] if r else "(parse error)")
	s = None

#-*- coding: utf-8 -*-

# Python Parser Combinators

def LIT(c):

return lambda s: (c, s[len(c):]) if s.startswith(c) else None

def CCL(r):

return lambda s: (s[0], s[1:]) if s[0] in r else None

def OR(a, b):

return lambda s: a(s) or b(s) or None

def AND(a, b):

def fn(a, b, s):

res1 = a(s)

if res1 is None:

return None

res2 = b(res1[1])

if res2 is None:

return None

return [res1[0], res2[0]], res2[1]

return lambda s: fn(a, b, s)

def SEQ(*args):

assert len(args) > 0

def fn(pl, s):

ret = []

for p in pl:

res = p(s)

if res is None:

return None

ret.append(res[0])

s = res[1]

return ret, s

return lambda s: fn(args, s)

def POS(p):

def fn(p, s):

ret = []

while s:

res = p(s)

if res is None:

break

ret.append(res[0])

s = res[1]

if not ret:

return None

return ret, s

return lambda s: fn(p, s)

def JOIN(p):

def fn(p, s):

res = p(s)

if res is None:

return None

return "".join(res[0]), res[1]

return lambda s: fn(p, s)

par = {}

def CALL(n):

global par

return lambda s: par[n](s)

def SYM(n, p):

global par

par[n] = p

return p

num = SYM("num", JOIN(POS(CCL("0123456789"))))

factor = SYM("factor", OR(num, SEQ(LIT("("), CALL("expr"), LIT(")"))))

term = SYM("term", OR(SEQ(factor, LIT("*"), CALL("term")), factor))

expr = SYM("expr", OR(SEQ(term, LIT("+"), CALL("expr")), term))

s = "1337+42*23+5"

print("> %s" % s)

while True:

s = s or raw_input("> ")

if not s:

break

r = expr(s)

print("< %r" % r[0] if r else "(parse error)")

s = None

Es ist verblüffend: Man erhält bereits aus der Eingabe 1337+42*23+5 die Ausgabe
[‘1337’, ‘+’, [[’42’, ‘*’, ’23’], ‘+’, ‘5’]], was ja quasi schon einem Syntaxbaum entspricht.

Daniel hat auch die C-Library mpc (Micro Parser Combinators) geschrieben, welche das ganze für C umsetzt. Und da wären wir schon wieder beim nächsten Problem: Die Sache ist eigentlich so elegant, das ich mir wieder die Frage stelle, ob die ganze Arbeit die ich bisher in die Phorward Library gesteckt habe es überhaupt noch Wert ist… oder ob man vielleicht sich einfach aus Spaß lieber damit beschäftigen sollte. Ernstaft nutzen würde es sowieso keiner, das musste ich ja schon inzwischen mehrfach schmerzlich feststellen. Aber naja, vielleicht muss man sich dabei einfach mal von dem Gedanken trennen, mit sowas erfolgreich zu sein… oder was heißt erfolgreich sein, es hat Spaß gemacht das zu programmieren, aber wenn es keiner nutzt und es eigentlich gar keinen Nutzen hat ausser das es einfach da ist und nicht genutzt wird, das ist irgendwie extrem demotivierend und ärgerlich.

Es gibt natürlich auch Paper dazu, wie man Parser Combinators sogar generalisiert hinbekommt. Also sozusagen das, was ich bereits mit GLR parsing mal im Ansatz versucht hatte zu verstehen (und kläglich gescheitert bin), nur eben genau anders herum (GLL).

Vielversprechende Papers dazu:

Denn wie auch Fefe in seinem Blog letztens schrieb, und was auch auf mich persönlich sehr stark zutrifft, und ich mit libphorward, UniCC, JS/CC, pynetree und min_lalr1 inzwischen eigentlich bis zur Gänze ausgereizt haben sollte:

Ich habe meine libc auch nicht geschrieben, damit ich eine libc habe (obwohl das ein schöner Seiteneffekt ist). Ich habe die geschrieben, damit ich das Problemumfeld verstanden habe. Und das habe ich jetzt. Genau so mit dem Webserver und dem LDAP-Server. Du merkst, ob du etwas verstanden hast, wenn du es jemand anderem erklären konntest. Und Programmieren ist ja am Ende wie jemand anderem was erklären, nur dass derjenige sehr maschinenlesbare Erklärungen braucht. 🙂

Ich treffe immer wieder Leute, die denken, man programmiert Open Source-Software, um Teil einer Community zu sein. Oder um am Ende die Software zu haben. Nein. Du programmierst, damit du am Ende das Problem verstanden hast.

Ich habe in meiner Karriere ein-zwei Mal Quellcode bei Plattenausfällen oder versehentlichem Löschen verloren. Das fühlt sich an wie eine Katastrophe, ist es aber nicht. Wenn du für die erste Version ein Jahr brauchtest, geht das nochmal hinschreiben in 1-2 Monaten. Denn diesmal hast du ja das Problemfeld verstanden. DAS ist die eigentliche Währung im Leben. Problemfelder verstanden haben.

Na denn… vielleicht auf zu neuen Ufern, und den Kram nun mal hinter sich lassen?