Parser und Interpreter für eine kleine Sprache

[sma]

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:

Code: Alles auswählen

def p1(s): return ()

Der nächste Parser erkennt ein beliebiges Zeichen:

Code: Alles auswählen

def p2(s): return s[0], s[1:]

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:

Code: Alles auswählen

def token(t):
    def p(s):
        return t, s[len(t):] if s.startswith(t) else ()
    return p

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

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

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:

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+')

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:

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

Die String-Literale übersetze ich automatisch in `Regexp`-Varianten:

Code: Alles auswählen

def tokenize(parsers):
    return [Regexp(re.escape(p)) if type(p) is str else p for p in parsers]

Der `Sequence`-Parser reiht die übergebenen Parser hintereinander. In einer (E)BNF-Grammatik ist dies ein impliziter Operator:

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

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

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

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

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

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:

Code: Alles auswählen

def p_if_stmt(r):
    "Sequence('if', condition, statements, 'end')"
    return e_if_stmt, r[1], r[2]

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.

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

Hier ist jetzt mein kompletter Parser inklusive Scanner:

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

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:

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

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:

Code: Alles auswählen

do(statements("print 3+4 a=7 print a-1 if a != 6 print 1 end")[0])

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:

Code: Alles auswählen

def p_condition(r):
    "expression ('=='|'!=') expression"
    return e_eq if r[1] == '==' else e_neq, r[0], r[2]

Und wenn man schon so weit ist, kann man auch Teilausdrücke benennen, um nicht mehr mit doch etwas fehleranfälligen Indizes zu arbeiten:

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

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:

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 }
    """

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:

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]

Stefan

[mitsuhiko]

Das mit den Docstrings ist eine ziemlich gute Idee. Ich hab neulich mal für Babel einen gettext-pluralize-expression compiler geschrieben der also ein bestimmes Unterset von C-Expressions in eine Python Funktion kompiliert, damit man die für jeden ngettext aufruf mitaufrufen kann.

Hat allerdings ziemlich viel Code für wie wenig der tut Außerdem ist er etwas unleserlich. Müsste glatt mal versuchen ob man mit einem so einem Parsergenerator weniger Code braucht.

Solltest du Lust haben damit rumzuspielen, der Code sieht momentan so aus: http://paste.pocoo.org/show/77778

[Leonidas]

Das mit den Docstrings ist eine ziemlich gute Idee.

Sowas ähnliches nutzt der Parsergenerator von PLY schon seit längerem, was eigentlich sehr praktisch ist.

[mitsuhiko]

Das mit den Docstrings ist eine ziemlich gute Idee.

Sowas ähnliches nutzt der Parsergenerator von PLY schon seit längerem, was eigentlich sehr praktisch ist.

Schon klar, das hat sogar Pyrr gemacht oder wie Modelnine's Parsergenerator heißt den ich da mal genutzt habe. Aber was ich an smas Lösung toll finde ist, dass es einfach nur ein eval() ist und nicht irgendeine Form einer Grammatik-DSL (BNF etc.)

Reply auf den Thread geht mal wieder ganz flott, danke CodeBB...

[sma]

Solltest du Lust haben damit rumzuspielen, der Code sieht momentan so aus: http://paste.pocoo.org/show/77778 :D

Hm, dein Code ist schon sehr kompakt. Da komme ich inklusive meiner Parserkombinatoren nicht gegen an. Dennoch habe ich mir mal das erste plural.y, das ich finden konnte, genommen und da folgende Grammatik abgeleitet:

Code: Alles auswählen

if_exp  = Seq(or_exp, '?', if_exp, ':', if_exp)
or_exp  = LAB(and_exp, '||')
and_exp = LAB(eq_exp, '&&')
eq_exp  = LAB(cmp_exp, OneOf('==', '!='))
cmp_exp = LAB(add_exp, OneOf('<', '<=', '>=', '>'))
add_exp = LAB(mul_exp, OneOf('+', '-'))
mul_exp = LAB(not_exp, OneOf('*', '/', '%'))
not_exp = OneOf(Seq('!', prim), prim)
prim    = OneOf('n', number, InParens(if_exp))
number  = Regexp(r'\d+')

`LAB` steht für "left associative binary operation sequence" und bekommt je einen Parser für Operand und Operator übergeben. Ich bin mir nicht ganz sicher, was der Parser für ein AST-Fragment liefern sollte. Damit's elegant wird, sollte er seine "action function" für jedes erkannte Tupel aus Operanden und Operator aufrufen. Das kann ich dann nicht mehr mit meinem bisherigen Rahmenwerk abbilden.

Da nur einige Operatoren andere Namen in Python als in C haben, sonst aber alles gleich ist, ist es wohl am einfachsten, direkt Strings zu erzeugen. Zur Sicherheit erzeuge ich überall Kammern, um die Rangfolge der Operatoren explizit zu machen:

Code: Alles auswählen

def p_if_exp(r):
    "Seq(or_exp, '?', if_exp, ':', if_exp)"
    return "(%s if %s else %s)" % (r[2], r[0], r[4])
    
def p_or_exp(r):
    "LAB(and_exp, '||')"
    return "(%s or %s)" % (r[0], r[2])
...
def p_add_exp(r):
    "LAB(and_exp, OneOf('+', '-'))"
    return "(%s %s %s)" % (r[0], r[1], r[2])
...
def not_exp(r):
    "OneOf(Seq('!', prim), prim)"
    return "(not %s)" % r[1] if type(r) is list else r

def prim(r):
    "OneOf('n', number, InParens(if_exp))"

Übrigens, dein Parser erlaubt auch '&' und '|' als Operatoren und beliebige Namen statt nur 'n' wie mein Vorbild.

Stefan