Parser Combinators 101: Ein leichter Einstieg in das Parsen mathematischer Ausdrücke
In diesem Tutorial bauen wir einen einfachen, aber leistungsfähigen Math-Expression-Parser, der Ausdrücke wie "2+3*4" oder "(1+2)/(3-1)" auswerten kann. Wir setzen dabei auf Parser Combinators—eine funktionale Programmiertechnik, mit der sich komplexe Parser durch Komposition kleinerer, einfacherer Parser realisieren lassen.
Lasst uns einen einfachen Parser für mathematische Ausdrücke erstellen
In diesem Tutorial bauen wir einen einfachen, aber leistungsfähigen Math-Expression-Parser, der Ausdrücke wie "2+3*4" oder "(1+2)/(3-1)" auswerten kann. Wir setzen dabei auf Parser Combinators—eine funktionale Programmiertechnik, mit der sich komplexe Parser durch Komposition kleinerer, einfacherer Parser realisieren lassen.
Parser Combinators sind nicht nur für Spielzeugbeispiele gedacht. Sie eignen sich hervorragend, wenn du:
- Eine Domain-Specific Language (DSL) für benutzerdefinierte Eingaben oder Konfigurationen brauchst
- Strukturierte, komplexe Eingaben ohne ein Durcheinander von Regexes verarbeiten musst
- Sauberen, wartbaren, typsicheren Code schreiben möchtest, der deine Grammatik direkt widerspiegelt
Sie bieten eine elegante Lösung für diese Probleme, weil sie es ermöglichen:
- Komplexe Grammatikregeln durch die Kombination kleiner Parser auszudrücken
- Die starke Typsicherheit während des gesamten Parsing-Vorgangs beizubehalten
- Klaren, komponierbaren Code zu schreiben, der der Grammatik natürlich folgt
Wir beginnen mit der Implementierung einiger grundlegender Parser Combinators und erweitern sie schrittweise zu einem vollständigen Expression-Parser, der arithmetische Operationen mit korrekter Operator-Präzedenz auswerten kann.
1. Was ist ein Parser Combinator?
Ein Parser Combinator ist eine Higher-Order-Funktion (oder eine Gruppe von Higher-Order-Funktionen), die beim Bau von Parsern eingesetzt wird.
Anstatt einen gesamten Parser von Hand zu schreiben oder ein separates Code-Generierungs-Tool (wie traditionelle Parser-Generatoren à la Yacc, ANTLR usw.) zu nutzen, erlauben Parser Combinators, komplexe Grammatiken direkt in der Host-Sprache aufzubauen – indem kleinere, wiederverwendbare Parser-Funktionen zusammengesetzt werden. Um diese Flexibilität zu erreichen, brauchen wir zunächst einen Basis-Parser. Definieren wir dafür ein Interface. Unser Parser erhält den verbleibenden, noch unverarbeiteten String als Input und gibt entweder ein Success- oder Failure-Objekt zurück, das signalisiert, ob das Parsing erfolgreich war.
Nachdem wir das Konzept von Parser Combinators verstanden haben, definieren wir die nötigen Interfaces, Helper-Typen und Utility-Funktionen:
// -- Ergebnis-Typen ---------------------------------------------------
interface Success<T = string> {
parsedData: T;
remainder: string;
success: true;
}
interface Failure {
message: string;
success: false;
}
// -- Parser-Typ ------------------------------------------------------
type Parser<T = string> = (input: string) => Success<T> | Failure;
// -- Utility-Typen ---------------------------------------------------
type UnwrapParser<T> = T extends Parser<infer U> ? U : T;
type UnwrapParsers<T extends any[], Acc extends any[] = []> =
T extends [infer Head, ...infer Rest]
? UnwrapParsers<Rest, [...Acc, UnwrapParser<Head>]>
: Acc;
// -- Utility-Funktionen --------------------------------------------------
function success<T = string>(args:{ parsedData:T, remainder: string } ): Success<T> {
return { success:true, ...args }
}
function failure(message?:string ): Failure {
return { success:false, message: message ?? "An error occurred." }
}
// -- Beispiel-Parser -------------------------------------------------
const parseUnsignedInteger: Parser<number> = (input) => {
const matched = input.match(/^[1-9]\d*/)
if (!matched) return failure("Input doesn't start with a number")
const num = parseInt(matched[0]!)
return isNaN(num)
? failure(`Expected number. Received NaN. Raw match: ${matched[0]}`)
: success({ parsedData: num, remainder: input.substring(matched[0].length)});
};
// -- Beispiel-Typ-Extraktion -----------------------------------------
// Extrahiert `number` aus dem Parser oben
type ParsedNumber = UnwrapParser<typeof parseUnsignedInteger>;
2. Ein grundlegender charParser
Als Nächstes implementieren wir den grundlegenden char-Parser, der als Fundament für komplexere Parser dient. Dieser Parser prüft, ob ein String mit einem bestimmten Zeichen beginnt, und gibt entsprechend ein Success- oder Failure-Result zurück. Darauf bauen wir dann später auf.
function char<T extends string>(ch:T):Parser<T> {
return function(input){
if (input[0]!==ch) return failure(`Expected input to start with "${ch}" but received "${input[0]}"`)
return success({ parsedData:ch, remainder:input.substring(1) })
}
}
Mit unserem char-Parser können wir nun testen, wie er funktioniert:
const parseA = char("a")
console.log(parseA("abc")) // Erfolg: { parsedData: "a", remainder: "bc" }
console.log(parseA("xyz")) // Fehler: { message: "Expected input to start with \"a\" but received \"x\"" }
Dies zeigt, wie unser Parser ein bestimmtes Zeichen am Anfang eines Input-Strings erkennt und entweder erfolgreich oder mit Fehler reagiert. Damit können wir zu komplexeren Parsern übergehen.
Implementieren wir noch einen weiteren einfachen Parser namens zero, der das Zeichen "0" matcht. Er ergänzt unseren bestehenden char-Parser und hilft später beim Aufbau von komplexeren Zahlenparsern:
const zero = char("0")
console.log(zero("0123")) // Erfolg: { parsedData: "0", remainder: "123" }
console.log(zero("abc")) // Fehler: { message: "Expected input to start with \"0\" but received \"a\"" }
3. Combining Parsers: sequence, or, many, optional
Als Nächstes kommen die eigentlichen Combinators. Mit ihnen lassen sich zwei oder mehr Parser zu größeren, mächtigeren Parsern zusammenfügen.
sequence
Der sequence-Combinator nimmt mehrere Parser und prüft, ob sie alle in einer bestimmten Reihenfolge erfolgreich sind. Scheitert ein Parser, schlägt die gesamte Sequenz fehl.
function sequence<const T extends Parser<any>[]>(parsers: T): Parser<UnwrapParsers<T>> {
return function(remainder){
const parsedData: UnwrapParsers<T> = [] as any;
for (const parser of parsers) {
const result = parser(remainder);
if (!result.success) return result;
remainder = result.remainder;
parsedData.push(result.parsedData as never);
}
return success({ parsedData, remainder });
}
}
or
Der or-Combinator nimmt mehrere Parser und gibt das Ergebnis des ersten erfolgreich matchenden Parsers zurück. Wenn alle Parser fehlschlagen, wird ein Failure zurückgegeben.
function or<const T extends Parser<any>[]>(parsers: T): Parser<UnwrapParser<T[number]>> {
return function(remainder){
for (const parser of parsers) {
const result = parser(remainder);
if (!result.success) continue;
return result;
}
return failure(`Expected any parser to match`);
}
}
many
Der many-Combinator nimmt einen einzelnen Parser und versucht, ihn null- oder beliebig oft zu matchen. Das Ergebnis ist ein Array der parse-Ergebnisse.
function many<T>(parser: Parser<T>):Parser<T[]>{
return function(remainder){
const parsedData: T[] = [];
while (true){
const result = parser(remainder)
if (!result.success) return success({ parsedData, remainder });
// Hinweis: Wenn der Parser keinen Fortschritt macht, resultiert dies in einer Endlosschleife
if (remainder === result.remainder) return success({ parsedData, remainder });
parsedData.push(result.parsedData);
remainder = result.remainder;
}
}
}
optional
Der optional-Combinator nimmt einen Parser und versucht, ihn null- oder einmal zu matchen. Falls der Parser fehlschlägt, gibt optional trotzdem ein Success mit null (oder einem beliebigen Default-Wert) zurück.
function optional<T>(parser: Parser<T>):Parser<T | null>{
return function(remainder){
const result = parser(remainder);
if (result.success) return result;
return success({ parsedData: null, remainder });
}
}
Mit diesen Parsern können wir nun Parser zu komplexeren Gebilden kombinieren:
const one = char("1");
const two = char("2");
// ...
const nine = char("0");
const digit = or([zero, one,/*...*/, nine])
const oneToNine = or([one,/*...*/, nine])
const unsignedInteger = sequence([oneToNine, many(digit)])
An dieser Stelle würde unsignedInteger einen String wie "1234" parsen und als Array von Zeichen ['1',['2','3','4']] (plus remainder) zurückgeben.
4. Ein Parse-Ergebnis mit map transformieren
Bisher können wir nur die Struktur eines Strings prüfen und eine Art AST der gematchten Parser erhalten. Um das volle Potenzial der Parser Combinators auszuschöpfen, fehlt noch der Schritt, das Parse-Ergebnis zu transformieren. Hierfür führen wir die map-Funktion ein. Sie nimmt einen Parser und wandelt das geparste Ergebnis T in einen beliebigen Typ U um – und gibt wiederum einen Parser zurück. Schauen wir uns die Implementierung an:
function map<T,U>(parser: Parser<T>,cb: (inner:T) => U): Parser<U> {
return function(remainder){
const result = parser(remainder);
if (!result.success) return result;
return success({
...result,
parsedData: cb(result.parsedData),
});
}
}
Nun sehen wir uns an, wie wir die map-Funktion verwenden können, um das Ergebnis unseres unsignedInteger-Parsers in eine Zahl zu verwandeln.
5. Ein einfacher Math-Expression-Parser
Jetzt können wir unseren Parser für mathematische Ausdrücke bauen. Die wichtigsten Schritte und Rahmenbedingungen:
- Nur nicht-negative Ganzzahlen (keine Floats und keine Sequenzen wie
+-+---4). - Die Operatoren
+,,,/. - Klammern
(,)für Gruppen.
Operator-Präzedenz
Die Reihenfolge der Operatoren ist entscheidend:
- Klammern haben die höchste Präzedenz.
- Multiplikation (``) und Division (
/) folgen. - Addition (
+) und Subtraktion (``) haben die niedrigste Präzedenz.
Statt die Präzedenz manuell zu handhaben, sorgen wir implizit durch die Reihenfolge unserer Parser dafür, dass die Regeln eingehalten werden.
Grammatik
Wir verwenden etwa diese Grammatik:
- factor → number | '(' expression ')'
- term → factor ((' * ' | '/' ) factor)*
- expression → term (('+' | '-') term)*
Jede nachfolgende Regel ist für eine niedrigere Präzedenzstufe zuständig.
High-Level-Struktur
const TokenParser = {
// Alle Token und Sonderzeichen kommen hier hinein
};
function mathExpression(input: string): Success<number> | Failure {
/**
* Wir bauen unseren Parser in mehreren Schritten auf:
* 1. Klammern/Factor-Parser
* 2. Multiplikation/Division (term)
* 3. Addition/Subtraktion (expression)
*/
return expression(input);
}
Unten definieren wir die Bausteine – Parentheses & factor, term (Multiplikation/Division) und expression (Addition/Subtraktion) – und zeigen, wie alles zusammenpasst.
Parentheses und factor parsing
- Klammern: Wir parsen eine öffnende Klammer
(, parsen rekursiv einen Ausdruck, und dann eine schließende Klammer). - Factor: Ein Factor ist entweder ein geklammerter Ausdruck oder ein
unsignedInteger.
const TokenParser = {
OPENING_PAR: char("("),
CLOSING_PAR: char(")"),
/* ...other tokens... */
}
function mathExpression(input:string):Success<number> | Failure {
// Faktor = '(' expression ')' | unsignedInteger
const factor:Parser<number> = (input) => or([
map(
sequence([
TokenParser.OPENING_PAR,
mathExpression,
TokenParser.CLOSING_PAR
]),
// wir ignorieren die Klammern selbst und geben nur den geparsten Unterausdruck zurück
([, expr]) => expr
),
unsignedInteger
])(input);
// ... nächste Schritte (term, expression) ...
return expression(input);
}
Multiplikation und Division
Ein term beginnt mit einem factor, gefolgt von null oder mehr * factor oder / factor. Wir speichern jeden Operator und Operand in einem Array und werten sie dann der Reihe nach aus.
const TokenParser = {
/* ... */
MUL: char("*"),
DIV: char("/"),
MUL_OR_DIV: or([char("*"), char("/")]),
/* ... */
};
function mathExpression(input: string): Success<number> | Failure {
// ... Faktordefinition oben ...
// Ein "term" ist ein "factor", optional gefolgt von (* factor) oder (/ factor)
const term = sequence([
factor,
many(
map(
sequence([
TokenParser.MUL_OR_DIV,
factor
]),
([op, val]) => ({ op, val })
)
)
]);
// Dieses Zwischenergebnis in einer map-Funktion auswerten
const evaluatedTerm = map(term, ([first, rest]) => {
let result = first;
for (const { op, val } of rest) {
if (op === "*") result *= val;
else result /= val;
}
return result;
});
// ... nächster Schritt (expression) ...
return expression(input);
}
Addition und Subtraktion
Zum Schluss verarbeitet der expression-Parser die niedrigst-priorisierten Operationen (+ und -). Er erwartet einen term, gefolgt von beliebig vielen Sequenzen aus + term oder - term.
const TokenParser = {
/* ... */
ADD: char("+"),
SUB: char("-"),
ADD_OR_SUB: or([char("+"), char("-")])
/* ... */
};
function mathExpression(input: string): Success<number> | Failure {
// ... term-Definition oben ...
// Ein "expression" ist ein "term", dem optional (+ term) oder (- term) folgen kann
const expression = sequence([
evaluatedTerm,
many(
map(
sequence([
TokenParser.ADD_OR_SUB,
evaluatedTerm
]),
([op, val]) => ({ op, val })
)
)
]);
// Den Ausdruck auswerten
const evaluatedExpression = map(expression, ([first, rest]) => {
let result = first;
for (const { op, val } of rest) {
if (op === "+") result += val;
else result -= val;
}
return result;
});
// Das finale Parse-Ergebnis zurückgeben
return evaluatedExpression(input);
}
6. Testing des Math-Expression-Parsers
Sobald unser Parser zusammengesetzt ist, können wir ihn testen:
console.log(mathExpression("1+1")); // Erfolg: 2
console.log(mathExpression("1*2")); // Erfolg: 2
console.log(mathExpression("(1+2)*3")) // Erfolg: 9
console.log(mathExpression("(1+2)* 3"))
// Überraschung! Dies schlägt nicht fehl, obwohl ein Leerzeichen vor der 3
// übrig bleibt und nicht geparst wird.
Warum das letzte Beispiel nicht fehlschlägt
Das letzte Beispiel "(1+2)* 3" gibt trotzdem ein Success zurück, weil unser Parser nie explizit den gesamten String konsumiert. Nach dem Parsen von (1+2) sieht er )* als gültige Tokens und lässt das Leerzeichen plus 3 als unbenutzten remainder übrig. Ein Success bedeutet hier lediglich, dass ein gültiger Ausdruck am Anfang erkannt wurde; es garantiert nicht, dass der ganze Input geparst wurde.
Einen vollständigen Parse erzwingen (EOF)
Wenn wir sicherstellen möchten, dass jeder Buchstabe im Input konsumiert wird – also wirklich nur ein einzelner Mathe-Ausdruck im Input steht und nichts weiter –, können wir ein "end-of-file"-Token erzwingen. Ein einfacher Trick dafür ist, nach dem Hauptparser noch ein leeres Zeichen (char("")) zu parsen:
const mathExpressionWithEoF = sequence([mathExpression,char("")])
console.log(mathExpressionWithEoF("(1+2)* 3") // Fehler
Wenn am Ende noch Input übrig ist, schlägt das Matchen von char("") fehl, was zu einem Failure statt eines Teilerfolgs führt.
7. Zusammenfassung & Ausblick
Wir haben:
- Kleine, komponierbare Parser Combinators für Zeichen, Sequenzen, Alternativen, Wiederholungen und optionale Tokens definiert
- Einen Math-Expression-Parser gebaut, der Klammern, Multiplikation/Division und Addition/Subtraktion mit korrekter Operator-Präzedenz verarbeitet
- Typensicherheit in TypeScript gewährleistet
- Gezeigt, wie man per EOF-Check einen vollständigen Parse erzwingt
Diese Herangehensweise bietet ein sauberes, gut lesbares und erweiterbares Fundament zum Parsen und Auswerten arithmetischer Ausdrücke in TypeScript. Sie lässt sich leicht um Features wie negative Zahlen, Fließkommazahlen oder komplexere Grammatikregeln ergänzen.
Darüber hinaus kannst du diese kleine Parsing-Bibliothek erweitern um:
- Erweitertes Debugging und Tracing: Optionale Logs in jedem Combinator, um Parsing-Entscheidungen zu verfolgen.
- Error Recovery: Strategien zum Umgang mit unerwarteten Tokens (z.B. Überspringen, um weiterparsen zu können).
- Reichhaltigere Combinators: Spezialisierte Combinators für Whitespace, Kommentare oder andere syntaktische Konstrukte.
- Abstract Syntax Trees (AST): Anstatt Ergebnisse direkt zu berechnen, könntest du Input erst in einen Baum umwandeln, um weitere Analysen oder Codegenerierung zu betreiben.
- Domain-spezifische Erweiterungen: Custom-Funktionen, Variablenreferenzen oder spezialisierte Operatoren.
Am Ende bieten Parser Combinators eine flexible, typsichere und hochgradig komponierbare Herangehensweise an Language Design in TypeScript – du kannst deinen Parser genau so gestalten, wie du ihn brauchst.
Viel Spaß beim Parsen!
PS: Hier ist der Code: https://tsplay.dev/NndAkW
