www.wikidata.de-de.nina.az

Rekursiver Abstieg englisch recursive descent ist eine Technik aus dem Compilerbau die auf direkte Weise d h ohne Tabell

Rekursiver Abstieg

Rekursiver Abstieg (englisch: recursive descent) ist eine Technik aus dem Compilerbau, die auf direkte Weise (d. h. ohne Tabelle) einen Top-Down-Parser implementiert. Sie zeichnet sich durch geringe Komplexität aus; das Verwenden eines Parsergenerators ist nicht nötig.

Bei diesem Verfahren wird jedes Nichtterminalsymbol durch jeweils eine eigene Prozedur behandelt, welche die Produktionsregeln zu diesem Symbol implementiert. Erlauben die Produktionsregeln eine Rekursion, dann rufen sich daher auch diese Prozeduren wechselseitig rekursiv auf.

Der rekursive Abstieg kann bei Bedarf mit Backtracking arbeiten; wenn eine LL(k)-Grammatik für die zu parsende Sprache verwendet wird, ist das jedoch nicht erforderlich. Unüberlegte Verwendung von Backtracking kann zudem zu exponentiellem Laufzeitverhalten führen. Im Folgenden wird daher der häufige Fall LL(1) angenommen.

Code für die Grammatikregeln eines Nichtterminalsymbols 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

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.

Beispiel Bearbeiten

Für die Arithmetik lässt sich die folgende formale Grammatik in EBNF angeben. 

Produktionsregeln in EBNF atom = number | "(" expression ")"; power = atom ["^" negation]; negation = ["-"] power; multiplication = negation {("*" | "/") negation}; addition = multiplication {("+" | "-") multiplication}; expression = addition;

Es folgt ein rekursiver Abstieg in Python, der eine syntaktische Analyse vornimmt und dabei einen abstrakten Syntaxbaum erstellt. Zuvor zerlegt ein lexikalischer Scanner scan die Eingabe in eine Liste von Tokens. Im Nachhinein wird noch mit evaluate eine rekursive Auswertung des abstrakten Syntaxbaumes demonstriert. 

class SyntaxError(Exception): pass def scan(s): a = []; i = 0; n = len(s) while i < n: if s[i] in "+-*/^()": a.append(s[i]) i += 1 elif s[i].isdigit(): j = i while i < n and s[i].isdigit(): i += 1 a.append(int(s[j:i])) elif s[i].isspace(): i += 1 else: raise SyntaxError( "unerwartetes Zeichen: '{}'".format(s[i])) a.append(None) return a def expect_token(a, i): if a[i] is None: raise SyntaxError("unerwartetes Ende der Eingabe") else: return a[i] def atom(a, i): t = expect_token(a, i) if isinstance(t, int): return i+1, a[i] elif t == "(": i, x = expression(a, i+1) if expect_token(a, i) != ")": raise SyntaxError( "')' wurde erwartet, es kam aber '{}'".format(a[i])) return i+1, x else: raise SyntaxError( "unerwartetes Symbol: '{}'".format(t)) def power(a, i): i, x = atom(a, i) if a[i] == "^": i, y = negation(a, i+1) return i, ["^", x, y] else: return i, x def negation(a, i): if a[i] == "-": i, x = power(a, i+1) return i, ["~", x] else: return power(a, i) def multiplication(a, i): i, x = negation(a, i) op = a[i] while op == "*" or op == "/": i, y = negation(a, i+1) x = [op, x, y] op = a[i] return i, x def addition(a, i): i, x = multiplication(a, i) op = a[i] while op == "+" or op == "-": i, y = multiplication(a, i+1) x = [op, x, y] op = a[i] return i, x def expression(a, i): return addition(a, i) def ast(a): i, t = expression(a, 0) if a[i] is None: return t else: raise SyntaxError( "Ende der Eingabe wurde erwartet, es kam aber: '{}'" .format(a[i])) dispatch = { "+": lambda x, y: x+y, "-": lambda x, y: x-y, "*": lambda x, y: x*y, "/": lambda x, y: x/y, "^": lambda x, y: x**y, "~": lambda x: -x } def evaluate(t): if isinstance(t, int): return t else: return dispatch[t[0]](*map(evaluate, t[1:])) while True: try: s = input("> ") if s == "": continue a = scan(s) t = ast(a) print("Abstrakter Syntaxbaum:\n {}\n".format(t)) print("Ergebnis:\n {}".format(evaluate(t))) except SyntaxError as e: print("Syntaxfehler: " + str(e)) except (KeyboardInterrupt, EOFError): print() break

