* * *
Automate
* * *


 Aujourd'hui, nous allons voir les automates. Ce ne sont pas les automates que vous voyez fleurir dans les halls de supermarché en cette fin d'année, mais une manière de coder un comportement très intéressante. Les applications des automates sont énormes, mais le but premier des automates est de faire de l'analyse lexicale dans les compilateurs. Les applications secondaires sont aussi intéressantes : gestion d'interface (par exemple Falk'mag), gestion d'animation de sprite, gestion de protocole, ...

 Le point commun entre toutes ces utilisations est la présence d'un état, c'est à dire qu'il y a un comportement qui différent suivant tel ou tel contexte. Par exemple dans Falk'mag, lorsque qu'un menu est déroulé, le contexte n'est pas le même que lorsqu'il n'y a pas de menu déroulé. Ainsi il n'est pas possible de lancer un article sans menu déroulé, ... De même pour une analyse lexicale, ou a un certain moment, on s'attend a voir apparaître tels ou tels caractères, ...

 Après vous avoir persuader de l'intérêt des automates, il ne reste plus qu'a comprendre comment ça marche, puis a en implémenter un. On représente un automate par un graphe (des carrés et des flèches entre ces carrés). Ainsi chaque carré représente un état. On peut passer d'un état à un autre, si il y a une flèche entre ces deux états, et si l'étiquette de la flèche correspond au caractère (ou à n'importe quoi que vous voulez analyser) courant. Cette flèche porte le nom de transition entre deux états. Par exemple imaginons que l'on veuille construire un automate qui reconnaît toutes les chaînes abba (aucun rapport avec le groupe). L'automate est le suivant :

     +---+ a  +---+ b  +---+ b  +---+ a  +---+
  -->¦ 0 ¦--->¦ 1 ¦--->¦ 2 ¦--->¦ 3 ¦--->¦ 4 ¦--+
     +---+    +---+    +---+    +---+    +---+
   ^                                           ^
   +-- flèche qui indique                      +-- flèche qui indique
       l'état initial de                           l'état d'acceptation
       l'automate                                  de l'automate
 L'automate débute avec l'état 0 (état initial), et le caractère courant est le premier de la chaîne. Si le caractère courant est a, alors on passe dans l'état 1, sinon la chaîne que l'on cherche à reconnaître n'est pas de la forme abba. Le caractère courant passe au caractère suivant, et on recommence la même opération que pour l'état 0. Et ainsi de suite. Lorsque l'on arrive à l'état 4, nous avons reconnus la chaîne abba. Si la chaîne se termine, puisque que l'on se trouve dans un état d'acceptation, alors la chaîne analysée est conforme à ce que nous cherchions. Par contre si elle ne se termine pas, elle n'est pas de la forme abba, et donc n'est pas une chaîne valide. Certain vont dire, que pour reconnaître la chaîne abba, un automate n'est pas nécessaire. Mais par contre pour reconnaître les chaines de la forme ab*a, c'est à dire les chaînes commençant par un a, ayant aucun ou plusieurs b, et se terminant par un a, là, c'est déjà plus compliqué par une méthode traditionnelle. Voici l'automate qui permet de reconnaître ce type de chaîne :

     +---+ a  +-----+ a  +---+ 
  -->¦ 0 ¦--->¦  1  ¦--->¦ 2 ¦--+
     +---+    +-----+    +---+
               ¦   ^
               ¦ b ¦
               +---+

 Encore plus simple que le premier! Le fonctionnement reste le même, mais la boucle sur l'état 1 permet de reconnaître aucun ou plusieurs b succéssifs. Ainsi une boucle dans un automate permet de créer un infini, et ainsi de reconnaître toutes les chaînes de caractères, il n'y a aucune limite! Pour vous en persuadez, faites un essai : reconnaître la chaîne abbbba.

 Plusieurs instants plus tard, vous continuez à lire (pas trop dur de tracer un automate?). Imaginez que vous vouliez reconnaître les chaînes abbaab*a. Et bien c'est très simple. Dans l'état 4 du 1er automate, vous avez déjà reconnu la chaîne abba, par contre dans l'état 0 du 2nd automate, il vous reste à reconnaître ab*a. Et bien pour construire notre automate reconnaissant les chaînes abbaab*a, il suffit de construire un automate né de la concaténation des deux premiers automates :

     +---+ a  +---+ b  +---+ b  +---+ a  +---+ a  +-----+ a  +---+
  -->¦ 0 ¦--->¦ 1 ¦--->¦ 2 ¦--->¦ 3 ¦--->¦ 4 ¦--->¦  5  ¦--->¦ 6 ¦--+
     +---+    +---+    +---+    +---+    +---+    +-----+    +---+
                                                   ¦   ^
                                                   ¦ b ¦
                                                   +---+

 Pour faire un automate reconnaissant les chaînes abba ou ab*a, il suffit de faire une "union" d'automate, c'est à dire que les deux états initiaux sont confondus. Ainsi le nouvel automate est :

     +---+ a  +---+ b  +---+ b  +---+ a  +---+
  -->¦ 0 ¦--->¦ 1 ¦--->¦ 2 ¦--->¦ 3 ¦--->¦ 4 ¦--+
     +---+    +---+    +---+    +---+    +---+
       +
       ¦   a  +-----+ a  +---+ 
       ------>¦  5  ¦--->¦ 6 ¦--+
              +-----+    +---+
               ¦   ^
               ¦ b ¦
               +---+

 Première remarque pour cet automate, il a deux états finals. Ca ne pose pas de problème en théorie, mais plutôt en pratique. Mais il faut savoir qu'il est souvent possible de se ramener à un état final (ici il suffit de modifier la flèche de l'état 5 à 6, en une flèche de l'état 5 à 4, et l'état 6 n'existe plus). Seconde remarque, et non des moindres, cet automate est non déterministe. C'est à dire que lorsque l'on reconnaît le premier caractère (on est dans l'état 0), si il s'agit d'un a, il y a deux possibilités (l'état 1 ou l'état 5). Le problème est qu'il ne faut choisir aucun chemin a priori, et donc suivre les deux en même temps! Par exemple si l'on veut reconnaître la chaîne abbba, on va s'apercevoir que ce n'est pas une chaîne du type abba lorsqu'on analyse la 4ième lettre, donc seul le chemin utilisant l'état 5 est finalement valide. Il existe des algorithmes pour rendre déterministe un automate à partir d'un automate non déterministe, mais ce n'est pas le but de l'article.

 Il est possible d'associer une action à chaque transition d'un état à un autre. Par exemple si l'on veut compter le nombre de b dans une chaîne de type ab*a, il suffit que lors de chaque transition de 1 vers 1 (lorsque l'on reconnaît un b), d'incrémenter une variable. En général, chaque action utilise le caractère reconnu pour y faire un traitement. Dans l'exemple de l'article, les chiffres reconnus sont utilisés pour construire le nombre à reconnaître.

 Après la théorie des automates (version simplifiée), passons au codage. Il existe deux méthodes différentes de coder un automate : une méthode dure, et une méthode souple. La méthode dure est très simple, il suffit de créer une fonction pour chaque état. Chaque fonction se charge de lire le caractère suivant, et suivant le caractère, il y a exécution de la bonne action et un appel de la fonction représentant l'état suivant. Cette méthode à l'avantage d'être assez rapide à l'exécution, mais le temps de codage est un peu plus long, la souplesse n'est pas là (il faut modifier le code pour modifier l'automate), et il y des risques de débordemment de pile (suite d'appel + allocation de variable locale).

 La seconde méthode est un peu plus complexe à comprendre. Un automate se représente sous la forme d'un graphe. L'idée est de coder ce graphe sous la forme d'un tableau bidimensionnel. Les lignes représentent les états, et les colonnes représentent le caractère courant. Dans chaque case du tableau, on stocke l'état suivant. Ainsi pour l'automate suivant, le tableau de transition est le suivant :

     +---+ a  +-----+ a  +---+ 
  -->¦ 0 ¦--->¦  1  ¦--->¦ 2 ¦--+
     +---+    +-----+    +---+
               ¦   ^
               ¦ b ¦
               +---+



caractères ¦ a      ¦ b      ¦ autre  ¦ fin    ¦
-----------+--------+--------+--------+--------+
état 0     ¦   1    ¦ erreur ¦ erreur ¦ erreur ¦
état 1     ¦   2    ¦   1    ¦ erreur ¦ erreur ¦
état 2     ¦ erreur ¦ erreur ¦ erreur ¦ OK     ¦

 On voit qu'on a rajouté deux "caractères" spéciaux : autre et fin. Le caractère autre représente tous les autres caractères, c'est à dire c, d, ... Le caractère fin représente la fin de la chaîne à reconnaître. Ce caractère permet de terminer l'analyse. Les états suplémentaires erreur et OK, représente respectivement une erreur dans l'analyse de la chaîne, et une chaîne correctement reconnue.

 L'utilisation de cette table est très simple. Par exemple, si l'on veut analyser la chaîne aba, le déroulement de l'analyse est le suivant. On débute avec l'état initial 0. Le premier caractère reconnu est un a, donc dans la colonne a de la ligne état 0, on trouve l'état suivant : l'état 1. Pour le deuxième caractère, qui est b, on cherche l'état suivant sur la ligne état 1, car on se trouve dans l'état 1. Et ansi de suite, jusqu'à arriver à l'état 2, et d'être en fin de chaîne. De même au lieu de coder l'état suivant, cette représentation peu servir à coder l'action à effectuer sur la transition.


 L'algorithme d'un automate est donc le suivant :

  état_courant=état_initial
  tant que pas en état final faire
     lire le caractère courant c
     faire l'action[état_courant][c]
     état_courant=transition[état_courant][c]
  fait

 C'est ce que réalise la boucle while de la fonction main du programme d'exemple. A propos d'exemple, de quoi s'agit-il ? Le but du jeu est de reconnaître un nombre en virgule flottante, avec comme virgule, non pas un point, mais une virgule. La grammaire des nombres en virgule flottante est :

     [0123456789]*[,[0123456789]*]0/1

 C'est à dire un nombre composé de 0 ou plusieurs chiffres ([0123456789]*), suivit d'une virgule (,) et d'un nombre composé de 0 ou plusieurs chiffres. Cette dernière partie est optionnelle (0/1). Par exemple, les nombres suivants sont valides :
  123,456789
     ,123456
     ,              vaut 0
     132,           vaut 132

 Avec un programme classique, la gestion des cas particuliers est un peu galère, mais avec un automate, c'est très simple! N'ayant pas le courage de dessiner le graphe de transition, je vous donne plutôt la table de transition, ainsi que la table des actions :

état initial : 0
état d'acceptation : 3
état d'erreur : 4  (on sort de cet état d'erreur en fin de chaîne,  et  donc 
                   il n'y a qu'un état "d'acceptation")

