Einen Parser von Hand schreiben (Recursive Descent)

In Agent im Loop (Teil 4) wich ein naiver String-Splitter einem echten Parser. Das Handwerk dahinter – Recursive Descent (rekursiver Abstieg) – ist erstaunlich überschaubar: Eine Grammatik beschreibt die Sprache, und für jede ihrer Regeln gibt es eine passende Funktion oder Methode.

Statt Würfelausdrücken nehmen wir hier einen kleinen Taschenrechner. Er soll verstehen, warum 2 + 3 * 4 den Wert 14 hat, (2 + 3) * 4 dagegen 20.

Grammatik zuerst

Bevor der erste Parser-Code entsteht, legen wir fest, welche Sprache er überhaupt verstehen soll:

expr   := term (('+' | '-') term)*
term   := factor (('*' | '/') factor)*
factor := zahl | '(' expr ')'

Ein expr besteht aus Termen, die mit + oder - verbunden sind. Ein term wiederum besteht aus Faktoren mit * oder /. Ein factor ist eine Zahl oder ein geklammerter Ausdruck.

Damit steckt die Operatorpräzedenz bereits in der Grammatik. Multiplikation und Division werden auf der term-Ebene verarbeitet, bevor die darüberliegende expr-Ebene Addition oder Subtraktion ausführt. Eine zusätzliche Regel wie „Mal vor Plus“ braucht der Parser nicht.

Was die Grammatik nicht beschreibt, akzeptieren wir auch nicht. Negative Zahlen, Dezimalzahlen oder Potenzen gehören in dieser kleinen Version also bewusst noch nicht zur Sprache.

Erst Tokens, dann Grammatik

Der Parser soll sich nicht mit einzelnen Zeichen und Whitespace beschäftigen müssen. Dafür gibt es vorher einen kleinen Tokenizer:

import re


TOKEN_RE = re.compile(r"\d+|[+\-*/()]|\s+")


def tokenize(text):
    tokens = []
    pos = 0

    for match in TOKEN_RE.finditer(text):
        if match.start() != pos:
            raise ValueError(
                f"Unerwartetes Zeichen: {text[pos:match.start()]!r}"
            )

        token = match.group()
        if not token.isspace():
            tokens.append(token)

        pos = match.end()

    if pos != len(text):
        raise ValueError(f"Unerwartetes Zeichen: {text[pos:]!r}")

    return tokens

Aus

2 + 3 * (4 - 1)

wird damit:

["2", "+", "3", "*", "(", "4", "-", "1", ")"]

Whitespace wird ignoriert, aber nicht einfach aus dem Eingabetext entfernt. Das ist ein wichtiger Unterschied. Würden wir vorher alle Leerzeichen löschen, würde aus der ungültigen Eingabe 2 3 einfach 23 werden.

Der Positionsabgleich erkennt außerdem Zeichen, für die es kein Token gibt:

2 + 3 % 4
      ^

finditer() würde % überspringen und beim nächsten bekannten Token weitermachen. Weil dessen Position dann nicht mehr zu pos passt, können wir genau dort abbrechen.

Recursive Descent: eine Methode pro Regel

Jetzt lässt sich die Grammatik fast Zeile für Zeile in Python übersetzen:

class Parser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.i = 0

    def parse(self):
        wert = self._expr()

        if self._peek() is not None:
            raise ValueError(f"Unerwartetes Token: {self._peek()!r}")

        return wert

    def _expr(self):
        wert = self._term()

        while self._peek() in ("+", "-"):
            op = self._next()
            rechts = self._term()

            if op == "+":
                wert += rechts
            else:
                wert -= rechts

        return wert

    def _term(self):
        wert = self._factor()

        while self._peek() in ("*", "/"):
            op = self._next()
            rechts = self._factor()

            if op == "*":
                wert *= rechts
            else:
                wert /= rechts

        return wert

    def _factor(self):
        token = self._next()

        if token == "(":
            wert = self._expr()

            if self._peek() != ")":
                raise ValueError("')' erwartet")

            self._next()
            return wert

        if token.isdigit():
            return int(token)

        raise ValueError(
            f"Zahl oder '(' erwartet, gefunden: {token!r}"
        )

    def _peek(self):
        if self.i >= len(self.tokens):
            return None

        return self.tokens[self.i]

    def _next(self):
        token = self._peek()

        if token is None:
            raise ValueError("Unerwartetes Ende der Eingabe")

        self.i += 1
        return token

Ein kleiner Wrapper reicht, um daraus unseren Rechner zu machen:

def berechne(text):
    return Parser(tokenize(text)).parse()

Jetzt funktionieren bereits verschachtelte Ausdrücke:

assert berechne("2 + 3 * 4") == 14
assert berechne("(2 + 3) * 4") == 20
assert berechne("10 - 2 - 3") == 5
assert berechne("2 * (3 + (4 * 5))") == 46

Warum die Präzedenz von selbst stimmt

Nehmen wir:

2 + 3 * 4

_expr() beginnt mit _term(). Dieser liest zunächst die 2. Danach sieht _expr() das + und fordert den nächsten vollständigen Term an.

Dieser zweite Aufruf von _term() bekommt:

3 * 4

und verarbeitet die Multiplikation vollständig. Erst dann erhält _expr() den Wert 12 zurück und addiert die vorherige 2.

Die Struktur des Codes folgt damit der Struktur der Grammatik:

