
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