CKTIS / JavaScript
Automates à états finis
Un automate à états finis décrit un comportement au moyen d’états et de transitions dépendant de l’entrée. L’exemple d’automate d’analyse CSV montre comment un état explicite distingue un séparateur de champ d’une virgule entre guillemets et aide à détecter les entrées invalides.
Version : 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.
Syntaxe
state = transition(state, input);Un automate fini déterministe (FSM) possède un ensemble fini d’états, un état initial et des règles de transition. L’état courant et le prochain symbole d’entrée déterminent de façon unique la transition suivante. Une règle peut aussi ajouter des données au résultat ou signaler une erreur. Il s’agit d’un modèle de conception, et non d’une construction JavaScript distincte ; state = transition(state, input) en exprime l’idée générale.
L’exemple d’automate d’analyse CSV traite un enregistrement. START désigne le début d’un champ, BARE un champ sans guillemets, QUOTED l’intérieur d’un champ entre guillemets et AFTER_QUOTE la position après un éventuel guillemet fermant. Une virgule sépare les champs en dehors de QUOTED. Dans AFTER_QUOTE, un deuxième guillemet ajoute un caractère " et rétablit l’état QUOTED.
La fin de l’entrée nécessite aussi une règle : QUOTED signifie qu’un champ n’est pas fermé, tandis que les autres états permettent d’ajouter le dernier champ. Cela préserve le champ vide après une virgule finale. Une entrée vide correspond ici à un champ vide. Le parseur rejette un guillemet dans un champ non délimité par des guillemets ainsi que tout caractère autre qu’une virgule après un guillemet fermant ; il ne supprime pas les espaces. Il rejette délibérément chaque CR et LF, même entre guillemets : ce n’est donc pas un parseur complet de fichiers CSV.
L’ensemble des états de contrôle est fini, mais les tampons field et fields ne le sont pas ; le programme entier, avec ses tampons qui grandissent, n’est donc pas une machine à mémoire finie. L’exemple utilise la syntaxe ECMAScript 2015 ou antérieure, sans Web APIs. La spécification ECMAScript définit les constructions du langage utilisées, pas les règles CSV de ce parseur ; console.log est fourni par l’environnement d’exécution. Testez les transitions valides, les erreurs et la fin de l’entrée dans chaque état.
Exemples
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""",')));Résultat
["Ada","x,y","say \"hi\"",""]
Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.