Ein Rechner für Ausdrücke

1. Punkt vor Strich

Ein Ausdruck wie 2 + 3 * 4 ist für einen Computer zuerst nur Text, eine Reihe von Zeichen. Von links nach rechts ausgerechnet käme 20 heraus: 2 + 3 ist 5, mal 4 ist 20. Richtig ist 14, denn Malnehmen bindet stärker als Plus. Für Ausdrücke gelten ein paar Regeln, die du aus der Mathematik kennst:

• Klammern zuerst.
• Punkt vor Strich: * und / vor + und -.
• Sonst von links nach rechts.

Die letzte Regel klingt selbstverständlich, macht aber einen Unterschied.

Ein Rechner muss diese Regeln kennen. Er arbeitet dafür in drei Schritten:

1. Zerlegen: Aus dem Text 12+3*(4-1) werden Tokens, die kleinsten Stücke, die etwas bedeuten: die Zahl 12, das Zeichen +, die Zahl 3 und so weiter. Leerzeichen fallen dabei weg.
2. Einen Baum bauen: Aus den Tokens wird ein Baum, an dem die Regeln schon abzulesen sind: Was zuerst gerechnet wird, hängt weiter unten.
3. Ausrechnen: Den Baum von unten nach oben, Knoten für Knoten.

So sieht der Baum für 2 + 3 * 4 aus. Das * hängt unter dem +, also wird es zuerst ausgerechnet:

2. Einrichten

Lege einen Ordner an und öffne ihn mit StrgK StrgO:

mkdir /workspace/calculator

# Ein Rechner für Ausdrücke

# Zerlegt einen Ausdruck in Tokens: Zahlen, Rechenzeichen und Klammern.
def tokenize(text)
    []
end

# Macht aus Tokens einen Baum.
def parse(tokens)
    tokens.first
end

# Rechnet einen Baum aus.
def evaluate(tree, variables = {})
    tree
end

def calculate(text, variables = {})
    evaluate(parse(tokenize(text)), variables)
end

loop do
    print '> '
    line = gets
    if line.nil?
        puts
        break
    end

    line = line.strip
    next if line.empty?

    begin
        p calculate(line)
    rescue ArgumentError => e
        puts "Fehler: #{e.message}"
    end
end

# Ein Rechner für Ausdrücke


def tokenize(text):
    """Zerlegt einen Ausdruck in Tokens: Zahlen, Rechenzeichen und Klammern."""
    return []


def parse(tokens):
    """Macht aus Tokens einen Baum."""
    return tokens[0] if tokens else None


def evaluate(tree, variables=None):
    """Rechnet einen Baum aus."""
    return tree


def calculate(text, variables=None):
    return evaluate(parse(tokenize(text)), variables)


while True:
    try:
        line = input('> ').strip()
    except EOFError:
        print()
        break
    if not line:
        continue
    try:
        print(calculate(line))
    except ValueError as error:
        print(f'Fehler: {error}')

3. Zerlegen

tokenize geht den Text Zeichen für Zeichen durch, mit einem Index i, und entscheidet bei jedem Zeichen, was es ist:

• Ein Leerzeichen trennt nur. Es wird übersprungen.
• + - * / ^ ( ) sind je ein Token für sich.
• Eine Ziffer ist der Anfang einer Zahl. Die Zahl geht weiter, solange Ziffern kommen. Kommen danach ein Punkt und wieder Ziffern, ist es eine Kommazahl: 3.25.
• Alles andere ist ein Fehler, zum Beispiel #. Dann bricht tokenize ab, mit einer Meldung, welches Zeichen an welcher Stelle nicht passt.

Was eine Zahl ist, beschreibt ein endlicher Automat, wie du sie aus Endliche Automaten kennst. In Automatron steht z für eine Ziffer und p für den Punkt: z+(pz+)? heißt »mindestens eine Ziffer, danach vielleicht ein Punkt und mindestens eine Ziffer«.

Die Schleifen in tokenize sind dieser Automat: Die erste läuft in s1 im Kreis, solange Ziffern kommen. Ein Punkt führt nach s2, und nur wenn danach wieder eine Ziffer kommt, geht es nach s3 weiter. Hört die Zahl in s2 auf, wie in 3., hat der Automat keine Zahl gelesen. Dein Tokenizer nimmt dann nur die 3 und meldet den Punkt als Zeichen, das nicht passt.

4. Ein Baum

Den Ausdruck 2 + 3 * 4 schreibt der Rechner als Baum, in dem das, was zuerst gerechnet wird, weiter unten hängt: oben das +, links die 2, rechts ein * mit der 3 und der 4. Als Liste ist das

["+", 2, ["*", 3, 4]]

Jeder Knoten ist entweder eine Zahl, ein Blatt, oder eine Liste aus dem Rechenzeichen und den beiden Teilbäumen links und rechts. Ein Minus vor einer Zahl oder einer Klammer ist ein Vorzeichen mit nur einem Teilbaum: -(1 + 2) ist ["neg", ["+", 1, 2]]. Klammern tauchen im Baum gar nicht mehr auf, sie stecken in seiner Form: (2 + 3) * 4 ist ["*", ["+", 2, 3], 4].

Probier es aus. Der Baum steht so, dass du den Ausdruck von links nach rechts lesen kannst. Mit den Pfeilen rechnest du ihn aus, einen Knoten nach dem anderen. Rot umrandet ist der Knoten, der als Nächstes drankommt: immer einer, unter dem nur noch Zahlen hängen.

Was ein Automat nicht kann

Für die Tokens hat ein Automat gereicht. Für den Baum reicht er nicht mehr. Um zu wissen, zu welcher Klammer ein ) gehört, muss man sich merken, wie viele Klammern gerade offen sind, und in ((((1)))) können es beliebig viele sein.

Was ein Automat nicht kann, kann ein Programm, das sich selbst aufruft. Die Regeln für Ausdrücke lassen sich als Grammatik aufschreiben, eine Regel pro Zeile. { … } heißt »beliebig oft, auch keinmal«, | heißt »oder«:

expression = term { ("+" | "-") term }
term       = factor { ("*" | "/") factor }
factor     = "-" factor | atom
atom       = Zahl | "(" expression ")"

Ein Ausdruck ist eine Summe aus Termen, ein Term ein Produkt aus Faktoren, und ein Faktor ist eine Zahl oder wieder ein ganzer Ausdruck in Klammern. Dass * stärker bindet als +, steht in der Grammatik selbst: Ein Term wird ganz eingesammelt, bevor das nächste + drankommt.

Aus jeder Regel wird eine Methode, die vorn aus der Liste der Tokens nimmt, was zu ihr gehört, und den Baum dafür zurückgibt. So sieht die erste aus:

def expression(tokens)
    tree = term(tokens)
    tree = [tokens.shift, tree, term(tokens)] while ['+', '-'].include?(tokens.first)
    tree
end

def expression(tokens):
    tree = term(tokens)
    while first(tokens) in ('+', '-'):
        tree = [tokens.pop(0), tree, term(tokens)]
    return tree

Wo der Automat nur Zustände hatte, merkt sich das Programm, wo es gerade ist: Jeder Aufruf, der noch nicht fertig ist, wartet auf dem Stack, bis der Aufruf darin zurückkommt. Bei ((((1)))) liegen vier atom übereinander, und jedes weiß, dass es noch ein ) braucht. Eine Grammatik wie diese heißt kontextfrei, und ein Parser, der für jede Regel eine Methode hat, die sich gegenseitig aufrufen, heißt rekursiver Abstieg.

5. Ausrechnen

Den Baum auszurechnen ist das Leichteste: Ein Blatt ist schon sein Wert. Bei jedem anderen Knoten rechnest du zuerst die Teilbäume aus, mit evaluate selbst, und verbindest dann ihre Werte mit dem Rechenzeichen. Genau so, wie der Baumzeichner oben es zeigt, nur dass evaluate die Knoten nicht nacheinander, sondern ineinander erledigt.

op, *args = tree
values = args.map { |arg| evaluate(arg, variables) }

op, *args = tree
values = [evaluate(arg, variables) for arg in args]

6. Fehler

Was soll bei (1 + 2 herauskommen, oder bei 1 +? Gar nichts: Das sind keine Ausdrücke. Ein Rechner, der dann trotzdem etwas ausrechnet, ist schlimmer als einer, der es sagt. Wo der Parser etwas anderes findet, als die Grammatik erlaubt, bricht er mit einem Fehler ab:

• atom bekommt kein Token mehr, weil der Ausdruck zu früh aufhört: 1 +.
• atom findet nach einem Ausdruck in Klammern kein ): (1 + 2.
• atom findet etwas, das keine Zahl und keine Klammer auf ist: ) oder * 3.
• Nach dem ganzen Ausdruck sind noch Tokens übrig: 1 2.

