CKTIS / JavaScript
Konečné automaty
Konečný automat popisuje chování pomocí stavů a přechodů závislých na vstupu. Příklad automatu pro parsování CSV ukazuje, jak explicitní stav odlišuje oddělovač polí od čárky uvnitř uvozovek a pomáhá odhalit neplatný vstup.
Verze: 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.
Syntaxe
state = transition(state, input);Deterministický konečný automat (FSM) má konečnou množinu stavů, počáteční stav a pravidla přechodů. Aktuální stav a následující vstupní symbol jednoznačně určují další přechod. Pravidlo může také přidat data do výstupu nebo signalizovat chybu. Jde o návrhový vzor, nikoli o samostatnou konstrukci JavaScriptu; state = transition(state, input) vyjadřuje jeho obecnou myšlenku.
Příklad automatu pro parsování CSV zpracovává jeden záznam. START označuje začátek pole, BARE pole bez uvozovek, QUOTED vnitřek pole v uvozovkách a AFTER_QUOTE pozici po případné ukončovací uvozovce. Čárka odděluje pole mimo QUOTED. Ve stavu AFTER_QUOTE druhá uvozovka přidá jeden znak " a obnoví stav QUOTED.
Také konec vstupu potřebuje pravidlo: QUOTED znamená neuzavřené pole, zatímco ostatní stavy umožňují přidat poslední pole. Tím se zachová prázdné pole za koncovou čárkou. Prázdný vstup zde znamená jedno prázdné pole. Parser odmítá uvozovku v poli bez uvozovek a znaky jiné než čárku po ukončovací uvozovce; bílé znaky neodstraňuje. Záměrně odmítá každý CR a LF, i uvnitř uvozovek, takže nejde o úplný parser souborů CSV.
Množina řídicích stavů je konečná, ale buffery field a fields konečné nejsou; celý program s rostoucími buffery proto není automat s výhradně konečnou pamětí. Příklad používá syntaxi ECMAScript 2015 nebo starší, bez Web APIs. Specifikace ECMAScript definuje použité jazykové konstrukce, nikoli pravidla CSV tohoto parseru; console.log poskytuje běhové prostředí. Otestujte platné přechody, chyby a konec vstupu v každém stavu.
Příklady
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""",')));Výsledek
["Ada","x,y","say \"hi\"",""]
Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.