Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

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.

Fontes