CKTIS / JavaScript
Máquinas de estados finitos
Uma máquina de estados finitos descreve o comportamento através de estados e transições dependentes da entrada. O exemplo de máquina de estados para análise de CSV mostra como um estado explícito distingue um separador de campo de uma vírgula entre aspas e ajuda a detetar entradas inválidas.
Versão: 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.
Sintaxe
state = transition(state, input);Uma máquina de estados finitos determinística (FSM) tem um conjunto finito de estados, um estado inicial e regras de transição. O estado atual e o símbolo de entrada seguinte determinam de forma única a transição seguinte. Uma regra também pode acrescentar dados ao resultado ou assinalar um erro. Trata-se de um padrão de conceção, não de uma construção JavaScript independente; state = transition(state, input) exprime a ideia geral.
O exemplo de máquina de estados para análise de CSV processa um registo. START indica o início de um campo, BARE um campo sem aspas, QUOTED o interior de um campo entre aspas e AFTER_QUOTE a posição após uma possível aspa de fecho. Uma vírgula separa os campos fora de QUOTED. Em AFTER_QUOTE, uma segunda aspa acrescenta um carácter " e repõe QUOTED.
O fim da entrada também precisa de uma regra: QUOTED significa que há um campo por fechar, enquanto os outros estados permitem acrescentar o campo final. Assim, preserva-se um campo vazio após uma vírgula final. Neste caso, uma entrada vazia corresponde a um campo vazio. O analisador rejeita uma aspa num campo sem aspas e caracteres que não sejam uma vírgula após uma aspa de fecho; não remove espaços em branco. Rejeita deliberadamente qualquer CR e LF, mesmo dentro de aspas, pelo que não é um analisador completo de ficheiros CSV.
O conjunto de estados de controlo é finito, mas os buffers field e fields não são; por isso, o programa completo, com buffers que crescem, não é uma máquina com memória exclusivamente finita. O exemplo utiliza sintaxe ECMAScript 2015 ou anterior, sem Web APIs. A especificação ECMAScript define as construções da linguagem utilizadas, não as regras CSV deste analisador; console.log é fornecido pelo ambiente de execução. Teste as transições válidas, os erros e o fim da entrada em cada estado.
Exemplos
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""",')));Resultado
["Ada","x,y","say \"hi\"",""]
O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.