Rekursiver Abstieg
# Rekursiver Abstieg

Rekursiver Abstieg (englisch: recursive descent) ist eine Technik aus dem Compilerbau, die auf direkte Weise (d. h. ohne Tabelle) einen Top-Down-Parser implementiert. Sie zeichnet sich durch geringe Komplexität aus; das Verwenden eines Parsergenerators ist nicht nötig.

Bei diesem Verfahren wird jedes Nichtterminalsymbol durch jeweils eine eigene Prozedur behandelt, welche die Produktionsregeln zu diesem Symbol implementiert. Erlauben die Produktionsregeln eine Rekursion, dann rufen sich daher auch diese Prozeduren wechselseitig rekursiv auf.

Der rekursive Abstieg kann bei Bedarf mit Backtracking arbeiten; wenn eine LL(k)-Grammatik für die zu parsende Sprache verwendet wird, ist das jedoch nicht erforderlich. Unüberlegte Verwendung von Backtracking kann zudem zu exponentiellem Laufzeitverhalten führen. Im Folgenden wird daher der häufige Fall LL(1) angenommen.

## Code für die Grammatikregeln eines Nichtterminalsymbols

Für jedes Nichtterminalsymbol der Grammatik wird eine Prozedur definiert. Wenn

    $A\to \alpha _{1}\,|\,\alpha _{2}\,|\,\ldots \,|\,\alpha _{n}$

alle Regeln mit $A$ auf der linken Seite sind, sieht die Prozedur $A$ in Pseudocode folgendermaßen aus:

Dabei gilt:

* lookahead ist das aktuelle Eingabezeichen (oder -token).
* $\mathrm {first} (T)$ ist die Menge der Terminalsymbole (oder Tokens), die am Anfang eines Wortes stehen können, das von einem der Wörter in der Menge $T$ erzeugt wurde.
* $\mathrm {follow} (A)$ ist die Menge der Terminalsymbole, die in einem vom Startsymbol erzeugten Wort direkt rechts von $A$ stehen können.
* $C_{i}$ ist der Code für das Parsen von $\alpha _{i}$.

Die $\mathrm {follow}$-Mengen müssen hier einbezogen werden, weil $\mathrm {first} (T)$ das leere Wort enthalten kann; siehe LL(k)-Grammatik.

## Code für eine Folge von Grammatiksymbolen

Für $\alpha _{i}=X_{1}\ldots X_{m}$ (wobei die $X_{j}$ Terminale und/oder Nichtterminale sein können) besteht $C_{i}$ aus den Code-Abschnitten für $X_{1},\ldots ,X_{m}$ in derselben Reihenfolge.

Der Code für ein einzelnes Symbol $X_{j}$ sieht wie folgt aus:

* Falls $X_{j}$ Terminal ist:
* Falls $X_{j}$ Nichtterminal ist:

Dabei ist GetSymbol eine Funktion, die das nächste Eingabezeichen (oder -token) liefert.

## Beispiel

Für die Arithmetik lässt sich die folgende formale Grammatik in EBNF angeben.

Es folgt ein rekursiver Abstieg in Python, der eine syntaktische Analyse vornimmt und dabei einen abstrakten Syntaxbaum erstellt. Zuvor zerlegt ein lexikalischer Scanner scan die Eingabe in eine Liste von Tokens. Im Nachhinein wird noch mit evaluate eine rekursive Auswertung des abstrakten Syntaxbaumes demonstriert.