_expr
 └─ _term
     └─ _factor

Je tiefer eine Operation in dieser Hierarchie verarbeitet wird, desto stärker bindet sie.

Linksassoziativität steckt in der Schleife

Präzedenz ist nur die halbe Geschichte. Bei mehreren Operatoren derselben Ebene muss auch klar sein, in welcher Richtung sie gruppiert werden.

Bei

10 - 2 - 3

erzeugt _expr() zunächst 10 - 2 und nimmt danach das Ergebnis für die nächste Subtraktion:

(10 - 2) - 3

Das Ergebnis ist 5.

Verantwortlich dafür ist die while-Schleife. Sie verarbeitet die Operatoren nacheinander von links nach rechts. Addition, Subtraktion, Multiplikation und Division sind damit linksassoziativ.

Bei einem rechtsassoziativen Operator wie Potenzierung würde die Grammatik anders aussehen. Vereinfacht etwa:

power := factor ('**' power)?

Die rechte Seite ruft wieder power auf. Dadurch würde

2 ** 3 ** 2

als

2 ** (3 ** 2)

interpretiert.

Klammern erzeugen die eigentliche Rekursion

Bisher könnte man sich fragen, was an diesem Parser überhaupt rekursiv sein soll. _expr() ruft _term() auf und _term() wiederum _factor(), aber keine dieser Methoden ruft direkt sich selbst auf.

Die Rekursion entsteht bei Klammern:

if token == "(":
    wert = self._expr()

Ein Faktor kann einen vollständigen neuen Ausdruck enthalten. Dieser Ausdruck kann wieder einen Faktor enthalten, der mit ( beginnt, der wiederum einen Ausdruck enthält:

2 * (3 + (4 * (5 - 1)))

Die Grammatik und der Python-Code folgen dabei derselben Struktur.

Warum parse() die Reste prüft

Es reicht nicht, irgendwann einen gültigen Ausdruck erkannt zu haben. Der Parser muss auch sicherstellen, dass danach nichts mehr übrig ist.

Ohne diese Prüfung:

if self._peek() is not None:
    raise ValueError(f"Unerwartetes Token: {self._peek()!r}")

könnte _expr() bei einer Eingabe wie

2 3

erfolgreich die 2 lesen und den Rest ignorieren.

Unser Tokenizer liefert stattdessen:

["2", "3"]

Nach dem ersten Ausdruck steht also noch "3" im Tokenstrom, und parse() lehnt die Eingabe ab.

Auch kaputte Klammern werden an der passenden Stelle entdeckt:

2 * (3 + 4

_factor() erwartet nach dem inneren Ausdruck ein ) und kann deshalb einen verständlicheren Fehler melden, statt später irgendwo aus dem Tritt zu geraten.

Parser und Evaluator in einem

Unser Beispiel baut keinen Syntaxbaum. Sobald _expr(), _term() oder _factor() eine Regel erkannt haben, berechnen sie direkt deren Wert.

Für einen kleinen Taschenrechner ist das angenehm kompakt. Parser und Auswertung sind damit allerdings fest miteinander verbunden.

Die Würfel-Engine aus der Serie geht einen Schritt weiter und baut zunächst einen AST, einen Abstract Syntax Tree. Aus

2 + 3 * 4

könnte vereinfacht etwa dieser Baum entstehen:

Add
├── Number(2)
└── Multiply
    ├── Number(3)
    └── Number(4)

Erst ein zweiter Schritt wertet diesen Baum aus.

Das lohnt sich, wenn die geparste Struktur später noch gebraucht wird: für mehrere Auswertungen, Transformationen, Optimierungen, bessere Fehlermeldungen oder eine andere Darstellung. Wenn nach dem Parsen nur ein einzelner Zahlenwert gebraucht wird, kann die direkte Auswertung völlig ausreichen.

Stolperfallen

Längere Tokens zuerst

Sobald die Sprache Operatoren aus mehreren Zeichen kennt, spielt die Reihenfolge in der Regex eine Rolle. Soll beispielsweise ** als eigenes Token erkannt werden, muss es vor * stehen:

r"\d+|\*\*|[+\-*/()]|\s+"

Andernfalls passen zwei einzelne * ebenfalls auf denselben Text.

Grammatik und Parser müssen zusammenpassen

Unary Minus ist in unserer Grammatik nicht vorgesehen:

-5 + 2

wird deshalb mit Absicht abgelehnt. Soll es erlaubt sein, muss die Grammatik erweitert werden, beispielsweise um:

factor := '-' factor | zahl | '(' expr ')'

Danach bekommt _factor() den entsprechenden Fall. Sonderbehandlungen irgendwo in _expr() einzubauen würde die Grammatik und ihre Implementierung dagegen auseinanderlaufen lassen.

Fehler nicht still übergehen

Ein Parser sollte entweder die vollständige Eingabe akzeptieren oder klar scheitern. Unbekannte Zeichen im Tokenizer und übrig gebliebene Tokens nach dem Parsen gehören deshalb beide geprüft.

Genau darin liegt ein großer Vorteil gegenüber einem schnell zusammengebauten String-Splitter: Die Syntax der erlaubten Sprache steht explizit da und ungültige Eingaben verschwinden nicht versehentlich zwischen ein paar split()-Aufrufen.

Weiterlesen

• Agent im Loop (Teil 4): Refactoring unter Testschutz

Sources: Wikipedia: Recursive descent parser, Python: re.