Rekursiver Abstieg (englisch Recursive Descent) ist das verbreitetste Verfahren, um einen Parser von Hand zu schreiben: Für jedes Nichtterminal der Grammatik gibt es genau eine Funktion, und diese Funktionen rufen sich gegenseitig genau nach den Produktionen der Grammatik auf. Das Ergebnis ist ein Parser, der direkt lesbar, erweiterbar und leicht zu debuggen ist — deshalb setzen ihn so unterschiedliche Projekte wie Python, Go, Rust oder der GCC-C++-Compiler ein.
Wie der rekursive Abstieg funktioniert
Man startet mit der Grammatik in EBNF-Notation und schreibt pro Nichtterminal eine Funktion. Für die Grammatik
expr → term (('+' | '-') term)*
term → factor (('*' | '/') factor)*
factor → NUMBER | '(' expr ')'entstehen drei Funktionen: parse_expr ruft parse_term auf und verarbeitet dann in einer Schleife Plus- und Minuszeichen, parse_term analog für Mal und Geteilt, parse_factor liest eine Zahl oder erwartet nach einer öffnenden Klammer ein expr. Jeder Schritt prüft ein Token (das Lookahead-Symbol) und wandert dann einen Schritt weiter — genau das Verhalten eines LL(1)-Parsers. Der rekursive Abstieg ist also die praktische Implementierung der LL-Idee; die FIRST/FOLLOW-Theorie erklärt, warum die Grammatik bestimmte Formen braucht.
Grenzen und ihre Lösung
- Linksrekursion ist tabu: Eine Regel A → A β würde die Funktion endlos sich selbst aufrufen lassen. Die Grammatik muss zuerst umgeformt werden (Rechtsrekursion oder Schleifen).
- Gemeinsame Präfixe: Rufen zwei Alternativen dieselbe Funktion zuerst auf, ist die Entscheidung nicht deterministisch — Linksfaktorisierung hilft.
- Backtracking-Variante: Eine naive Version probiert alle Alternativen aus und setzt bei Misserfolg zurück. Das ist einfach, kann aber exponentiell werden; in der Praxis parsen die meisten Hand-Parser deterministisch mit ein bis zwei Token Vorausschau.
Ausdrücke mit Vorrang parsen
Für arithmetische und logische Ausdrücke mit Operator-Vorrang (etwa „2 + 3 * 4“) gibt es zwei bewährte Muster: geschachtelte Ebenen wie im Beispiel oben (jede Vorrangstufe eine Funktionsebene) oder einen Pratt-Parser, der jedem Operator eine Bindungsstärke zuordnet und die Hierarchie über eine Tabelle steuert. Beide vermeiden eine vollständig linksrekursive Grammatik und liefern denselben Syntaxbaum.
Warum so beliebt?
Der rekursive Abstieg benötigt keine Generator-Toolchain, produziert kontextbezogene Fehlermeldungen („erwartet ')' in Zeile 7“) und lässt sich beliebig erweitern: Semantische Aktionen, AST-Aufbau oder symbolische Tabellen können direkt in die Funktionen eingebaut werden. Die Nachteile — Grammatik-Einschränkungen und das Verbot der Linksrekursion — wiegen für handgeschriebene Parser meist gering. Wer maximale Grammatik-Mächtigkeit braucht, weicht auf LR-Parser mit Generator aus. Zusammen mit der lexikalischen Analyse und der anschließenden semantischen Analyse bildet der Parser das Herzstück jedes Compilers und Interpreters.