MathParser: Parser als Denkwerkzeug
Ein Rückblick auf ein eigenes Parser-Demo von 2010 zeigt, warum ein handgeschriebener Ausdrucks-Parser auf wenigen Zeilen mehr über Schichten, Struktur und die Grenze zwischen Syntax und Semantik lehrt als manches große Projekt.
Rund 200 Zeilen C#. Mehr braucht ein vollständiger Parser für Rechenausdrücke nicht – Tokenizer, rekursiver Abstieg, Auswertung, Klammern, Punkt-vor-Strich, brauchbare Fehlermeldungen mit Positionsangabe. Ein durchschnittlicher Controller in einem Geschäftssystem erreicht dieselbe Länge und lehrt dabei fast nichts über Softwareentwurf. Die 200 Parser-Zeilen dagegen enthalten drei sauber getrennte Schichten, eine Grammatik als explizites Strukturmodell und eine Grenze zwischen Form und Bedeutung, an der man sich beim Schreiben mindestens einmal die Finger klemmt. Gemessen an Erkenntnis pro Zeile kenne ich wenig, das dichter ist – und es passt in einen Nachmittag.
Ein vier Jahre altes Demo-Projekt, neu gelesen
Der Anlass für diesen Text ist ein eigenes Repository: MathParser, ein C#-Demo-Projekt von 2010. Eine Visual-Studio-Solution, darin ein Parser-Projekt, eine zweite Variante namens ClassicMathParser und ein Testprojekt. Kein Produkt, keine Bibliothek für andere – ein Demo, geschrieben, um die Sache einmal selbst durchdrungen zu haben.
Vier Jahre später habe ich es wieder aufgemacht, eigentlich nur, um aufzuräumen. Hängen geblieben bin ich an etwas anderem: Der Code stellt Fragen, die ich 2010 gar nicht gesehen habe. Warum liegen da zwei Varianten nebeneinander? Warum wertet der Parser sofort aus, statt erst eine Struktur zu bauen? Warum steckt die Behandlung des Minuszeichens genau dort, wo sie steckt? Alte eigene Projekte sind darin unbequem ehrlich: Man diskutiert mit einem früheren Ich, das sich nicht mehr herausreden kann.
Genau deshalb lohnt sich der Rückblick als Artikel. Nicht weil das Repository besonders wäre – sondern weil das Thema als Denkwerkzeug besser altert als die meisten Frameworks jener Zeit.
Warum ein regulärer Ausdruck hier nicht reicht
Der erste Reflex bei „Rechenausdruck parsen“ ist in Code-Reviews immer wieder derselbe: ein regulärer Ausdruck, vielleicht zwei, dazu ein Split auf Operatoren. Für 2+3*4 sieht das kurz sogar gut aus. Für (1+2)*(3-(4/2)) bricht es zusammen, und zwar nicht wegen handwerklicher Fehler, sondern grundsätzlich: Reguläre Ausdrücke können nicht zählen. Verschachtelte Klammern verlangen ein Gedächtnis über die Tiefe der Verschachtelung, und genau das gibt ein regulärer Ausdruck vom Modell her nicht her. Man kann das theoretisch begründen – reguläre gegen kontextfreie Sprachen –, aber praktisch reicht ein Blick auf die Klammern: Wer ((( liest, muss sich merken, dass noch dreimal ))) folgen muss.
Mir ist dabei 2010 zum ersten Mal aufgefallen, dass die Wahl des Werkzeugs eine Aussage über die Struktur des Problems ist. Ein regulärer Ausdruck behauptet: „Diese Eingabe ist flach.“ Ein Parser mit Rekursion behauptet: „Diese Eingabe ist ein Baum.“ Rechenausdrücke sind Bäume – 1+2*3 hat eine innere Gliederung, die man der Zeichenkette nicht ansieht. Wer das Falsche behauptet, bezahlt später mit Sonderfällen.
Drei Schichten, drei Verträge
Ein Ausdrucks-Parser zerfällt fast von selbst in drei Schichten, und jede hat einen klaren Vertrag:
- Der Tokenizer macht aus einer Zeichenkette einen Strom von Symbolen: Zahlen, Operatoren, Klammern. Er kennt Zeichen, aber keine Struktur.
- Der Parser prüft, ob die Symbolfolge der Grammatik entspricht, und baut daraus die Struktur. Er kennt Struktur, aber keine Bedeutung.
- Die Auswertung gibt der Struktur eine Bedeutung: Sie rechnet. Erst hier existieren Begriffe wie „Ergebnis“ oder „Division durch null“.
flowchart LR A["Eingabe<br/>(1+2)*3"] --> B["Tokenizer<br/>Zeichen zu Symbolen"] B --> C["Token-Strom<br/>( 1 + 2 ) * 3"] C --> D["Parser<br/>rekursiver Abstieg"] D --> E["Struktur<br/>Baum oder direkter Wert"] E --> F["Auswertung<br/>Bedeutung, Ergebnis"]
Das klingt nach Lehrbuch, hat aber eine sehr praktische Pointe: Jede Schicht kann man einzeln testen, einzeln ersetzen und einzeln erklären. Genau dafür ist in der Solution ein eigenes Testprojekt vorgesehen, und die Tests für den Tokenizer wissen nichts von Grammatik – sie prüfen nur, dass aus "12.5+" die Symbole 12.5 und + werden. Diese Art von Trennung predigt man in großen Systemen ständig; im Parser ist sie kein Vorsatz, sondern die einzig bequeme Bauweise. Das ist der erste Grund, warum ich das Thema ein Denkwerkzeug nenne: Es macht ein Architekturprinzip erlebbar, statt es zu behaupten.
Die Grammatik zwingt zum Nachdenken über Struktur
Bevor der eigentliche Parser entsteht, steht die Grammatik – bei mir damals als EBNF-Skizze auf einem Zettel, in dieser Form:
Expression := Term { ("+" | "-") Term }
Term := Factor { ("*" | "/") Factor }
Factor := Number | "(" Expression ")" | "-" FactorDrei Zeilen, und die interessanteste Eigenschaft steht nirgends explizit: die Operator-Rangfolge. Punkt-vor-Strich ist keine Regel, die irgendwo per if geprüft wird – sie steckt in der Schichtung der Grammatik. Expression besteht aus Term-Bausteinen, Term aus Factor-Bausteinen. Weil * und / eine Ebene tiefer gebunden werden als + und -, binden sie automatisch stärker. Die Klammer wiederum springt von ganz unten zurück nach ganz oben: Ein Factor darf eine komplette Expression enthalten. Das ist die Rekursion, an der der reguläre Ausdruck vorhin gescheitert ist, hier in einer einzigen Zeile.
Beim Wiederlesen 2014 finde ich das immer noch bemerkenswert: Rangfolge als Struktur statt als Bedingung. Terence Parr behandelt genau diese Denkweise in „Language Implementation Patterns“ von 2010 ausführlich, und Douglas Crockford zeigt in seinem Essay „Top Down Operator Precedence“ von 2007 einen alternativen Weg, bei dem die Rangfolge als Bindungsstärke an den Operatoren selbst hängt. Beide Wege führen zum Ziel; wer beide einmal nachgebaut hat, versteht danach besser, was „Struktur ausdrücken“ überhaupt heißt.
Rekursiver Abstieg in C#
Die Grammatik übersetzt sich fast mechanisch in Code – pro Regel eine Methode. Zuerst der Tokenizer, hier bewusst schlicht gehalten:
public enum TokenType { Number, Plus, Minus, Star, Slash, LeftParen, RightParen, End }
public sealed class Tokenizer
{
private readonly string _input;
private int _position;
public Tokenizer(string input) { _input = input; }
public Token Next()
{
while (_position < _input.Length && char.IsWhiteSpace(_input[_position]))
_position++;
if (_position >= _input.Length)
return new Token(TokenType.End, 0, _position);
char current = _input[_position];
if (char.IsDigit(current))
{
int start = _position;
while (_position < _input.Length &&
(char.IsDigit(_input[_position]) || _input[_position] == '.'))
_position++;
double value = double.Parse(
_input.Substring(start, _position - start),
CultureInfo.InvariantCulture);
return new Token(TokenType.Number, value, start);
}
_position++;
switch (current)
{
case '+': return new Token(TokenType.Plus, 0, _position - 1);
case '-': return new Token(TokenType.Minus, 0, _position - 1);
case '*': return new Token(TokenType.Star, 0, _position - 1);
case '/': return new Token(TokenType.Slash, 0, _position - 1);
case '(': return new Token(TokenType.LeftParen, 0, _position - 1);
case ')': return new Token(TokenType.RightParen, 0, _position - 1);
}
throw new FormatException(
string.Format("Unexpected character '{0}' at position {1}.", current, _position - 1));
}
}Zwei Kleinigkeiten mit großer Wirkung: CultureInfo.InvariantCulture, weil double.Parse auf einer deutschen Maschine sonst das Komma erwartet und 1.5 still zu 15 macht – ein Fehler, den ich nicht im Parser-Demo, aber in echten Systemen mehr als einmal gejagt habe. Und die Positionsangabe im Token, denn ohne sie kann später keine Schicht eine Fehlermeldung erzeugen, die dem Anwender die Stelle zeigt.
Der Parser selbst folgt der Grammatik Zeile für Zeile:
public sealed class Parser
{
private readonly Tokenizer _tokenizer;
private Token _current;
public Parser(string input)
{
_tokenizer = new Tokenizer(input);
_current = _tokenizer.Next();
}
public double Parse()
{
double result = ParseExpression();
Expect(TokenType.End);
return result;
}
// Expression := Term { ("+" | "-") Term }
private double ParseExpression()
{
double left = ParseTerm();
while (_current.Type == TokenType.Plus || _current.Type == TokenType.Minus)
{
TokenType op = _current.Type;
Advance();
double right = ParseTerm();
left = op == TokenType.Plus ? left + right : left - right;
}
return left;
}
// Term := Factor { ("*" | "/") Factor }
private double ParseTerm()
{
double left = ParseFactor();
while (_current.Type == TokenType.Star || _current.Type == TokenType.Slash)
{
TokenType op = _current.Type;
Advance();
double right = ParseFactor();
left = op == TokenType.Star ? left * right : left / right;
}
return left;
}
// Factor := Number | "(" Expression ")" | "-" Factor
private double ParseFactor()
{
if (_current.Type == TokenType.Number)
{
double value = _current.Value;
Advance();
return value;
}
if (_current.Type == TokenType.LeftParen)
{
Advance();
double inner = ParseExpression();
Expect(TokenType.RightParen);
return inner;
}
if (_current.Type == TokenType.Minus)
{
Advance();
return -ParseFactor();
}
throw new FormatException(
string.Format("Unexpected token at position {0}.", _current.Position));
}
private void Advance() { _current = _tokenizer.Next(); }
private void Expect(TokenType type)
{
if (_current.Type != type)
throw new FormatException(
string.Format("Expected {0} at position {1}.", type, _current.Position));
Advance();
}
}Das ist rekursiver Abstieg in Reinform: ParseExpression ruft ParseTerm, ParseTerm ruft ParseFactor, und ParseFactor ruft bei einer Klammer wieder ParseExpression. Der Aufruf-Stack der Laufzeitumgebung übernimmt das Klammern-Zählen, das dem regulären Ausdruck gefehlt hat. Man kann Werkzeuge wie ANTLR solche Methoden aus einer Grammatik generieren lassen – für ernsthafte Sprachen würde ich das auch tun. Für das Verstehen ist die Handarbeit durch nichts zu ersetzen.
AST oder direkte Auswertung – die Frage, die ich 2010 übersprungen habe
Der gezeigte Parser rechnet sofort: ParseTerm liefert ein double, nicht einen Knoten. Das ist die kürzeste Variante, und für ein Demo völlig in Ordnung. Beim Wiederlesen fällt mir aber auf, was diese Abkürzung kostet: Parser und Auswertung, eben noch zwei Schichten mit eigenen Verträgen, sind hier zu einer verschmolzen. Wer denselben Ausdruck zweimal mit anderen Variablenwerten rechnen will, muss zweimal parsen. Wer den Ausdruck hübsch formatiert ausgeben, vereinfachen oder in eine andere Sprache übersetzen will, kann es gar nicht – die Struktur wurde ja nie festgehalten, sie existierte nur flüchtig im Aufruf-Stack.
Die Alternative ist ein abstrakter Syntaxbaum: ParseTerm liefert dann einen Node, etwa BinaryNode(Star, NumberNode(2), NumberNode(3)), und eine getrennte Evaluate-Methode läuft über den Baum. Mehr Code, mehr Allokationen – aber die Struktur wird zum eigenständigen Wert, mit dem sich weiterarbeiten lässt. In meiner Solution liegen bis heute zwei Projektvarianten nebeneinander, und ich vermute stark, dass der Unterschied genau um diese Frage kreiste; sicher sagen kann ich es nach vier Jahren nicht mehr, und das ist selbst eine Lektion über Demo-Projekte ohne Notizen.
Die allgemeine Form der Frage begegnet mir seither ständig: Werte ich sofort aus oder baue ich erst ein Modell? Ein Import, der Zeile für Zeile direkt in die Datenbank schreibt, ist die direkte Auswertung. Ein Import, der erst ein geprüftes Zwischenmodell baut und es dann anwendet, ist der Baum. Beides ist legitim – aber es sollte eine Entscheidung sein, kein Zufall.
Dasselbe in ES5, zur Probe
Um zu prüfen, ob die Struktur trägt oder nur ein C#-Idiom ist, habe ich den Kern in JavaScript nachgezogen – gleiches Muster, gleiche Namen:
// Expression := Term { ("+" | "-") Term }
function parseExpression(state) {
var left = parseTerm(state);
while (state.current.type === 'Plus' || state.current.type === 'Minus') {
var op = state.current.type;
advance(state);
var right = parseTerm(state);
left = op === 'Plus' ? left + right : left - right;
}
return left;
}Kein Typsystem, keine Klassen, und trotzdem ist es erkennbar derselbe Parser. Das ist kein Zufall: Die Grammatik ist das Entwurfsdokument, der Code nur ihre Übersetzung. Crockfords Essay treibt das in JavaScript noch weiter und baut damit einen Parser für JavaScript selbst – wer wissen will, was JSON.parse oder ein Ausdrucks-Feld in einem Formular innen tun, findet dort die Antwort in erstaunlich wenig Code.
Die Grenze zwischen Syntax und Semantik wird körperlich
Der Moment, der mir vom Nachmittag 2010 am deutlichsten geblieben ist, hängt am Minuszeichen. 3-2 und -2 enthalten dasselbe Zeichen, aber zwei verschiedene Dinge: einmal einen binären Operator, einmal ein Vorzeichen. Der Tokenizer kann den Unterschied nicht kennen – er sieht nur ein Zeichen. Entschieden wird im Parser, und zwar über den Kontext: Ein Minus an einer Stelle, an der ein Factor erwartet wird, ist ein Vorzeichen; ein Minus nach einem fertigen Term ist eine Subtraktion. Die Bedeutung „negieren“ kommt dann noch einmal später, in der Auswertung.
Dasselbe gilt für Fehler. 2+*3 scheitert im Parser – ein Syntaxfehler, die Eingabe ist schon als Form ungültig. 2/0 dagegen passiert den Parser anstandslos und scheitert erst in der Auswertung – ein semantischer Fehler, die Form war korrekt, die Bedeutung ist es nicht. Wer beide Fehler in derselben Schicht behandelt, hat die Grenze verwischt; wer sie trennt, bekommt zwei präzise Fehlermeldungen fast geschenkt. Diese Unterscheidung – was ist wohlgeformt, was ist gültig, was ist sinnvoll – trage ich seitdem durch jede Schnittstellen-Diskussion, von der Validierung eines XML-Dokuments bis zur Frage, ob ein Web-Service eine 400 oder eine 422 zurückgeben sollte.
Was ich daraus mitnehme
Unterm Strich hat mir das Wiederlesen des alten Demos drei Dinge klargemacht. Erstens: Kleine, abgeschlossene Probleme sind die besseren Lehrstücke, weil man sie vollständig durchdringen kann – bei einem Parser gibt es keine Stelle, an der man auf Magie verweisen müsste. Zweitens: Die drei Schichten und die Grammatik-Schichtung sind kein Parser-Spezialwissen, sondern Architektur im Kleinen; die Fragen „wer darf was wissen“ und „wo steckt die Struktur“ sind exakt dieselben wie in jedem größeren System. Drittens: Alte eigene Projekte mit vier Jahren Abstand zu lesen ist eine unterschätzte Übung – die offenen Fragen von damals sind heute sichtbar, und die Antworten von heute wären ohne den damaligen Nachmittag nicht da.
Wer noch nie einen Parser geschrieben hat: Ein Nachmittag, ein leeres Projekt, die drei EBNF-Zeilen von oben. Kein Generator, keine Bibliothek, kein Blick in fremden Code. Die 200 Zeilen, die dabei herauskommen, sind vermutlich das dichteste Stück Softwareentwurf, das sich in dieser Zeit lernen lässt.
Weiterführende Quellen
- Mein Demo-Repository: github.com/MikeBild/MathParser
- Douglas Crockford: Top Down Operator Precedence (2007)
- Terence Parr: Language Implementation Patterns (Pragmatic Bookshelf, 2010)
- ANTLR – Parser-Generator, falls es doch eine echte Grammatik werden soll
Kommentare