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]