caractères ¦ 0 ¦ 1 ¦ 2 ¦ 3 ¦ 4 ¦ 5 ¦ 6 ¦ 7 ¦ 8 ¦ 9 ¦ , ¦ \n ¦ autre ¦
-----------+---+---+---+---+---+---+---+---+---+---+---+----+-------+
état 0     ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 2 ¦ 3  ¦ 4     ¦
état 1     ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 2 ¦ 3  ¦ 4     ¦
état 2     ¦ 2 ¦ 2 ¦ 2 ¦ 2 ¦ 2 ¦ 2 ¦ 2 ¦ 2 ¦ 2 ¦ 2 ¦ 4 ¦ 3  ¦ 4     ¦
état 3     ¦ 3 ¦ 3 ¦ 3 ¦ 3 ¦ 3 ¦ 3 ¦ 3 ¦ 3 ¦ 3 ¦ 3 ¦ 3 ¦ 3  ¦ 3     ¦
état 4     ¦ 4 ¦ 4 ¦ 4 ¦ 4 ¦ 4 ¦ 4 ¦ 4 ¦ 4 ¦ 4 ¦ 4 ¦ 4 ¦ 3  ¦ 4     ¦              /* état 4 : erreur */

Les états ont la signification suivantes :

état 0
état initial, sur chaque transitions il faudra procéder à une initialisation. Il y a initialisation d'un accumulateur qui contient le nombre lu sous forme entière. Cet accumulateur sera divisé par une puissance de 10 pour obtenir le nombre en virgule flottante correspondant. Cette puissance de 10 est initialisée à 1 (10^0)
état 1
état de lecture de la partie entière. Chaque caractère qui est lu, est stocké dans l'accumulateur. Dès qu'il y a apparition de la virgule, on passe à l'état 2 qui se charge de la lecture de la partie décimale
état 2
état de lecture de la partie décimale. A chaque chiffre lu, il est stocké dans l'accumulateur, et il y a incrémentation du nombre de puissance de 10 par laquel il faudra diviser l'accumulateur pour obtenir le nombre lu
état 3
état qui d'acceptation, c'est l'état final de l'automate. Il y a transition sur cette état lorsque l'on rencontre le caractère '\n' (retour chariot). Certaine transition sur cette état affiche soit le nombre lu (si il n'y a pas eu d'erreur), soit un message d'erreur
état 4
état d'erreur. On arrive dans cet état lorsque des caractères non conforme on été utilisé, ou bien qu'un nombre ne correspondant pas à la grammaire ai été rentré (deux virgules par exemple)

 Les actions liées aux transitions sont les suivantes :


