База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / JavaScript

Крайни автомати

Крайният автомат описва поведение чрез състояния и преходи, зависещи от входа. Примерът с автомат за анализиране на CSV показва как изрично състояние различава разделител на поле от запетая в кавички и помага за откриване на невалиден вход.

Версия: 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.

Синтаксис

state = transition(state, input);

Детерминираният краен автомат (FSM) има краен набор от състояния, начално състояние и правила за преход. Текущото състояние и следващият входен символ еднозначно определят следващия преход. Едно правило може също да добави данни към резултата или да сигнализира за грешка. Това е проектен шаблон, а не отделна конструкция на JavaScript; state = transition(state, input) изразява общата идея.

Примерът с автомат за анализиране на CSV обработва един запис. START означава начало на поле, BARE — поле без кавички, QUOTED — съдържанието на поле в кавички, а AFTER_QUOTE — позицията след евентуална затваряща кавичка. Запетая разделя полетата извън QUOTED. В AFTER_QUOTE втора кавичка добавя един знак " и възстановява състоянието QUOTED.

За края на входа също е необходимо правило: QUOTED означава незатворено поле, а останалите състояния позволяват добавянето на последното поле. Така празното поле след завършваща запетая се запазва. Тук празният вход означава едно празно поле. Парсерът отхвърля кавичка в поле без кавички и символи, различни от запетая, след затваряща кавичка; не премахва интервалите. Умишлено отхвърля всеки CR и LF, дори в кавички, затова не е пълен парсер на CSV файлове.

Наборът от управляващи състояния е краен, но буферите field и fields не са; следователно цялата програма с нарастващи буфери не е автомат с изцяло крайна памет. Примерът използва синтаксис на ECMAScript 2015 или по-стар, без Web APIs. Спецификацията на ECMAScript определя използваните езикови конструкции, а не CSV правилата на този парсер; console.log се предоставя от средата за изпълнение. Проверете валидните преходи, грешките и края на входа във всяко състояние.

Примери

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

Резултат

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

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници