Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / JavaScript

Končni avtomati

Končni avtomat opisuje vedenje s stanji in prehodi, odvisnimi od vhoda. Primer avtomata za razčlenjevanje CSV pokaže, kako izrecno stanje loči ločilo polj od vejice znotraj narekovajev in pomaga zaznati neveljaven vhod.

Različica: 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.

Sintaksa

state = transition(state, input);

Deterministični končni avtomat (FSM) ima končno množico stanj, začetno stanje in pravila prehodov. Trenutno stanje in naslednji vhodni simbol enolično določata naslednji prehod. Pravilo lahko tudi doda podatke v izhod ali sporoči napako. To je načrtovalski vzorec, ne samostojna konstrukcija JavaScripta; state = transition(state, input) izraža njegovo splošno zamisel.

Primer avtomata za razčlenjevanje CSV obdela en zapis. START pomeni začetek polja, BARE polje brez narekovajev, QUOTED notranjost polja v narekovajih, AFTER_QUOTE pa položaj za morebitnim zaključnim narekovajem. Zunaj stanja QUOTED vejica ločuje polja. V stanju AFTER_QUOTE drugi narekovaj doda en znak " in povrne stanje QUOTED.

Tudi konec vhoda potrebuje pravilo: QUOTED pomeni, da polje ni zaključeno, druga stanja pa dovoljujejo dodajanje zadnjega polja. Tako se ohrani prazno polje za končno vejico. Prazen vhod tukaj pomeni eno prazno polje. Razčlenjevalnik zavrne narekovaj v polju brez narekovajev in znake, ki niso vejica, za zaključnim narekovajem; presledkov ne odstranjuje. Namenoma zavrne vsak CR in LF, tudi znotraj narekovajev, zato ni popoln razčlenjevalnik datotek CSV.

Množica krmilnih stanj je končna, medtem ko medpomnilnika field in fields nista; celoten program z rastočimi medpomnilniki zato ni avtomat z izključno končnim pomnilnikom. Primer uporablja sintakso ECMAScript 2015 ali starejšo, brez Web APIs. Specifikacija ECMAScript določa uporabljene jezikovne konstrukte, ne pravil CSV tega razčlenjevalnika; console.log zagotavlja izvajalno okolje. Preizkusite veljavne prehode, napake in konec vhoda v vsakem stanju.

Primeri

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""",')));

Rezultat

["Ada","x,y","say \"hi\"",""]

Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.

Viri