Rekursiver Abstieg

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

${\displaystyle A\to \alpha _{1}\,|\,\alpha _{2}\,|\,\ldots \,|\,\alpha _{n}}$ 

alle Regeln mit ${\displaystyle A}$  auf der linken Seite sind, sieht die Prozedur ${\displaystyle A}$  in Pseudocode folgendermaßen aus:

 proc ${\displaystyle A}$ ()
    if lookahead in ${\displaystyle \mathrm {first} (\{\alpha _{1}\}\mathrm {follow} (A))}$  then
       ${\displaystyle C_{1}}$ 
    else if lookahead in ${\displaystyle \mathrm {first} (\{\alpha _{2}\}\mathrm {follow} (A))}$  then
       ${\displaystyle C_{2}}$ 
    ...
    else if lookahead in ${\displaystyle \mathrm {first} (\{\alpha _{n}\}\mathrm {follow} (A))}$  then
       ${\displaystyle C_{n}}$ 
    else
       error

Dabei gilt:

• lookahead ist das aktuelle Eingabezeichen (oder -token).
• ${\displaystyle \mathrm {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 ${\displaystyle T}$  erzeugt wurde.
• ${\displaystyle \mathrm {follow} (A)}$  ist die Menge der Terminalsymbole, die in einem vom Startsymbol erzeugten Wort direkt rechts von ${\displaystyle A}$  stehen können.
• ${\displaystyle C_{i}}$  ist der Code für das Parsen von ${\displaystyle \alpha _{i}}$ .

Die ${\displaystyle \mathrm {follow} }$ -Mengen müssen hier einbezogen werden, weil ${\displaystyle \mathrm {first} (T)}$  das leere Wort enthalten kann; siehe LL(k)-Grammatik.

Für ${\displaystyle \alpha _{i}=X_{1}\ldots X_{m}}$  (wobei die ${\displaystyle X_{j}}$  Terminale und/oder Nichtterminale sein können) besteht ${\displaystyle C_{i}}$  aus den Code-Abschnitten für ${\displaystyle X_{1},\ldots ,X_{m}}$  in derselben Reihenfolge.

Der Code für ein einzelnes Symbol ${\displaystyle X_{j}}$  sieht wie folgt aus:

• Falls ${\displaystyle X_{j}}$  Terminal ist:

 if lookahead = ${\displaystyle X_{j}}$  then
    lookahead := GetSymbol()
 else
    error

• Falls ${\displaystyle X_{j}}$  Nichtterminal ist:

 ${\displaystyle X_{j}}$ ()

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

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

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