Rekursiver Abstieg

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 angenommen.

Code für die Grammatikregeln eines Nichtterminalsymbols[Bearbeiten | Quelltext bearbeiten]

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

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

 proc ()
   if lookahead in  then
     
   else if lookahead in  then
     
   ...
   else if lookahead in  then
     
   else
     error

Dabei gilt:

  • lookahead ist das aktuelle Eingabezeichen (oder -token).
  • ist die Menge der Terminalsymbole (oder Tokens), die am Anfang eines Wortes stehen können, das von einem der Wörter in der Menge erzeugt wurde.
  • ist die Menge der Terminalsymbole, die in einem vom Startsymbol erzeugten Wort direkt rechts von stehen können.
  • ist der Code für das Parsen von .

Die -Mengen müssen hier einbezogen werden, weil das leere Wort enthalten kann; siehe LL(k)-Grammatik.

Code für eine Folge von Grammatiksymbolen[Bearbeiten | Quelltext bearbeiten]

Für (wobei die Terminale und/oder Nichtterminale sein können) besteht aus den Code-Abschnitten für in derselben Reihenfolge.

Der Code für ein einzelnes Symbol sieht wie folgt aus:

  • Falls Terminal ist:
 if lookahead =  then
   lookahead := GetSymbol()
 else
   error
  • Falls Nichtterminal ist:
 ()

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

Literatur[Bearbeiten | Quelltext bearbeiten]

  • 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.