CKTIS / JavaScript
Eindige-toestandsautomaten
Een eindige-toestandsautomaat beschrijft gedrag met toestanden en invoerafhankelijke overgangen. Het voorbeeld van een CSV-parseerautomaat laat zien hoe een expliciete toestand een veldscheidingsteken onderscheidt van een komma tussen aanhalingstekens en helpt ongeldige invoer te herkennen.
Versie: 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);Een deterministische eindige-toestandsautomaat (FSM) heeft een eindige verzameling toestanden, een begintoestand en overgangsregels. De huidige toestand en het volgende invoersymbool bepalen eenduidig de volgende overgang. Een regel kan ook gegevens aan de uitvoer toevoegen of een fout aangeven. Dit is een ontwerppatroon, geen afzonderlijk JavaScript-construct; state = transition(state, input) geeft het algemene idee weer.
Het voorbeeld van de CSV-parseerautomaat verwerkt één record. START betekent het begin van een veld, BARE een veld zonder aanhalingstekens, QUOTED de inhoud van een veld tussen aanhalingstekens en AFTER_QUOTE de positie na een mogelijk afsluitend aanhalingsteken. Buiten QUOTED scheidt een komma de velden. In AFTER_QUOTE voegt een tweede aanhalingsteken één "-teken toe en herstelt het de toestand QUOTED.
Ook voor het einde van de invoer is een regel nodig: QUOTED betekent dat een veld niet is afgesloten; in de andere toestanden kan het laatste veld worden toegevoegd. Zo blijft een leeg veld na een afsluitende komma behouden. Lege invoer betekent hier één leeg veld. De parser weigert een aanhalingsteken in een veld zonder aanhalingstekens en tekens anders dan een komma na een afsluitend aanhalingsteken; witruimte wordt niet verwijderd. Hij weigert bewust elke CR en LF, ook binnen aanhalingstekens, en is dus geen volledige parser voor CSV-bestanden.
De verzameling besturingstoestanden is eindig, maar de buffers field en fields zijn dat niet; het volledige programma met groeiende buffers is daarom geen machine met uitsluitend eindig geheugen. Het voorbeeld gebruikt ECMAScript 2015-syntaxis of ouder, zonder Web APIs. De ECMAScript-specificatie definieert de gebruikte taalconstructies, niet de CSV-regels van deze parser; console.log wordt door de runtime-omgeving geleverd. Test geldige overgangen, fouten en het einde van de invoer in elke toestand.
Voorbeelden
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""",')));Resultaat
["Ada","x,y","say \"hi\"",""]
De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.