CKTIS / JavaScript
Konečné automaty
Konečný automat opisuje správanie pomocou stavov a prechodov závislých od vstupu. Príklad automatu na parsovanie CSV ukazuje, ako explicitný stav odlišuje oddeľovač polí od čiarky v úvodzovkách a pomáha odhaliť neplatný vstup.
Verzia: 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);Deterministický konečný automat (FSM) má konečnú množinu stavov, počiatočný stav a pravidlá prechodov. Aktuálny stav a nasledujúci vstupný symbol jednoznačne určujú ďalší prechod. Pravidlo môže tiež pridať údaje do výstupu alebo signalizovať chybu. Ide o návrhový vzor, nie o samostatnú konštrukciu JavaScriptu; state = transition(state, input) vyjadruje jeho všeobecnú myšlienku.
Príklad automatu na parsovanie CSV spracúva jeden záznam. START označuje začiatok poľa, BARE pole bez úvodzoviek, QUOTED vnútro poľa v úvodzovkách a AFTER_QUOTE pozíciu po prípadnej uzatváracej úvodzovke. Čiarka oddeľuje polia mimo QUOTED. V stave AFTER_QUOTE druhá úvodzovka pridá jeden znak " a obnoví stav QUOTED.
Aj koniec vstupu potrebuje pravidlo: QUOTED znamená neuzavreté pole, kým ostatné stavy umožňujú pridať posledné pole. Tým sa zachová prázdne pole po koncovej čiarke. Prázdny vstup tu znamená jedno prázdne pole. Parser odmieta úvodzovku v poli bez úvodzoviek a znaky iné než čiarku po uzatváracej úvodzovke; biele znaky neodstraňuje. Zámerne odmieta každý CR a LF, aj vnútri úvodzoviek, takže nejde o úplný parser súborov CSV.
Množina riadiacich stavov je konečná, ale buffery field a fields konečné nie sú; celý program s rastúcimi buffermi preto nie je automat s výhradne konečnou pamäťou. Príklad používa syntax ECMAScript 2015 alebo staršiu, bez Web APIs. Špecifikácia ECMAScript definuje použité jazykové konštrukcie, nie pravidlá CSV tohto parsera; console.log poskytuje runtime prostredie. Otestujte platné prechody, chyby a koniec vstupu v každom stave.
Prí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ýsledok
["Ada","x,y","say \"hi\"",""]
Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.