Rekursiver Abstieg

Rekursiver Abstieg (englisch: recursive descent) ist eine Technik aus dem Compilerbau, die auf direkte Weise (d. h. ohne Tabelle) einen LL-Parser implementiert.

Voraussetzung ist eine LL(k)-Grammatik für die zu parsende Sprache. Im Folgenden wird der häufige Fall $k=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:

 proc $A$()
   if lookahead in $first(\{\alpha_1\}follow(A))$ then
     $C_1$
   else if lookahead in $first(\{\alpha_2\}follow(A))$ then
     $C_2$
   ...
   else if lookahead in $first(\{\alpha_n\}follow(A))$ then
     $C_n$
   else
     error

Dabei gilt:

• lookahead ist das aktuelle Eingabezeichen (oder -token).
• $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.
• $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 $follow$-Mengen müssen hier einbezogen werden, weil $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:

 if lookahead = $X_j$ then
   lookahead := GetSymbol()
 else
   error

• Falls $X_j$ Nichtterminal ist:

 $X_j$()

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

Siehe auch

• Parser
• Rekursion

Literatur

• Aho, Alfred V., Sethi, Ravi, and Ullman, Jeffrey D. (1988). Compilers — Principles, Techniques, and Tools. Addison-Wesley. Abschnitte 2.4 und 4.4, S. 45-46 und 188-189.