caractères ¦ 0  ¦ 1  ¦ 2  ¦ 3  ¦ 4  ¦ 5  ¦ 6  ¦ 7  ¦ 8  ¦ 9  ¦ ,  ¦ \n ¦ aut
-----------+----+----+----+----+----+----+----+----+----+----+----+----+----
état 0     ¦ I  ¦ I  ¦ I  ¦ I  ¦ I  ¦ I  ¦ I  ¦ I  ¦ I  ¦ I  ¦ IV ¦ R  ¦ E
état 1     ¦ C  ¦ C  ¦ C  ¦ C  ¦ C  ¦ C  ¦ C  ¦ C  ¦ C  ¦ C  ¦ V  ¦ F  ¦ E
état 2     ¦ CV ¦ CV ¦ CV ¦ CV ¦ CV ¦ CV ¦ CV ¦ CV ¦ CV ¦ CV ¦ E  ¦ F  ¦ E
état 3     ¦ R  ¦ R  ¦ R  ¦ R  ¦ R  ¦ R  ¦ R  ¦ R  ¦ R  ¦ R  ¦ R  ¦ R  ¦ R
état 4     ¦ R  ¦ R  ¦ R  ¦ R  ¦ R  ¦ R  ¦ R  ¦ R  ¦ R  ¦ R  ¦ R  ¦ R  ¦ R
 Les actions ont la signification suivante :

