Dieses Kapitel basiert auf dem Artikel »It’s Easy As 1, 2, 3« von Graham Hutton.
Zunächst definieren wir die minimalistische Sprache, die Gegenstand der Betrachtungen sein wird. Die Sprache soll aus Ganzzahlen und Addition von Ganzzahlen bestehen. Dafür genügt eine einzige Zeile BNF:
E = Integer | E "+" E;
Wir legen außerdem fest, dass Ausdrücke geklammert werden dürfen, was zur erweiterten Grammatik
E = Integer | E "+" E | "(" E ")";
führt. Gewiss möchte man nun einen Parser für diese Sprache schreiben. Für die weiteren Betrachtungen ist das allerdings nebensächlich. Für Interessierte ist ein Verfahren zur Konstruktion in ›Beispiele: rekursiver Abstieg‹ beschrieben.
Jeder Ausdruck besitzt eine direkte Entsprechung als abstrakter Syntaxbaum der Form:
enum Expr {Value(i32), Add(Box<(Expr, Expr)>)}
Beispielsweise gehört zum Ausdruck »1 + 2« der Baum
Expr::Add(Box::new((Expr::Value(1), Expr::Value(2)))).
Da das recht umständlich ist, fügen wir zwei freistehende Konstruktorfunktionen hinzu:
fn value(n: i32) -> Expr {Expr::Value(n)}
fn add(x: Expr, y: Expr) -> Expr {Expr::Add(Box::new((x, y)))}
Damit verkürzt sich die Notation zu
add(value(1), value(2)).
Wir definieren die Auswertungsfunktion, die einem Ausruck
x vom Typ Expr den Wert ⟦x⟧
vom Typ i32 zuordnet, gemäß
⟦value(n)⟧ = n, ⟦add(x, y)⟧ = ⟦x⟧ + ⟦y⟧.
Wir tun so, als würde i32 alle ganzen Zahlen
umfassen, bzw. als würden wir eine Langzahlarithmetik haben.
Andernfalls ist die Auswertung eine partielle Funktion, die wir
total machen müssten, indem der Rückgabewert zu
Option<i32> eingehüllt wird.
Aus der mathematischen Definition der Auswertung erhält man direkt eine Rust-Funktion:
fn eval(t: &Expr) -> i32 {
match t {
Expr::Value(n) => *n,
Expr::Add(t) => eval(&t.0) + eval(&t.1)
}
}
Man kann hier noch bemerken, dass die mathematische
Defintion nicht per se eine Auswertungsreihenfolge vorgiebt,
die Funktion eval aber eifrig auswertet.