Parser und Interpreter für eine kleine Sprache
Verfasst: Mittwoch 25. Juni 2008, 12:29
Inspiriert durch diesen Artikel habe ich mich ebenfalls an der Aufgabe versucht. Mein Interpreter ist prinzipbedingt effizienter und ich brauche 10 Zeilen weniger. Daher möchte ihn hier mit stolzgeschwellter Brust vorstellen :)
Statt des traditionellen Ansatzes mit einem Scanner und einem handgeschriebenen rekursiv absteigendem LL(1)-Parser benutze ich Parser-Kombinatoren und ein bisschen Metaprogrammierung, damit das ganze netter aussieht. (Quält ein bisschen codeBB, weil viel Code folgt, sorry)
Ein Parser ist für mich eine Funktion, die einen String bekommt und zurückliefert, ob sie eine Zeichenfolge am Stringanfang erkannt hat. In diesem Fall liefert sie ein Tupel mit der erkannten Zeichenfolge sowie dem restlichen String zurück. Andernfalls liefert sie das leere Tupel.
Die Theorie kennt einige triviale Parser, die vielleicht zur Verdeutlichung des Prinzips interessant sind. Der folgende Parser `p` erkennt nichts:
Der nächste Parser erkennt ein beliebiges Zeichen:
Möchte man einen Parser haben, der ein definierte Zeichenfolge erkennt, diese aber nicht fest verdrahten, braucht man eine Funktion, die eine Parserfunktion bauen kann:
`token("if")` ist dann ein Parser, der ein `if` im Eingabestring erkennt.
Derartige Parser lassen sich kombinieren. Möchte ich einen Parser haben, der `if` oder `while` erkennen kann, baue ich mir zwei Parser für die beiden Schlüsselworte und kombiniere die mit Hilfe eines dritten Parsers, z.B. so:
Mit wenigen derartigen Parserkombinatoren kann man nicht nur reguläre Ausdrücke nachbilden, sondern auch kontextfreie Grammatiken. Und das will ich ausnutzen. So sieht meine Grammatik für die zu übersetzende Sprache aus:
Mein grundlegender Parser ist `Regexp`, der (hauptsächlich aus Effizienzgründen) Pythons reguläre Ausdrücke benutzt, um einen Teilstring zu erkennen. Er schluckt auch gleich noch führende Leerzeichen, die ich in meiner Sprache nicht brauche:
Die String-Literale übersetze ich automatisch in `Regexp`-Varianten:
Der `Sequence`-Parser reiht die übergebenen Parser hintereinander. In einer (E)BNF-Grammatik ist dies ein impliziter Operator:
Der `OneOf`-Parser ist erfolgreich, sobald der erste der übergebenen Parser erfolgreich ist. Diese Funktion wird normalerweise als `|`-Operator aufgeschrieben (PEGs nutzen ein `/`, um anzudeuten, dass die Auswahl nicht beliebig ist sondern der erste passende Teilausdruck gewinnt, das sei aber hier egal):
`ListOf` entspricht dem `*`-Operator. Dieser Parser schlägt niemals fehlt, sondern liefert immer eine Liste mit den erkannten Teilausdrücken, die durch den übergebenen Parser beschrieben werden:
Zwar sind meine Ausdrücke jetzt syntaktisch korrektes Python, doch die Parser sind rekursiv und das ganze lässt sich so nicht ausführen. Dies lässt sich durch das Einführen einer Indirektionsebene lösen, macht das ganze aber nicht lesbarer.
Daher habe ich mich dafür entschieden, die Parser als doc-Strings in speziellen Funktionen abzulegen. Alle Funktionsnamen beginnen mit `p_`, damit ich sie leichter finde. Der Funktionsrumpf definiert, was mit dem erkannten Teilausdruck passieren soll. Ein Beispiel macht es hoffentlich klarer:
Der `Sequence`-Parser liefert eine Liste mit 4 Elementen. Diese wird dann der Funktion als Parameter `r` übergeben und ich liefere ein Tupel bestehend aus dem Namen `e_if_stmt` (dazu später mehr) und den beiden relevanten Teilausdrücken zurück. Das `if` und das `end` sind ja nur syntaktischer Zucker und für den abstrakten Syntaxbaum (AST) nicht notwendig. Dort muss ich nur wissen, wie der Knoten heißen soll, um daran dann fest zu machen, wie ich den Knoten auswerte.
Die Parser-Funktionen aus dem Modul herauszusuchen und zu verarbeiten ist erstaunlich kompakt. Ich nutze dazu eine `Parser`-Klasse, der ich später erst den eigentlichen Parser setze, die aber schon mal existiert, um in anderen Parsern referenziert werden zu können. Deren `__call__`-Methode kümmert sich auch darum, die eigentliche Parser-Funktion aufzurufen, die den AST baut.
Hier ist jetzt mein kompletter Parser inklusive Scanner:
Häßlich ist die Verarbeitung in `p_expression`, wo ich einen Ausdruck der Form `[t1, [[op1, t2], [op2, t3], ...]]` in eine linksassoziative Struktur von Binäroperationen bringen muss. Eine gute Parserkombinator-Bibliothek hätte dafür einen fertigen Parser, doch den hinzuzufügen wäre aufwendiger gewesen als meine lokale Funktion `left`. Leider kann man die linksassoziativen Ausdrücke nicht anders aufschreiben, da Parsing Expression Grammars (PEGs), so wie ich sie hier nutze, genau wie LL(k)-Parser keine Linksrekursion erlauben.
Aus etwas wie `1+2-3` wird jetzt `(e_sub, (e_add, (e_lit, 1), (e_lit, 2)), (e_lit, 3))`.
Das ist ein waschechter AST und kann jetzt wie folgt ausgewertet werden:
Man hätte auch pro Knotentyp je eine Klasse benutzen können, doch das ist schwergewichtiger als mein "Mikrorahmenwerk" namens `do` zum einfachen Dispatch über den AST.
In weniger als 150 Zeilen (50 davon sind wiederverwendbar) kann ich jetzt die neue Sprache verstehen und auswerten:
Man könnte jetzt einen Parser für EBNF-artige Regeln bauen, um dann die Regeln nicht mehr direkt als Python-Ausdrucke sondern als EBNF anzugeben. Dafür kann man natürlich das Parserrahmenwerk benutzen. Das könnte dann so aussehen:
Und wenn man schon so weit ist, kann man auch Teilausdrücke benennen, um nicht mehr mit doch etwas fehleranfälligen Indizes zu arbeiten:
Vielleicht lohnt es auch, die AST-Konstruktion direkt in die Grammatik zu ziehen. Ich erkläre `|` dabei auch als implizit, jede Zeile wird automatisch zu einer Alternative:
Der EBNF-Ansatz macht aber höher abstrahierende Parser wie z.B. für Listen, geklammerte Ausdrücke oder Strings mit Escape-Zeichen unmöglich. Ringt man sich im Gegensatz zu mir zu Klassen statt Funktionen zum Konstruieren von Parsern durch, kann man auch Pythons Operatoren als leichtgewichtige Alternative zu `Sequence` und `OneOf` nutzen. Ich bin mir aber gar nicht sicher, ob das so viel bringt. Angenommen, ich wollte noch Funktionen in meiner kleinen Sprache definieren, wäre doch folgendes nett:
Stefan
Statt des traditionellen Ansatzes mit einem Scanner und einem handgeschriebenen rekursiv absteigendem LL(1)-Parser benutze ich Parser-Kombinatoren und ein bisschen Metaprogrammierung, damit das ganze netter aussieht. (Quält ein bisschen codeBB, weil viel Code folgt, sorry)
Ein Parser ist für mich eine Funktion, die einen String bekommt und zurückliefert, ob sie eine Zeichenfolge am Stringanfang erkannt hat. In diesem Fall liefert sie ein Tupel mit der erkannten Zeichenfolge sowie dem restlichen String zurück. Andernfalls liefert sie das leere Tupel.
Die Theorie kennt einige triviale Parser, die vielleicht zur Verdeutlichung des Prinzips interessant sind. Der folgende Parser `p` erkennt nichts:
Code: Alles auswählen
def p1(s): return ()
Code: Alles auswählen
def p2(s): return s[0], s[1:]
Code: Alles auswählen
def token(t):
def p(s):
return t, s[len(t):] if s.startswith(t) else ()
return p
Derartige Parser lassen sich kombinieren. Möchte ich einen Parser haben, der `if` oder `while` erkennen kann, baue ich mir zwei Parser für die beiden Schlüsselworte und kombiniere die mit Hilfe eines dritten Parsers, z.B. so:
Code: Alles auswählen
def alt(p1, p2):
def p(s):
result = p1(s)
if result: return result
return p2(s)
return p
if_or_while = alt(token('if'), token('while')
Code: Alles auswählen
statements = ListOf(OneOf(ifelse_stmt, if_stmt, while_stmt, print_stmt, set_stmt))
ifelse_stmt = Sequence('if', condition, statements, 'else', statements, 'end')
if_stmt = Sequence('if', condition, statements, 'end')
while_stmt = Sequence('while', condition, statements, 'end')
print_stmt = Sequence('print', expression)
set_stmt = Sequence(label, '=', expression)
condition = Sequence(expression, OneOf('==', '!='), expression)
expression = Sequence(term, ListOf(Sequence(OneOf('+', '-'), term)))
term = OneOf(number, variable)
variable = label
label = Regexp(r'\w+')
number = Regexp(r'\d+')
Code: Alles auswählen
def Regexp(r):
r = re.compile("(?:\s*)(" + r + ")")
def p(s):
m = r.match(s)
return m.group(1), s[m.end(1):] if m else ()
return p
Code: Alles auswählen
def tokenize(parsers):
return [Regexp(re.escape(p)) if type(p) is str else p for p in parsers]
Code: Alles auswählen
def Sequence(*parsers):
parsers = tokenize(parsers)
def p(s):
l = []
for p in parsers:
result = p(s)
if result is (): return ()
l.append(result[0])
s = result[1]
return l, s
return p
Code: Alles auswählen
def OneOf(*parsers):
parsers = tokenize(parsers)
def p(s):
for p in parsers:
result = p(s)
if result: return result
return ()
return p
Code: Alles auswählen
def ListOf(parser):
def p(s):
l = []
while True:
result = parser(s)
if result is (): return l, s
l.append(result[0])
s = result[1]
return p
Daher habe ich mich dafür entschieden, die Parser als doc-Strings in speziellen Funktionen abzulegen. Alle Funktionsnamen beginnen mit `p_`, damit ich sie leichter finde. Der Funktionsrumpf definiert, was mit dem erkannten Teilausdruck passieren soll. Ein Beispiel macht es hoffentlich klarer:
Code: Alles auswählen
def p_if_stmt(r):
"Sequence('if', condition, statements, 'end')"
return e_if_stmt, r[1], r[2]
Die Parser-Funktionen aus dem Modul herauszusuchen und zu verarbeiten ist erstaunlich kompakt. Ich nutze dazu eine `Parser`-Klasse, der ich später erst den eigentlichen Parser setze, die aber schon mal existiert, um in anderen Parsern referenziert werden zu können. Deren `__call__`-Methode kümmert sich auch darum, die eigentliche Parser-Funktion aufzurufen, die den AST baut.
Code: Alles auswählen
def setup(dct):
parsers = [n for n in dct.keys() if n.startswith("p_")]
for p in parsers: dct[p[2:]] = Parser(dct[p])
for p in parsers: dct[p[2:]].p = eval(dct[p].__doc__)
class Parser(object):
def __init__(self, f): self.f = f
def __call__(self, s):
result = self.p(s)
return (self.f(result[0]) or result[0], result[1]) if result else ()
Code: Alles auswählen
def p_statements(r):
"ListOf(OneOf(ifelse_stmt, if_stmt, while_stmt, print_stmt, set_stmt))"
return e_statements, r
def p_ifelse_stmt(r):
"Sequence('if', condition, statements, 'else', statements, 'end')"
return e_ifelse_stmt, r[1], r[2], r[4]
def p_if_stmt(r):
"Sequence('if', condition, statements, 'end')"
return e_if_stmt, r[1], r[2]
def p_while_stmt(r):
"Sequence('while', condition, statements, 'end')"
return e_while_stmt, r[1], r[2]
def p_print_stmt(r):
"Sequence('print', expression)"
return e_print_stmt, r[1]
def p_set_stmt(r):
"Sequence(label, '=', expression)"
return e_set_stmt, r[0], r[2]
def p_condition(r):
"Sequence(expression, OneOf('==', '!='), expression)"
return e_eq if r[1] == '==' else e_neq, r[0], r[2]
Code: Alles auswählen
def p_expression(r):
"Sequence(term, ListOf(Sequence(OneOf('+', '-'), term)))"
def op(op, l, r):
return e_add if op == '+' else e_sub, l, r
def left(lhs, seq):
return left(op(seq[0][0], lhs, seq[0][1]), seq[1:]) if seq else lhs
return left(r[0], r[1])
def p_term(r):
"OneOf(number, variable)"
return r
def p_variable(r):
"label"
return e_var, r
def p_label(r):
"Regexp(r'\w+')"
return r
def p_number(r):
"Regexp(r'\d+')"
return e_lit, int(r)
setup(locals())
Aus etwas wie `1+2-3` wird jetzt `(e_sub, (e_add, (e_lit, 1), (e_lit, 2)), (e_lit, 3))`.
Das ist ein waschechter AST und kann jetzt wie folgt ausgewertet werden:
Code: Alles auswählen
def do(a): return a[0](*a[1:])
bindings = {}
def e_statements(stmts):
for stmt in stmts: do(stmt)
def e_ifelse_stmt(c, t, e):
if do(c): do(t)
else: do(e)
def e_if_stmt(c, t):
if do(c): do(t)
def e_while_stmt(c, stmts):
while do(c): do(stmts)
def e_print_stmt(expr): print do(expr)
def e_set_stmt(name, expr): bindings[name] = do(expr)
def e_eq(a, b): return do(a) == do(b)
def e_neq(a, b): return do(a) != do(b)
def e_add(a, b): return do(a) + do(b)
def e_sub(a, b): return do(a) - do(b)
def e_var(name): return bindings[name]
def e_lit(v): return v
In weniger als 150 Zeilen (50 davon sind wiederverwendbar) kann ich jetzt die neue Sprache verstehen und auswerten:
Code: Alles auswählen
do(statements("print 3+4 a=7 print a-1 if a != 6 print 1 end")[0])
Code: Alles auswählen
def p_condition(r):
"expression ('=='|'!=') expression"
return e_eq if r[1] == '==' else e_neq, r[0], r[2]
Code: Alles auswählen
def p_condition(r):
"expression:e1 ('=='|'!='):op expression:e2"
return e_eq if r.op == '==' else e_neq, r.e1, r.e2
Code: Alles auswählen
def p_condition(r):
"""
expression:e1 '==' expression:e2 { return e_eq, r.e1, r.e2 }
expression:e2 '!=' expression:e2 { return e_neq, r.e1, r.e2 }
"""
Code: Alles auswählen
def p_def_stmt(r):
"Sequence('def', label, InParens(CommaSeparatedList(label)), InCurlyBraces(statements))"
return e_def_stmt, r[1], r[2], r[3]
def p_call(r):
"Sequence(label, InParens(CommaSeparatedList(expression)))"
return e_call, r[0], r[1]