26

Machine à état fini, le retour

nov
No Comments |  Posted by Etienne SOBOLE |  Category:Algorithmes, Divers

Chose promise chose due,

Je vous avais parlé de vous proposer une version plus évoluée d’automate. Effectivement dans mon précédent post, l’automate ne servait à rien si ce n’est reconnaitre une chaîne de caractère alphabétique. Je vous propose donc un automate amélioré qui dispose de deux nouvelles fonctionnalités:

  • La conversion de caractère
  • L’exécution d’une fonction a chaque traitement de caractère

Voici donc un automate qui permet de reconstruire une sorte de DOM (Document object model) à partir d’une chaîne de caractères.
L’automate doit donc trouver les TAGs dans fichier html, vérifier qu’il existent (conforme aux standard) puis créer un arbre à partir des TAGs trouvés.

Le html est insensible à la case, ce qui pose un double problème. Il faut tout d’abord s’assurer que notre automate sera capable de gérer aussi bien les minuscules que les majuscules, mais en plus il faut que lors du contrôle de la validité du TAG on soit capable de s’assurer que “div”, “Div”, “DIV”, … seront bien reconnus comme le même TAG.

Normalement un automate devrait prendre en compte tous les TAG possibles et créer tous les états permettant de reconnaître n’importe lequel de ces TAG. Si cette approche serait sans doute la plus performante, elle a le défaut de consommer énormément de mémoire. De plus vu que je code les automates à la main, la réalisation d’un tel automate deviendrai vite un cauchemars (même s’il serait assez simple de faire un petit programme pour le construire automatiquement).
J’ai opté pour une approche différente, un peu plus lente (c’est vrai) mais beaucoup moins gourmande en mémoire. Si vraiment j’avais des performances décevantes au final je pourrais toujours faire marche arrière.
Mon automate recopie les chaînes de caractères qu’il considère être des TAGs puis contrôle leur validité dans une table de hachage qui contient tous les TAGs possibles. Il en sera de même ultérieurement pour les attributs et autre mots clé du HTML.
Le problème est que “Div” et “DIV” ne donnent pas le même résultat dans une table de hachage, j’ai donc modifié la syntaxe de mon langage pour insérer dans la transition de l’état le caractère converti en minuscule. Ainsi que ma chaîne soit “Div” ou “DIV” le contrôle dans la table de hachage se fera toujours sur la chaîne “div” (en minuscule).

J’ai de plus prévu une sorte de callback appliquée (optionnellement) sur chaque transitions d’état afin de réaliser des opérations sur les octets (ou sur le buffer) qui sont traités par l’automate.

Ma chaîne test est celle-ci

$string = "
<html>
<head></hEaD>
<body>
<Div style=’hop’ class=’hop’>test de <b>gras</b>. C’est cool</ DIV>
</body>
<html>
";

J’ai inséré dans mon exemple, une class et un id, mais ils seront ignorés par l’automate. Le fait de pouvoir ignorer certain caractère est également un besoin utile lors de l’utilisation d’une machine à état fini.

La définition de l’automate est la suivante:

WaitTag:tolower
[ nt]->WaitTag <->PreTag

#
#
# TAG
#
#

PreTag:tolower
default->PreTag
[aA]->OpenTag /->PreCloseTag

OpenTag:tolower
default->WaitTag
fct->bufferise
[aA0]->OpenTag [ ]->OpenTagFound >->OpenTagFound

PreCloseTag:tolower
default->PreCloseTag
[aA]->CloseTag

CloseTag:tolower
default->WaitTag
fct->bufferise
[aA0]->CloseTag [ ]->CloseTagFound >->CloseTagFound

OpenTagFound:
default->WaitCloseTag
>->WaitTag
fct->checkOpenTag

OpenTagFound:
default->WaitCloseTag
>->WaitTag
fct->checkCloseTag

WaitCloseTag:
default->WaitCloseTag
>->WaitTag

Comme on le voit, il y a quelques nouveautés…
Tout d’abord il est possible de spécifier “tolower” derrière les noms d’état. Cela indique à l’automate que tout caractère entrant dans cet état doit être (sera) converti en minuscule avant d’être traité par la callback.
Ensuite, il devient possible de spécifier une fonction (callback) à appeler à chaque fois que l’automate entre (ou ré entre) dans un état.
Pour cet automate j’ai utilisé 3 fonctions:

  • bufferize : écrit le caractère dans un buffer
  • checkOpenTag : contrôle que le buffer est bien un TAG valide, créé dans le DOM le TAG puis remet le buffer à zero
  • checkCloseTag : contrôle que le buffer est bien un TAG valide, remonte d’un niveau dans le DOM puis remet le buffer à zero

Enfin j’ai ajouté les commentaires dans mon langage.

A présent chaque transition ne contient plus seulement le numéro de l’état suivant mais également le caractère converti (ou non) ainsi que la fonction (ou plus exactement un numéro de fonction) à appeler.
Personnellement j’ai décidé de coder tout ça sur 32 bits.
16 bits pour l’état suivant, 8 bits pour le caractère converti et 8 bits pour la fonction. Mais rien m’empêche de faire un autre choix (utiliser une structure, séparer les fonctions dans un autres espace mémoire, …)

Le code de la machine à états fini n’est guère plus compliqué que le précédent.

$etat = 0;
for ($c = 0 ; $c < strlen($chaine) ; $c++)
{
  $char = ord($chaine{$c});
  $transition = $tAutomate[$etat][$char];
  $etat = ($transition & 0xffff0000) >> 16;
  $cnvchar = ($transition & 0×0000ff00) >> 8;
  $ifct = $transition & 0×000000ff;
  switch($ifct)
  {
  case 1: atm_bufferize($cnvchar); break;
  case 2: atm_checkOpenTag($cnvchar); break;
  case 3: atm_checkCloseTag($cnvchar); break;
  }
}

Il ne récupère plus directement l’état suivant de l’automate mais une structure qu’il découpe avant de pouvoir l’utiliser.
Le switch appelle ensuite la fonction liée à l’état en lui passant le caractère converti. En PHP le switch est généralement très gourmand en temps machine, mais en assembleur, il est possible de créer une table de pointeurs de fonctions puis d’appeler très rapidement la bonne fonction. Ce qui est d’autant plus intéressant que vous pouvez fournir à votre automate des tables différentes en fonction de ce que fait votre automate.

Je ne détaille pas ici les 3 fonctions atm_bufferize, atm_checkOpenTag, atm_checkCloseTag car l’intérêt est surtout de voir comment on peut utiliser concrètement une machine à états finis et pas tellement les techniques mise en place derrière pour parser un document.

 | Tags:

Répondre

Human control : 1 + 4 =