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\"",""]
Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.