Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

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.

Źródła