Der Rechner zum Tippen fängt solche Fehler ab und schreibt die Meldung hin, statt abzustürzen. Mach die Meldungen so, dass man versteht, was fehlt.

7. Hoch

Als Nächstes kommt ^ für »hoch« dazu: 2 ^ 3 ist 8. Hoch bindet noch stärker als Malnehmen, 2 * 3 ^ 2 ist 18. Und es hat eine Eigenart:

Hoch wird von rechts nach links gerechnet. Und ein Minus davor gilt erst nach dem Hoch: -2 ^ 2 ist −4, so wie in der Mathematik −2² = −4 ist. Beides passt in eine neue Regel zwischen factor und atom:

factor     = "-" factor | power
power      = atom [ "^" factor ]

[ … ] heißt »vielleicht«. Weil nach dem ^ wieder factor kommt und nicht eine Schleife wie bei +, hängt 2 ^ 3 ^ 2 als ["^", 2, ["^", 3, 2]] zusammen: rechts tiefer, also rechts zuerst. Und weil factor ein Vorzeichen erlaubt, geht auch 2 ^ -1.

8. Variablen

Ein Rechner, der sich Zahlen merkt, ist viel praktischer: breite = 4, hoehe = 3, dann breite * hoehe. Dafür braucht es drei Änderungen:

1. tokenize erkennt Namen: ein Buchstabe oder _, danach beliebig viele Buchstaben, Ziffern und _. Ein Name ist ein String-Token wie die Rechenzeichen.
2. In der Grammatik ist ein Name ein atom, so wie eine Zahl, und im Baum ein Blatt: x * (x + 1) ist ["*", "x", ["+", "x", 1]].
3. evaluate bekommt die Werte der Namen mit und schaut ein Blatt, das ein Name ist, dort nach. Ein Name ohne Wert ist ein Fehler.

Die Werte stehen in einem Hash: calculate('x * (x + 1)', { 'x' => 3 }) ist 12. Gib variables in evaluate an jeden Aufruf für die Teilbäume weiter.

Fehlt noch die Zuweisung. Sie gehört nicht in die Grammatik, sondern in den Rechner zum Tippen: Fängt eine Zeile mit einem Namen und = an, rechnet er den Rest aus und merkt sich das Ergebnis.

if (m = line.match(/\A([a-z_][a-z_0-9]*)\s*=(.*)\z/i))
    variables[m[1]] = calculate(m[2], variables)
    puts "#{m[1]} = #{variables[m[1]]}"
else
    puts calculate(line, variables)
end

variables = {} steht vor der Schleife, damit es sich von Zeile zu Zeile hält.

Die Werte stehen in einem dict: calculate('x * (x + 1)', {'x': 3}) ist 12. Gib variables in evaluate an jeden Aufruf für die Teilbäume weiter.

Fehlt noch die Zuweisung. Sie gehört nicht in die Grammatik, sondern in den Rechner zum Tippen: Fängt eine Zeile mit einem Namen und = an, rechnet er den Rest aus und merkt sich das Ergebnis.

m = re.fullmatch(r'([A-Za-z_]\w*)\s*=(.*)', line)
if m:
    variables[m[1]] = calculate(m[2], variables)
    print(f'{m[1]} = {variables[m[1]]}')
else:
    print(calculate(line, variables))

import re gehört an den Anfang und variables = {} vor die Schleife, damit es sich von Zeile zu Zeile hält.

9. Wie geht es weiter?

• Funktionen: sqrt(16) oder max(3, 7). Ein Name mit ( dahinter ist ein Aufruf; die Grammatik bekommt dafür eine Regel mit einer Liste von Ausdrücken, durch Kommas getrennt.
• Vergleiche wie x < 3 binden noch schwächer als +: eine Regel über expression. Mit Vergleichen, if und Schleifen wird aus dem Rechner eine kleine Programmiersprache, und evaluate ein Interpreter.
• Ein Compiler rechnet den Baum nicht aus, sondern schreibt für jeden Knoten Befehle auf, die ihn später ausrechnen. Wie solche Befehle für einen Prozessor aussehen, zeigt die CPU Sandbox.
• Ruby und Python bauen aus deinem Programm auch zuerst einen Baum. Sieh ihn dir an:

ruby -e 'pp RubyVM::AbstractSyntaxTree.parse("2 + 3 * 4")'
python3 -c 'import ast; print(ast.dump(ast.parse("2 + 3 * 4", mode="eval"), indent=2))'