0Ce qu'on va faire, et pourquoi ça compte
Une expression régulière décrit un ensemble de mots permis : (navire+voilier) permet
exactement deux mots. Une machine d'états fait le même travail caractère par caractère : elle part d'un
état de départ, chaque caractère lu la fait changer d'état, et à la fin du mot elle dit oui ou non.
Les deux sont équivalentes : toute expression régulière se transforme en machine d'états. C'est exactement ce que fait un compilateur quand il découpe votre code en mots-clés, parenthèses et opérateurs avant de le comprendre. Le FSM simulator fait cette transformation sous vos yeux et dessine la machine obtenue.
On construit ici trois petites machines sur le thème des bateaux, puis vous appliquez la même méthode au
if du laboratoire.
1Ouvrir et régler le simulateur
- Ouvrir ivanzuzak.info/noam/webapps/fsm_simulator. La page est en anglais et se lit de haut en bas, en trois sections numérotées.
- Dans la section ① Create automaton, rester sur l'onglet Input regex.
- Écrire l'expression dans le champ or write your own. Le champ devient vert quand l'expression est valide, rouge sinon.
- Régler la liste Select generated FSM type sur DFA. Les autres types (eNFA, NFA) dessinent des machines avec plusieurs chemins possibles pour un même caractère ; le DFA en a un seul, c'est celui qu'on programme.
- Cliquer Create automaton. Le graphe apparaît plus bas, dans la section ③ Transition graph.
2La syntaxe du simulateur
Le simulateur accepte une syntaxe réduite, plus ancienne que celle de Python. Six symboles suffisent :
| Symbole | Sens | Exemple |
|---|---|---|
a, B, 9, = | Le caractère lui-même | if : un i, puis un f |
+ | OU : l'un ou l'autre | (navire+voilier) : navire, ou voilier |
* | Zéro fois ou plus | a *b : a, des espaces ou aucun, puis b |
( ) | Regrouper | (navire+voilier)s : navires ou voiliers |
$ | Le mot vide : rien | navire(s+$) : navire ou navires |
\( \) | Une vraie parenthèse, échappée par la barre oblique inverse | if\( : i, f, puis le caractère ( |
⚠️ Le piège du + : en Python, + veut dire « une fois ou plus ».
Ici, il veut dire OU, comme le | de Python. Et le | n'existe pas dans le simulateur.
⚠️ Le piège des parenthèses : navire(s) sans barre oblique reconnaît
seulement navires, car les parenthèses regroupent. Pour reconnaître le texte navire(s)
avec ses parenthèses, il faut écrire navire\(s\).
L'aide-mémoire REGEX de la semaine 6 donne la syntaxe complète de Python, pour comparer.
3Lire le graphe
- L'état rose avec une flèche entrante est l'état de départ, numéroté 0. Pendant une simulation, le rose se déplace : il marque l'état courant.
- Le double cercle est un état acceptant : si le mot se termine là, il est reconnu.
- Chaque flèche porte les caractères qui la font emprunter, séparés par des virgules.
- Le grand état à droite, où arrivent presque toutes les flèches et qui boucle sur lui-même, est l'état puits : un caractère inattendu y envoie la machine, et elle n'en ressort jamais. C'est l'erreur de syntaxe.
💡 Les numéros des états sont choisis par le simulateur, pas par vous. Deux machines équivalentes peuvent avoir des numéros différents : comparez la forme et le nombre d'états, pas les numéros.
4Des parenthèses littérales
Premier objectif : reconnaître exactement le texte navire(s), parenthèses comprises.
La machine est une ligne droite : un état par caractère lu. À chaque état, le seul bon caractère fait avancer ; tous les
autres mènent à l'état puits. Remarquez que la parenthèse est devenue un caractère comme les autres sur les flèches
( et ).
5L'alternative
Deuxième objectif : reconnaître navire ou voilier.
Le premier caractère décide du chemin : n part en haut, v en bas. Les deux branches se
rejoignent à la fin sur le même état acceptant : le simulateur fusionne les états qui ont le même avenir.
6Combiner les deux
Troisième objectif : reconnaître navire(s) ou voilier(s). On regroupe l'alternative avec de
vraies parenthèses, puis on ajoute les parenthèses littérales.
Les deux sortes de parenthèses travaillent ensemble : ( ) regroupe (navire+voilier) pour que le
OU ne s'applique qu'aux deux mots, et \( \) devient du texte à reconnaître. La partie commune, (s),
n'est dessinée qu'une fois.
7Faire lire un mot à la machine
- Dans la section ② Simulate automaton, écrire un mot dans le champ See if this fits,
par exemple
voilier(s). - Cliquer Start, puis Read next pour lire un caractère à la fois : l'état rose avance dans le graphe. Read all lit tout d'un coup, Step backward recule d'un caractère, Reset recommence.
- À la fin, le mot est accepté si l'état rose est un double cercle.
- Les boutons Acceptable string et Unacceptable string génèrent des mots que la machine accepte ou refuse : pratique pour vérifier qu'elle ne laisse rien passer de trop.
(navire+voilier)\(s\) : navire(s), voilier(s)navire, voiliers, navire(s, bateau(s)Retour à l'énoncé du Labo Machine d'état de parsing · outil : FSM simulator (Ivan Zuzak et Vedrana Jankovic, bibliothèque noam).