Literatur 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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Rekursiver Abstieg englisch recursive descent ist eine Technik aus dem Compilerbau die auf direkte Weise d h ohne Tabelle einen Top Down Parser implementiert Sie zeichnet sich durch geringe Komplexitat aus das Verwenden eines Parsergenerators ist nicht notig Bei diesem Verfahren wird jedes Nichtterminalsymbol durch jeweils eine eigene Prozedur behandelt welche die Produktionsregeln zu diesem Symbol implementiert Erlauben die Produktionsregeln eine Rekursion dann rufen sich daher auch diese Prozeduren wechselseitig rekursiv auf Der rekursive Abstieg kann bei Bedarf mit Backtracking arbeiten wenn eine LL k Grammatik fur die zu parsende Sprache verwendet wird ist das jedoch nicht erforderlich Unuberlegte Verwendung von Backtracking kann zudem zu exponentiellem Laufzeitverhalten fuhren Im Folgenden wird daher der haufige Fall LL 1 angenommen Inhaltsverzeichnis 1 Code fur die Grammatikregeln eines Nichtterminalsymbols 2 Code fur eine Folge von Grammatiksymbolen 3 Beispiel 4 LiteraturCode fur die Grammatikregeln eines Nichtterminalsymbols BearbeitenFur jedes Nichtterminalsymbol der Grammatik wird eine Prozedur definiert Wenn A a 1 a 2 a n displaystyle A to alpha 1 alpha 2 ldots alpha n nbsp alle Regeln mit A displaystyle A nbsp auf der linken Seite sind sieht die Prozedur A displaystyle A nbsp in Pseudocode folgendermassen aus proc A displaystyle A nbsp if lookahead in f i r s t a 1 f o l l o w A displaystyle mathrm first alpha 1 mathrm follow A nbsp then C 1 displaystyle C 1 nbsp else if lookahead in f i r s t a 2 f o l l o w A displaystyle mathrm first alpha 2 mathrm follow A nbsp then C 2 displaystyle C 2 nbsp else if lookahead in f i r s t a n f o l l o w A displaystyle mathrm first alpha n mathrm follow A nbsp then C n displaystyle C n nbsp else error Dabei gilt a href Lookahead html title Lookahead lookahead a ist das aktuelle Eingabezeichen oder token f i r s t T displaystyle mathrm first T nbsp ist die Menge der Terminalsymbole oder Tokens die am Anfang eines Wortes stehen konnen das von einem der Worter in der Menge T displaystyle T nbsp erzeugt wurde f o l l o w A displaystyle mathrm follow A nbsp ist die Menge der Terminalsymbole die in einem vom Startsymbol erzeugten Wort direkt rechts von A displaystyle A nbsp stehen konnen C i displaystyle C i nbsp ist der Code fur das Parsen von a i displaystyle alpha i nbsp Die f o l l o w displaystyle mathrm follow nbsp Mengen mussen hier einbezogen werden weil f i r s t T displaystyle mathrm first T nbsp das leere Wort enthalten kann siehe LL k Grammatik Code fur eine Folge von Grammatiksymbolen BearbeitenFur a i X 1 X m displaystyle alpha i X 1 ldots X m nbsp wobei die X j displaystyle X j nbsp Terminale und oder Nichtterminale sein konnen besteht C i displaystyle C i nbsp aus den Code Abschnitten fur X 1 X m displaystyle X 1 ldots X m nbsp in derselben Reihenfolge Der Code fur ein einzelnes Symbol X j displaystyle X j nbsp sieht wie folgt aus Falls X j displaystyle X j nbsp Terminal ist if lookahead X j displaystyle X j nbsp then lookahead GetSymbol else error Falls X j displaystyle X j nbsp Nichtterminal ist X j displaystyle X j nbsp Dabei ist GetSymbol eine Funktion die das nachste Eingabezeichen oder token liefert Beispiel BearbeitenFur die Arithmetik lasst sich die folgende formale Grammatik in EBNF angeben Produktionsregeln in EBNF atom number expression power atom negation negation power multiplication negation negation addition multiplication multiplication expression addition Es folgt ein rekursiver Abstieg in Python der eine syntaktische Analyse vornimmt und dabei einen abstrakten Syntaxbaum erstellt Zuvor zerlegt ein lexikalischer Scanner scan die Eingabe in eine Liste von Tokens Im Nachhinein wird noch mit evaluate eine rekursive Auswertung des abstrakten Syntaxbaumes demonstriert class SyntaxError Exception pass def scan s a i 0 n len s while i lt n if s i in a append s i i 1 elif s i isdigit j i while i lt n and s i isdigit i 1 a append int s j i elif s i isspace i 1 else raise SyntaxError unerwartetes Zeichen format s i a append None return a def expect token a i if a i is None raise SyntaxError unerwartetes Ende der Eingabe else return a i def atom a i t expect token a i if isinstance t int return i 1 a i elif t i x expression a i 1 if expect token a i raise SyntaxError wurde erwartet es kam aber format a i return i 1 x else raise SyntaxError unerwartetes Symbol format t def power a i i x atom a i if a i i y negation a i 1 return i x y else return i x def negation a i if a i i x power a i 1 return i x else return power a i def multiplication a i i x negation a i op a i while op or op i y negation a i 1 x op x y op a i return i x def addition a i i x multiplication a i op a i while op or op i y multiplication a i 1 x op x y op a i return i x def expression a i return addition a i def ast a i t expression a 0 if a i is None return t else raise SyntaxError Ende der Eingabe wurde erwartet es kam aber format a i dispatch lambda x y x y lambda x y x y lambda x y x y lambda x y x y lambda x y x y lambda x x def evaluate t if isinstance t int return t else return dispatch t 0 map evaluate t 1 while True try s input gt if s continue a scan s t ast a print Abstrakter Syntaxbaum n n format t print Ergebnis n format evaluate t except SyntaxError as e print Syntaxfehler str e except KeyboardInterrupt EOFError print breakLiteratur BearbeitenAho 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 Abgerufen von https de wikipedia org w index php title Rekursiver Abstieg amp oldid 229835579