- 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
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
(wobei die Xj Terminale und/oder Nichtterminale sein können) besteht Ci aus den Code-Abschnitten für
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.