I INIT : initialisation de l'accumulateur au chiffre lu, et du nombre de décalage à 0 (10^0 = 1)
IV INIT_VIRG : initialisation de l'accumulateur à 0, et du nombre de décalage à 0
R RIEN : ne fait rien
E ERREUR : affiche un message d'erreur
C CH : multiplie l'accumulateur par 10, et lui ajoute le nombre lu.
V VIRG : passage dans la partie décimale : rien à faire
F FIN_CH : calcul le nombre rentré, et l'affiche. On va dans l'état final de l'automate
CV CH_VIRG : multiplie l'accumulateur par 10, lui ajoute le chiffre lu, et ajoute 1 au nombre de décalage (multiplication de la valeur decalage par 10)

 Ces actions sont regroupés dans la fonction automate. L'aiguillage se réalise avec l'instruction switch. De plus les variables nécessaire à l'automate sont locales à la fonction automate et statique.

 Voyons un peu le format des données manipulées. Le type t_automate regroupe toutes les données nécessaires au fonctionnement d'un automate. On retrouve donc l'état initial (champ etat_initial), l'état final (champ etat_final), l'état courant (champ etat_courant), et deux matrices d'entier transition et action. Ces matrices sont du type t_matrice composé d'un champ largeur, d'un champ hauteur, et d'un pointeur sur une suite d'entier. L'accès à un élément d'un matrice se réalise avec la fonction matrice. Cette fonction vérifie qu'il n'y a pas d'accès illégal à un élément de la matrice. Retour sur l'automate, la fonction init_automate initialise l'automate, la fonction fin_automate retourne vrai lorsque l'automate est dans un état de fin, action retourne le numéro de l'action a exécuté en fonction de l'état courant et du caractère lu, et transition retourne le prochain état en fonction du caractère lu et de l'état de l'automate. La fonction automate sert à faire un pas dans l'automate, ou si vous préférez, consomme un caractère. On y retrouve les actions qui sont réalisé suivant le retour de la fonction action. Et aussi transition, qui effectue une transition de l'automate. Traduit est une fonction qui sert d'adaptation entre les caractères ascii et les caractères de l'automate. Ainsi le caractère '1' de l'automate à pour code 1 (très pratique pour modifier l'automate), Le caractère '\n' à pour code 11 ou FIN_CHAINE... Ceci permet d'avoir des matrices concises.

 Le programme principal commence par définir les deux matrices de transition et d'action, puis l'automate. Il initialise l'automate, et affiche un petit message d'invitation. La boucle principal commence par regarder si l'automate n'est pas dans un état final, sinon il lit un caractère du clavier, traduit ce caractère, et lance la fonction automate avec la traduction du caractère.

 J'espère que vous aurez compris comment fonctionne un automate, et comment les utiliser. Cet article touche à sa fin, alors bon code !





Golio Junior