Décrire une règle : les expressions régulières
Ce que ce chapitre apporte
- Écrire une règle de validation avec les trois opérations des expressions régulières : concaténation, union, étoile de Kleene.
- Construire l'automate d'une expression brique par brique, et assembler les briques.
- Lire le rôle des transitions spontanées dans un automate assemblé, et voir plusieurs états s'allumer.
- Appliquer une expression à un journal de production avec le module re de Python.
- Éviter les deux pièges de l'étoile : elle autorise zéro occurrence, et elle porte sur l'élément qui précède.
C'est ici que les automates sortent du cours. Filtrer un journal de production, extraire des codes d'erreur d'un fichier de plusieurs milliers de lignes, vérifier qu'une référence saisie a la bonne forme : toutes ces tâches s'écrivent en une ligne, avec une expression régulière. Et derrière cette ligne, il y a exactement l'objet des deux chapitres précédents, les états et les événements puis la reconnaissance d'une séquence : un automate qui lit les caractères un à un. Ce chapitre montre le passage de l'un à l'autre, brique par brique, et désamorce les deux pièges sur lesquels tout le monde trébuche.
Une règle qui tient sur une ligne
Un poste d'assemblage écrit un journal. Chaque anomalie y apparaît sous la forme ERR- suivi de quatre chiffres. Extraire ces anomalies d'un journal de dix mille lignes est un travail d'une ligne.
Deux lignes ressortent sur cinq. L'expression ERR-\d{4} se lit de gauche à droite : les quatre caractères E, R, R et -, puis quatre chiffres. Rien d'autre n'est demandé, et re.search cherche ce motif n'importe où dans la ligne.
Une expression régulière est une description d'un ensemble de séquences, pas un programme. C'est la même chose qu'un automate, écrite en une ligne au lieu d'un dessin, et le reste du chapitre établit ce lien.
Trois opérations, et rien d'autre
Tout ce qu'une expression régulière sait faire se ramène à trois opérations, appliquées à des symboles.
La concaténation met deux motifs bout à bout : EW décrit la séquence E suivie de W. L'union, notée par une barre verticale, offre un choix : E|W décrit soit E, soit W. L'étoile de Kleene répète : E* décrit zéro, une, ou autant de répétitions de E que voulu.
Le reste de la syntaxe n'est qu'un raccourci pour ces trois opérations, et il est utile de savoir ce que chaque raccourci cache :
\dremplace l'union des dix chiffres,[0-9A-F]celle des seize caractères d'un chiffre hexadécimal.E+remplace la concaténationEE*: au moins une occurrence.E?remplace l'union deEet de la séquence vide : zéro ou une occurrence.\d{4}remplace la concaténation\d\d\d\d.
Les parenthèses servent à dire sur quoi porte une opération, exactement comme en calcul. Elles ne sont pas une décoration, et la fin du chapitre montre ce qu'elles changent.
De l'expression à l'automate, brique par brique
Chaque opération correspond à une façon d'assembler des automates, et l'assemblage utilise des transitions spontanées, notées ε, qui se franchissent sans rien lire. Une brique se construit toujours de la même manière : une entrée, une sortie, et ce qu'il y a entre les deux.
La brique d'un symbole
L'automate le plus simple lit un symbole et s'arrête.
E
État actif : départ.
La brique de l'union
Pour E|W, deux briques sont posées côte à côte. Un état d'entrée mène aux deux par des transitions spontanées, et les deux sorties rejoignent une sortie commune de la même façon.
E
3 états actifs en même temps : entrée, départ E, départ W. L'automate suit tous les chemins à la fois.
Trois états sont allumés avant la première lecture : entrée, et les deux départs atteints sans rien consommer. L'automate n'a pas choisi de branche, il est dans les deux à la fois, et c'est ce que la ligne sous le dessin annonce. Le symbole lu élimine ensuite la branche qui ne le prévoit pas.
La brique de la concaténation
Pour EW, la sortie de la première brique est reliée à l'entrée de la seconde par une transition spontanée.
EW
État actif : départ.
Après le premier symbole, deux états s'allument : après E, atteint par la lecture, et attente W, atteint sans rien lire. La transition spontanée est franchie d'office, dès qu'elle est disponible.
La brique de l'étoile
L'étoile est la seule brique qui ajoute un chemin en arrière. Pour C*, une transition spontanée saute par-dessus la brique répétée, et une autre revient de sa sortie vers son entrée.
CCC
3 états actifs en même temps : entrée, sortie, corps départ. L'automate suit tous les chemins à la fois.
Les deux transitions spontanées portent chacune une moitié du sens de l'étoile. Celle qui va de entrée à sortie autorise zéro répétition : c'est elle qui fait accepter la séquence vide. Celle qui revient de corps fin à corps départ autorise les répétitions suivantes.
L'assemblage
Les briques se composent comme un jeu de construction. Soit la règle suivante, tirée d'un fichier d'identifiants d'équipements : un identifiant de vanne s'écrit V suivi d'au moins un chiffre. En expression régulière, V\d+, c'est-à-dire la concaténation de V, d'un chiffre, et de l'étoile d'un chiffre.
L'automate assemblé enchaîne la brique de V, celle d'un chiffre, puis la brique d'étoile de la partie précédente.
VCCC
État actif : départ.
L'alphabet est réduit à deux symboles, V et C pour un chiffre quelconque, pour la même raison que le numéro de lot : la règle ne distingue pas les chiffres entre eux. Après le premier chiffre, trois états sont allumés, dont fin : l'identifiant VC est déjà valide, et chaque chiffre supplémentaire ramène dans la même situation. La séquence V seule, elle, s'arrête sur après V, qui n'est pas acceptant : l'expression exige bien au moins un chiffre.
C'est là toute la construction : un automate par symbole, trois façons de les recoller, et n'importe quelle expression régulière devient un automate. Le mécanisme est purement mécanique, et c'est exactement ce qu'un moteur d'expressions régulières fait avant de lire le premier caractère du texte.
Deux pièges de l'étoile
L'étoile autorise zéro occurrence
V\d* ne veut pas dire « V suivi de chiffres », mais « V suivi de zéro chiffre ou plus ». L'identifiant V, sans le moindre chiffre, satisfait l'expression.
V
État actif : départ.
L'état atteint après le seul symbole V porte le double cercle : la séquence est acceptée. C'est la même chose du côté de Python, et le résultat surprend à la première rencontre.
La première ligne affiche ['ERR-', 'ERR-42', 'ERR-0117'] : le code d'erreur tronqué, sans aucun chiffre, est retenu comme les autres. La deuxième confirme que V seul satisfait V\d*. La troisième affiche None : V\d\d*, c'est-à-dire V\d+, exige un premier chiffre avant l'étoile.
Un filtre écrit avec * retient des séquences vides là où personne ne les attendait, et c'est la cause la plus fréquente des extractions polluées. Dès que la règle dit « au moins un », écrire +, jamais *. Et vérifier le filtre sur une ligne volontairement tronquée, pas seulement sur des lignes correctes.
L'étoile porte sur l'élément qui précède
Deuxième piège, plus discret : l'étoile ne s'applique pas à tout ce qui la précède, mais au seul élément qui la précède immédiatement. Dans V\d*, l'étoile porte sur \d. Pour répéter le groupe entier, il faut des parenthèses, et (V\d)* décrit une tout autre chose : une suite de couples, comme la liste V1V2V3 relevée en fin de ligne d'un journal.
VCVC
État actif : départ.
L'état départ est à la fois initial et acceptant : la séquence vide est acceptée, zéro couple étant un nombre de couples valide. La séquence VCVC est acceptée, et chaque couple ramène au départ. La séquence VCC, en revanche, bloque au troisième symbole : depuis départ, aucune transition ne lit un chiffre.
V12 satisfait V\d* et pas (V\d)* ; V1V2 fait l'inverse. Les deux expressions ne diffèrent que par une paire de parenthèses, et elles décrivent des ensembles de séquences qui n'ont presque rien en commun.
Extraire dans un journal de production
Le cas type est l'analyse d'un relevé d'équipement réseau, où les adresses matérielles sont à extraire. Une adresse MAC s'écrit six paires de chiffres hexadécimaux séparées par des deux-points. La règle se transcrit directement : cinq fois le groupe « deux caractères puis un deux-points », puis une dernière paire.
Deux adresses sont extraites, et la troisième ligne n'en fournit aucune : 44:11:3A ne compte que trois paires, et l'expression en exige six. Les horodatages de début de ligne ne sont pas retenus non plus, pour la même raison.
Le groupe (?:...) est un groupe de parenthèses ordinaire dont le contenu n'est pas mémorisé ; sans le ?:, re.findall renverrait le contenu du groupe au lieu de l'adresse entière. C'est un détail du module re, pas de la théorie, mais il coûte assez de temps pour mériter d'être signalé.
re.search cherche le motif quelque part dans le texte : c'est ce qu'il faut pour filtrer un journal. re.fullmatch exige que le motif décrive le texte en entier : c'est ce qu'il faut pour valider une saisie. Utiliser l'un pour l'autre est une erreur silencieuse : un contrôle de numéro de lot écrit avec re.search accepte XXAB123XX.
Exercices type
WR
3 états actifs en même temps : entrée, départ E, départ W. L'automate suit tous les chemins à la fois.
Quelle expression régulière l'automate ci-dessus décrit-il, sur l'alphabet `E`, `W` et `R` ? Écrire ensuite l'automate de la même expression sans aucune transition spontanée.
L'union est en tête et la concaténation derrière : l'expression est (E|W)R, soit un E ou un W, suivi d'un R. Les deux séquences acceptées sont ER et WR, et rien d'autre : R seul est rejeté, EW bloque au second symbole.
Les transitions spontanées viennent de la construction mécanique, et elles ne sont pas nécessaires. Ici, les deux branches font exactement la même chose après leur premier symbole, donc un seul état intermédiaire suffit.
WR
État actif : entrée.
Une même règle admet donc plusieurs automates. La déterminisation et la minimisation donnent les procédés qui les comparent et qui produisent le plus petit.
Un code de traçabilité s'écrit `LOT-` suivi de trois chiffres, puis éventuellement d'un tiret et d'une lettre de reprise, comme `LOT-042` ou `LOT-042-B`. Écrire l'expression régulière correspondante, puis le programme qui retient les lignes conformes d'un journal.
Le « éventuellement » se traduit par ?, qui porte sur un groupe entier, donc parenthésé : LOT-\d{3}(-[A-Z])?. Sans les parenthèses, LOT-\d{3}-[A-Z]? exigerait le tiret et rendrait seulement la lettre facultative, ce qui n'est pas la règle énoncée.
La validation d'une saisie demande re.fullmatch, qui refuse tout caractère en trop.
Le programme affiche vrai pour LOT-042 et LOT-042-B, faux pour les trois autres : LOT-42 n'a que deux chiffres, LOT-042- a un tiret sans lettre, et XLOT-042 porte un caractère de trop, refusé par fullmatch mais qui serait accepté par search.
Un relevé contient des mesures de la forme `T=` suivi d'un nombre entier, comme `T=21`. Un collègue écrit le motif `T=\d*` et s'étonne d'obtenir des résultats vides dans sa liste. Expliquer, puis corriger.
L'étoile autorise zéro chiffre : toute occurrence de T=, même suivie d'un espace ou d'une fin de ligne, satisfait le motif et ressort sous la forme 'T='. Une ligne tronquée par un capteur en défaut suffit à polluer la liste.
La correction tient en un caractère : T=\d+ exige au moins un chiffre.
La première liste contient quatre entrées dont 'T=', la seconde trois seulement. La même prudence vaut pour tout filtre de journal : l'éprouver sur une ligne volontairement incomplète, et pas seulement sur des lignes correctes.
Vérification
1.Que décrit l'expression V\d* ?
2.Sur quoi porte l'étoile dans V\d* ?
3.À quoi sert une transition spontanée dans un automate assemblé ?
4.Dans la brique de l'étoile, quel chemin fait accepter la séquence vide ?
5.Un contrôle de saisie doit refuser XXAB123XX. Quelle fonction employer ?
6.Combien d'adresses le motif (?:[0-9A-F]{2}:){5}[0-9A-F]{2} trouve-t-il dans la chaîne 44:11:3A ?
7.Que devient une expression régulière avant que le texte ne soit lu ?
La méthode
- Écrire la règle en français avant tout motif, en séparant ce qui est obligatoire, ce qui est facultatif et ce qui se répète.
- Traduire opération par opération : bout à bout donne une concaténation, « soit ceci soit cela » une union, « autant de fois que voulu » une étoile, « au moins un » un plus.
- Parenthéser tout groupe répété ou facultatif, car l'étoile, le plus et le point d'interrogation ne portent que sur l'élément qui les précède.
- Construire l'automate brique par brique quand le motif résiste : un automate par symbole, recollé par des transitions spontanées, puis dérouler un exemple dessus.
- Choisir la fonction selon l'usage :
re.searchpour filtrer un journal,re.fullmatchpour valider une saisie. - Éprouver le motif sur trois cas : une ligne conforme, une ligne tronquée qui doit être refusée, une ligne qui contient le motif au milieu d'autre chose.
Synthèse
- Une expression régulière décrit un ensemble de séquences avec trois opérations : concaténation, union, étoile de Kleene ; le reste de la syntaxe n'en est qu'un raccourci.
- Chaque opération a sa brique d'automate, recollée par des transitions spontanées qui se franchissent sans rien lire, d'où plusieurs états allumés en même temps.
- La brique de l'étoile porte deux chemins : le saut qui autorise zéro répétition, et le retour qui autorise les suivantes.
- Toute expression se transforme mécaniquement en automate, et c'est ce que fait un moteur d'expressions régulières avant de lire le premier caractère.
- L'étoile autorise zéro occurrence : un filtre écrit avec
*ramène des résultats vides, et « au moins un » s'écrit+. - L'étoile porte sur l'élément qui précède immédiatement :
V\d*et(V\d)*ne décrivent pas la même chose, et seule la parenthèse fait la différence. re.searchfiltre,re.fullmatchvalide : les confondre fait accepter une saisie qui contient la bonne forme au milieu de caractères parasites.
Les briques assemblées ici allument plusieurs états à la fois, sans que la règle d'exécution ait été dite. C'est l'objet du chapitre sur le non-déterminisme, qui remplace l'état courant par un ensemble d'états actifs.