Rekursiver Abstieg

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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 kommt jedem Nichtterminalsymbol eine Prozedur zu, welche die Produktionsregel zu diesem Symbol charakterisiert. Erlauben die Produktionsregeln eine Rekursion, dann rufen sich daher auch diese Prozeduren wechselseitig rekursiv auf.

Ein rekursiver Abstieg kann Backtracking enthalten. Ein Verzicht darauf ist jedoch garantiert, wenn eine LL(k)-Grammatik für die zu parsende Sprache gegeben ist. 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.

Beispiel[Bearbeiten | Quelltext 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, welcher eine syntaktische Analyse vornimmt und dabei einen abstrakten Syntaxbaum erstellt. Zuvor wird die Eingabe mit einem lexikalischen Scanner scan in eine Liste von Tokens zerlegt. 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:
        print()
        break

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.