CKTIS / JavaScript
Automaty o skończonej liczbie stanów
Automat o skończonej liczbie stanów opisuje zachowanie przez stany i przejścia zależne od wejścia. Przykład automatu do analizy składniowej CSV pokazuje, jak jawny stan pozwala odróżnić separator pola od przecinka wewnątrz cudzysłowów oraz wykrywać błędne dane.
Wersja: 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.
Składnia
state = transition(state, input);Deterministyczny automat o skończonej liczbie stanów (FSM) ma skończony zbiór stanów, stan początkowy i reguły przejść. Bieżący stan oraz następny symbol wejścia jednoznacznie określają kolejne przejście. Reguła może też dopisywać dane do wyniku lub zgłaszać błąd. To wzorzec projektowy, nie osobna konstrukcja JavaScript; zapis state = transition(state, input) przedstawia jego ogólną ideę.
Przykład CSV parsing state machine przetwarza jeden rekord. START oznacza początek pola, BARE pole bez cudzysłowów, QUOTED wnętrze pola w cudzysłowach, a AFTER_QUOTE pozycję po potencjalnym cudzysłowie zamykającym. Przecinek rozdziela pola poza QUOTED. W AFTER_QUOTE drugi cudzysłów dopisuje jeden znak " i przywraca QUOTED.
Koniec wejścia także wymaga reguły: QUOTED oznacza niedomknięte pole, a pozostałe stany pozwalają dopisać ostatnie pole. Dzięki temu końcowy przecinek zachowuje puste pole. Puste wejście oznacza tutaj jedno puste pole. Parser odrzuca cudzysłów w polu bez cudzysłowów i znaki po zamknięciu pola inne niż przecinek; nie usuwa odstępów. Celowo odrzuca każdy CR i LF, również wewnątrz cudzysłowów, więc nie jest pełnym parserem plików CSV.
Skończony jest zbiór stanów sterujących, nie bufory field i fields; cały program z rosnącymi buforami nie jest więc automatem o wyłącznie skończonej pamięci. Przykład korzysta ze składni ECMAScript 2015 lub starszej, bez Web APIs. Specyfikacja ECMAScript definiuje użyte konstrukcje języka, a nie reguły tego parsera CSV; console.log zapewnia środowisko uruchomieniowe. Przy testowaniu sprawdzaj zarówno poprawne przejścia, jak i błędy oraz koniec wejścia w każdym stanie.
Przykłady
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""",')));Wynik
["Ada","x,y","say \"hi\"",""]
Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.