01 · Problem
Wofür braucht man das?
Protokolle und Grammatiken brauchen Sequenz, Alternativen, Wiederholung und gute Fehlerpositionen, ohne einen monolithischen handgeschriebenen Parser zu erzeugen.
02 · Denkmodell
Das mentale Modell
Ein Parser ist eine pure Funktion von Inputzustand zu Erfolg plus neuem Offset oder Fehler plus Position. Kombinatoren verkabeln diese Zustandsübergänge.
Kombiniert byteorientierte Parser mit korrekten Input-Ausschnitten und Fortschrittsprüfung bei Wiederholung. Die Bibliothek besitzt viele Kombinatoren; Regressionstests konzentrieren sich auf Kombination, View-Grenzen und Terminierung.
03 · Kontrollfluss
Was passiert in welcher Reihenfolge?
- Input als unveränderliche Byteview plus aktuellen Offset modellieren.
- Primitive lesen genau einen Vertrag und liefern neuen Zustand oder erwartetes Token.
- Sequenz reicht Erfolg weiter; Alternative startet vom ursprünglichen Zustand.
- Bei mehreren Fehlern die weiteste Position und erwartete Tokens zusammenführen.
- parseAll kombiniert den Zielparser mit einem expliziten End-of-input-Parser.
04 · Bauteile
Die entscheidenden Verträge
Parser / map / chain / runKombiniert und startet Parser-Zustandstransformationen.str / char / regex / sequenceOf / choice / many / sepByErzeugt Primitive, Alternativen und Wiederholung mit Fortschrittsprüfung.05 · Selbst bauen
Selbst implementieren
Beginne mit einem minimalen Result-Typ und map/flatMap/orElse. Wiederholung und Komfortsyntax kommen erst nach korrekter Fortschritts- und Fehlersemantik.
- Definiere State, Success und Failure mit explizitem Offset.
- Implementiere map, flatMap und orElse ohne den Eingabestate zu mutieren.
- Breche many ab, wenn ein erfolgreicher Parser den Offset nicht erhöht.
type State = { input: Uint8Array; offset: number };
type Result<T> =
| { ok: true; value: T; state: State }
| { ok: false; offset: number; expected: Set<string> };
class Parser<T> {
constructor(readonly parse: (state: State) => Result<T>) {}
map<U>(fn: (value: T) => U) {
return new Parser<U>(state => {
const result = this.parse(state);
return result.ok ? { ...result, value: fn(result.value) } : result;
});
}
}06 · Verifizieren
Was solltest du testen?
- Sequenz, Alternative und Backtracking erhalten den korrekten ursprünglichen oder fortgeschrittenen Offset.
- many erkennt einen erfolgreichen Nullfortschritt und terminiert mit einem definierten Fehler.
- UTF-8, TypedArray-Slices, Inputende und der weiteste kombinierte Fehler werden geprüft.
Selbst ausprobieren
Formuliere die erste Prüfaussage als fehlschlagenden Test, implementiere die kleinste Korrektur und ergänze einen Grenzfall.
Sequenz, Alternative und Backtracking erhalten den korrekten ursprünglichen oder fortgeschrittenen Offset.
Ansatz vergleichen
Dein Test sollte beim gezielten Verletzen der Invariante fehlschlagen und nach der Korrektur wieder bestehen. Halte den Aufbau deterministisch und prüfe ein beobachtbares Ergebnis.
07 · Grenzen
Kompromisse und Stolperfallen
- Vollständiges Backtracking kann exponentiell werden; commit/cut begrenzt bewusste Alternativen.
- Bytepositionen sind für Binärdaten korrekt, für Nutzerfehler in Unicode-Texten aber erklärungsbedürftig.
- Ein gemeinsamer Parser für Text und Binärdaten erhöht Flexibilität und Typkomplexität zugleich.
Die Bibliothek besitzt viele Kombinatoren; Regressionstests konzentrieren sich auf Kombination, View-Grenzen und Terminierung.
08 · Weiterdenken
Quellcode und verwandte Ideen
yarn tsx packages/parser-combinator/examples/basic.ts