Rekursiver Abstieg

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.

Inhaltsverzeichnis

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({α1}follow(A)) then
     C1
   else if lookahead in first({α2}follow(A)) then
     C2
   ...
   else if lookahead in first({αn}follow(A)) then
     Cn
   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.
  • Ci ist der Code für das Parsen von α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 Xj Terminale und/oder Nichtterminale sein können) besteht Ci aus den Code-Abschnitten für X_1, \ldots, X_m in derselben Reihenfolge.

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

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

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

Siehe auch

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.

Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Recursive Descent Parser — Rekursiver Abstieg (englisch: Recursive descent parser, RDP) ist eine Technik aus dem Compilerbau, die auf direkte Weise einen LL Parser implementiert. Dabei entsprechen die Nichtterminalsymbole der Grammatik Funktionsaufrufen. Siehe auch Parser… …   Deutsch Wikipedia

  • Rekursionsanfang — Dieser Artikel erläutert die Technik der rekursiven Definition; zum Begriff rekursive Menge siehe entscheidbar. Als Rekursion (lat. recurrere „zurücklaufen“) bezeichnet man die Technik in Mathematik, Logik und Informatik, eine Funktion durch sich …   Deutsch Wikipedia

  • Rekursionsformel — Dieser Artikel erläutert die Technik der rekursiven Definition; zum Begriff rekursive Menge siehe entscheidbar. Als Rekursion (lat. recurrere „zurücklaufen“) bezeichnet man die Technik in Mathematik, Logik und Informatik, eine Funktion durch sich …   Deutsch Wikipedia

  • Rekursionsschritt — Dieser Artikel erläutert die Technik der rekursiven Definition; zum Begriff rekursive Menge siehe entscheidbar. Als Rekursion (lat. recurrere „zurücklaufen“) bezeichnet man die Technik in Mathematik, Logik und Informatik, eine Funktion durch sich …   Deutsch Wikipedia

  • Rekursionstiefe — Dieser Artikel erläutert die Technik der rekursiven Definition; zum Begriff rekursive Menge siehe entscheidbar. Als Rekursion (lat. recurrere „zurücklaufen“) bezeichnet man die Technik in Mathematik, Logik und Informatik, eine Funktion durch sich …   Deutsch Wikipedia

  • Rekursiv — Dieser Artikel erläutert die Technik der rekursiven Definition; zum Begriff rekursive Menge siehe entscheidbar. Als Rekursion (lat. recurrere „zurücklaufen“) bezeichnet man die Technik in Mathematik, Logik und Informatik, eine Funktion durch sich …   Deutsch Wikipedia

  • Rekursive Endlosschleife — Dieser Artikel erläutert die Technik der rekursiven Definition; zum Begriff rekursive Menge siehe entscheidbar. Als Rekursion (lat. recurrere „zurücklaufen“) bezeichnet man die Technik in Mathematik, Logik und Informatik, eine Funktion durch sich …   Deutsch Wikipedia

  • Rekursive Funktion — Dieser Artikel erläutert die Technik der rekursiven Definition; zum Begriff rekursive Menge siehe entscheidbar. Als Rekursion (lat. recurrere „zurücklaufen“) bezeichnet man die Technik in Mathematik, Logik und Informatik, eine Funktion durch sich …   Deutsch Wikipedia

  • Rekursivität — Dieser Artikel erläutert die Technik der rekursiven Definition; zum Begriff rekursive Menge siehe entscheidbar. Als Rekursion (lat. recurrere „zurücklaufen“) bezeichnet man die Technik in Mathematik, Logik und Informatik, eine Funktion durch sich …   Deutsch Wikipedia

  • Coco/R — Maintainer: Institut für Systemsoftware, Johannes Kepler Universität Linz Kategorie: Parser Generator Lizenz: GNU GPL http://ssw.jku.at/Coco/ …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”