Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

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.

Zdroje