CKTIS / JavaScript
Endliche Automaten
Ein endlicher Automat beschreibt Verhalten durch Zustände und eingabeabhängige Übergänge. Das Beispiel eines CSV-Parsing-Automaten zeigt, wie ein expliziter Zustand ein Feldtrennzeichen von einem Komma innerhalb von Anführungszeichen unterscheidet und ungültige Eingaben erkennen hilft.
Version: A finite-state machine is a design pattern, not a versioned JavaScript feature. The CSV parser uses ECMAScript 2015 features and requires no browser APIs. The example's separate logging call uses host-provided console.log.
Syntax
state = transition(state, input);Ein deterministischer endlicher Automat (FSM) hat eine endliche Menge von Zuständen, einen Anfangszustand und Übergangsregeln. Der aktuelle Zustand und das nächste Eingabesymbol bestimmen eindeutig den nächsten Übergang. Eine Regel kann außerdem Daten an die Ausgabe anhängen oder einen Fehler melden. Dies ist ein Entwurfsmuster und kein eigenes JavaScript-Konstrukt; state = transition(state, input) drückt die allgemeine Idee aus.
Das Beispiel eines CSV-Parsing-Automaten verarbeitet einen Datensatz. START bezeichnet den Feldanfang, BARE ein Feld ohne Anführungszeichen, QUOTED den Inhalt eines Feldes in Anführungszeichen und AFTER_QUOTE die Position nach einem möglichen schließenden Anführungszeichen. Außerhalb von QUOTED trennt ein Komma die Felder. In AFTER_QUOTE hängt ein zweites Anführungszeichen ein einzelnes "-Zeichen an und setzt den Zustand auf QUOTED zurück.
Auch für das Ende der Eingabe ist eine Regel erforderlich: QUOTED bedeutet, dass ein Feld nicht geschlossen wurde; in den anderen Zuständen kann das letzte Feld angehängt werden. So bleibt nach einem abschließenden Komma ein leeres Feld erhalten. Eine leere Eingabe bedeutet hier ein leeres Feld. Der Parser weist Anführungszeichen in nicht umschlossenen Feldern und Zeichen außer einem Komma nach einem schließenden Anführungszeichen zurück; Leerraum wird nicht entfernt. Er weist absichtlich jedes CR und LF zurück, auch innerhalb von Anführungszeichen, und ist daher kein vollständiger Parser für CSV-Dateien.
Die Menge der Steuerzustände ist endlich, die Puffer field und fields sind es nicht; das gesamte Programm mit wachsenden Puffern ist daher kein Automat mit ausschließlich endlichem Speicher. Das Beispiel verwendet ECMAScript-Syntax von 2015 oder älter und keine Web APIs. Die ECMAScript-Spezifikation definiert die verwendeten Sprachkonstrukte, nicht die CSV-Regeln dieses Parsers; console.log stellt die Laufzeitumgebung bereit. Teste gültige Übergänge, Fehler und das Eingabeende in jedem Zustand.
Beispiele
function parseCsvRecord(text) {
const fields = [];
let field = "";
let state = "START";
for (const ch of text) {
if (ch === "\r" || ch === "\n") {
throw new SyntaxError("Line breaks are not supported");
}
switch (state) {
case "START":
if (ch === '"') state = "QUOTED";
else if (ch === ",") fields.push("");
else { field += ch; state = "BARE"; }
break;
case "BARE":
if (ch === ",") {
fields.push(field); field = ""; state = "START";
} else if (ch === '"') {
throw new SyntaxError("Quote in unquoted field");
} else field += ch;
break;
case "QUOTED":
if (ch === '"') state = "AFTER_QUOTE";
else field += ch;
break;
case "AFTER_QUOTE":
if (ch === '"') { field += ch; state = "QUOTED"; }
else if (ch === ",") {
fields.push(field); field = ""; state = "START";
} else throw new SyntaxError("Unexpected character after quote");
break;
default:
throw new Error("Invalid state");
}
}
if (state === "QUOTED") throw new SyntaxError("Unclosed quote");
fields.push(field);
return fields;
}
console.log(JSON.stringify(parseCsvRecord('Ada,"x,y","say ""hi""",')));Ergebnis
["Ada","x,y","say \"hi\"",""]
Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.