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 <math>k=1</math> angenommen.

Code für die Grammatikregeln eines Nichtterminalsymbols

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

<math>A \to \alpha_1 \,|\, \alpha_2 \,|\, \ldots \,|\, \alpha_n</math>

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

 proc <math>A</math>()
   if lookahead in <math>\mathrm{first}(\{\alpha_1\}\mathrm{follow}(A))</math> then
     <math>C_1</math>
   else if lookahead in <math>\mathrm{first}(\{\alpha_2\}\mathrm{follow}(A))</math> then
     <math>C_2</math>
   ...
   else if lookahead in <math>\mathrm{first}(\{\alpha_n\}\mathrm{follow}(A))</math> then
     <math>C_n</math>
   else
     error

Dabei gilt:

• lookahead ist das aktuelle Eingabezeichen (oder -token).
• <math>\mathrm{first}(T)</math> ist die Menge der Terminalsymbole (oder Tokens), die am Anfang eines Wortes stehen können, das von einem der Wörter in der Menge <math>T</math> erzeugt wurde.
• <math>\mathrm{follow}(A)</math> ist die Menge der Terminalsymbole, die in einem vom Startsymbol erzeugten Wort direkt rechts von <math>A</math> stehen können.
• <math>C_i</math> ist der Code für das Parsen von <math>\alpha_i</math>.

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

Code für eine Folge von Grammatiksymbolen

Für <math>\alpha_i = X_1 \ldots X_m</math> (wobei die <math>X_j</math> Terminale und/oder Nichtterminale sein können) besteht <math>C_i</math> aus den Code-Abschnitten für <math>X_1, \ldots, X_m</math> in derselben Reihenfolge.

Der Code für ein einzelnes Symbol <math>X_j</math> sieht wie folgt aus:

• Falls <math>X_j</math> Terminal ist:

 if lookahead = <math>X_j</math> then
   lookahead := GetSymbol()
 else
   error

• Falls <math>X_j</math> Nichtterminal ist:

 <math>X_j</math>()

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

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.
• Aho, Alfred V., Sethi, Ravi, and Ullman, Jeffrey D. (2008). Compiler — Prinzipien, Techniken und Werkzeuge Pearson Studium. Abschnitte 2.4.2 und 4.4.1, S. 79-82 und 264-266.