Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

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.

Zdroje