Pratt-Parser: Ausdrücke mit Binding Power analysieren

Pratt-Parser (auch Top Down Operator Precedence genannt) ist ein handgeschriebenes Parsing-Verfahren für Ausdrücke, das die Operator-Präzedenz und Assoziativität direkt in Zahlen kodiert — statt sie über eine umgeschriebene Grammatik oder einen Parser-Generator zu regeln. Entwickelt wurde es von Vaughan Pratt im Jahr 1973 (Paper „Top Down Operator Precedence“, ACM POPL). Es gehört zu den Top-down-Verfahren, wird aber meist als eigenständige Technik neben dem rekursiven Abstieg behandelt.

Die Grundidee: Binding Power

Jeder Operator erhält eine Zahl, seine Binding Power (Bindungsstärke). Beispiel:

+  hat  Binding Power 10
*  hat  Binding Power 20
^  hat  Binding Power 30 (rechts-assoziativ)

Beim Parsen von 1 + 2 * 3 sieht der Parser nach der 1 das + mit Binding Power 10. Danach wird der rechte Operand mit einer Mindest-Binding-Power von 10 geparst. Das 2 * 3 bindet stärker (20 > 10) und wird daher als Einheit zusammengefasst — genau die gewünschte Operator-Präzedenz, ohne eine einzige Grammatikregel.

nud und led: Präfix- und Infix-Behandlung

Pratt unterteilt Token in zwei Verarbeitungsfunktionen:

  • nud (null denotation): behandelt ein Token ohne linken Operanden, also Zahlen, Variablen und Präfix-Operatoren wie das Minus in -5.
  • led (left denotation): behandelt ein Token mit linkem Operanden, also Infix-Operatoren wie +, * oder Funktionsaufrufe.

Der Kernalgorithmus ist überraschend kurz. In Pseudocode:

parse_expression(min_bp):
    token = next_token()
    left = token.nud()
    while next_token_bp() > min_bp:
        op = next_token()
        left = op.led(left)
    return left

Links- und rechts-assoziativ

Die Assoziativität steckt in der Detailfrage, ob beim Schleifendurchlauf >= oder > verglichen und ob die Binding Power des rechten Operanden um 1 erhöht wird. 2 + 3 + 4 soll als (2 + 3) + 4 gebildet werden (links-assoziativ), während 2 ^ 3 ^ 4 als 2 ^ (3 ^ 4) entstehen soll (rechts-assoziativ).

Vorteile und Einsatzgebiete

  • Kein Parser-Generator nötig: Der Parser ist ein überschaubares handgeschriebenes Stück Code.
  • Leicht erweiterbar: Ein neuer Operator braucht nur eine Binding Power und eine led-Funktion.
  • Gute Fehlermeldungen möglich, weil der Code vollständig unter eigener Kontrolle bleibt.
  • Sehr kompakt für Ausdrücke — ideal in Interpretern, Formel-Engines und kleinen Compilern.

Bekannt wurde die Technik vor allem durch Bob Nystroms Artikel „Pratt Parsers: Expression Parsing Made Easy“ (2011). Sie ist eine beliebte Wahl, wenn ein Parser von Hand geschrieben wird — als Alternative zum klassischen rekursiven Abstieg. Auch der Shunting-Yard-Algorithmus löst ein ähnliches Problem (Infix-Ausdrücke) und erzeugt dabei Postfix- statt Struktur.

Verwandte Compiler-Grundlagen: lexikalische Analyse, Syntaxbaum, LL-Parser, LR-Parser.