La regex est le marteau du traitement de texte

Les regexes constituent l'outil de base pour traiter les données textuelles. Et l'occasion d'écrire des programmes que vous ne pourrez pas relire vous-même, bande de masochistes.

Ce billet présente les regexes et quelques langues formelles qu'elles peuvent définir. Au passage, nous verrons les problèmes qui surgissent pour des tâches a priori simples et que rencontrent fréquemment les data scientists et, plus généralement, les développeurs.

Remarque préliminaire : comme écrit dans le billet sur les langages et les langues, l'anglais n'a pas de mot pour distinguer « langue » de « langage ». Afin de ne pas appauvrir le français, nous parlerons donc de langue formelle plutôt que de langage formel, de langue de programmation plutôt que de langage de programmation. Tant pis si ça vous fait bizarre.

Exprimer un motif

Utiliser une langue formelle c'est se retreindre aux mots qu'elle autorise. C'est très contraignant. Mais, dans certains cas, c'est exactement ce que l'on veut : vérifier qu'un mot, ou une suite de mots, est d'une certaine forme ou suit un certain motif.

Les expressions régulières classiques proposent une façon compacte de décrire les mots d'une langue formelle sous forme de motif. Elles encodent des opérations dites régulières ou rationnelles : concaténation, union et répétitions de mots.

Les langues formelles dont les mots sont donnés par une expression régulière classique sont qualifiées de régulières ou rationnelles. Elles sont situées en bas de la hiérarchie de Chomsky-Schützenberger, juste au-dessus des langues finies.

Étendre les expressions régulières classiques

En pratique, nous n'utilisons pas d'expressions régulières classiques mais des extensions de celles-ci obtenues en autorisant des opérations non régulières, comme la référence arrière. Ce sont ces expressions régulières étendues que nous appelons ici regexes.

Une regex est une succession de symboles, comme des lettres et des chiffres, qui décrit un ensemble de mots. Certains des symboles utilisés revêtent un sens spécial : signes de ponctuations, parenthèses, crochets, étoile *, alternative |, chapeau ^, etc.

Les symboles spéciaux et leurs sens varient légèrement suivant les définitions, mais globalement on retrouve les mêmes idées et des expressions similaires d'une définition à l'autre. Nous utiliserons dans ce billet la convention du module re de Python afin de décrire quelques langues régulières et illustrer le fonctionnement des regexes.

Parler comme un robot, écrire comme un pied

Les regexes font partie des outils de base du technicien des données, du développeur au data scientist guru. Mais il faut savoir ne pas s'acharner avec.

Some people, when confronted with a problem, think “I know, I'll use regular expressions”. Now they have two problems. Jamie Zawinski

En effet, le réel est toujours plus complexe qu'on ne le croît. Il échappe à la bureaucratie. Pour des tâches simples, les regexes marchent bien. Quand les tâches se complexifient, par exemple quand la langue à décrire grimpe dans la hiérarchie de Chomsky-Schützenberger, les regexes ne sont plus le bon outil pour exprimer cette complexité. À un moment, la regex devient franchement immonde, donc difficile à comprendre et à corriger.

Défaut structurel

Pourquoi ? Parce que, malgré leurs opérations supplémentaires qui leur permettent de décrire des langues non régulières, les regexes restent conçues et adaptées pour des langues régulières. C'est à la fois leur force et leur faiblesse.

Leur(s) place(s) précise(s) dans la hiérarchie de Chomsky-Schützenberger n'est pas claire et dépend de l'implantation choisie. Elles peuvent reconnaître des langues plus riches que les langues régulières. Par exemple, les regexes de Perl peuvent reconnaître les langages bien parenthésés via l'opérateur de sous-motif récursif, impensable avec les expressions régulières classiques qui n'ont pas de mémoire et se contentent de réunir, de concaténer et de répéter.

Toutefois, leur manque de lisibilité demeure. Malgré les commentaires via l'option re.VERBOSE.

Les regexes engendrent donc facilement de la dette technique. Le code est figé, on l'observe religieusement sans le comprendre, personne n'ose y toucher, le temps passe. Les gens commencent à râler, le chef de projet déprime et les développeurs s'insultent jusqu'à trouver à qui refiler le bébé. Ça retombe habituellement sur un junior qui burn-out en salopant encore plus le code.

Il faut alors adopter une autre approche : se débarrasser du bébé, mais garder l'eau du bain, soyons écolos. Nous en parlerons dans un autre billet.

Langues unaires, binaires et ADN

Les langues unaire et binaire, dont nous avons déjà parlé ici sont régulières.

Un mot de la langue unaire, comme a, aa ou aaaaaaaaa est modélisé par l'expression régulière classique a*. L'étoile * signifie que la lettre a est absente ou bien répétée autant de fois que souhaitée.

Un mot de la langue binaire, comme a, b, ab, ba, aab, baba ou aaaabbbaab est modélisé par l'expression régulière classique [ab]*, les crochets [ et ] regroupant plusieurs caractères possibles.

L'ADN est constitué de mots dont l'alphabet contient quatre lettres : A, C, G et T. Une molécule d'ADN est ainsi modélisée par l'expression régulière classique [ACGT]+, le symbole + indiquant au moins une répétition de la lettre précédente, au contraire de l'étoile * où cette dernière peut être absente.

Langues animales

Pour continuer de présenter les regexes, modélisons quelques onomatopées animales sous formes des langues formelles.

Le coq coquerique

Quand il voit le soleil :

Chaque lettre o est répétée au moins une fois, de même pour le point d'exclamation final, ce qui donne l'expression régulière classique Co+co+rico+ !+.

Le chat miaule

Quand il voit une porte :

Le préfixe Miaou est toujours présent, suivi ou pas de répétitions du mot miaou, avec en suffixe une ponctuation : point d'interrogation ou point d'exclamation éventuellement précédé d'un point d'interrogation. D'où la regex

[Mm]iaou(miaou)* (\?|(\?)?!).

Les parenthèses forment des groupes. La barre | représente ici une alternative. Le point d'interrogation échappé \? correspond au caractère et pas au symbole ? qui représente, lui, l'opérateur optionnel.

Le chien aboie

Quand il voit, ou pas :

Un aboiement est formé d'un mot de base comme Wouaf suivi d'une ponctuation, éventuellement répété avec une ponctuation identique ou différente. La regex commence à être velue :

((W(ou)?|Ou)a[fh])(.{3}| ?| !{1,3})( \1)*.

Le point d'interrogation ? marque le caractère optionnel. L'opérateur \1 correspond au premier groupe capturé (W(ou)?|Ou)a[fh], qui sera éventuellement répété. L'opérateur {m} indique que ce qui précède sera répété m fois et l'opérateur {m,n} que ce qui précède sera répété entre m et n fois..

Le Shadok gabuzomeuse

Quand il pompe :

Une phrase de la langue gabuzomeuse, comme décrit précédemment est formé d'au plus quatre mots séparés par une espace, chaque mot étant formé d'au plus quatre lettres prises dans l'alphabet à quatre lettres ᘐ, Ꜿ, ω et ρ. La regex correspondante :

[ᘐꜾωρ]{1,4}( [ᘐꜾωρ]{1,4}){0,3}.

Cas pratique : détecter les codes des départements français

Je te vois sourire, lapin.
C'est un cas trop simple ?
Bouge pas, je t'explique.

La langue formelle des codes des départements français sert, par exemple, à s'assurer que le code rentré par un utilisateur dans un formulaire administratif est valide. C'est une tâche que tout dev se retrouve à faire (au moins) une fois dans sa vie, car les données ne sont jamais aussi propres qu'elles le prétendent.

C'est une langue formelle finie : nous pouvons dresser une liste finie de tous les mots qui la composent. Pour vérifier qu'un code est valide, il suffit alors de déterminer s'il appartient à cette liste. C'est bourrin mais efficace, car il y a peu de départements.

Se compliquer la vie

Plutôt que de lister tous les codes des départements français un par un, essayons de les décrire à l'aide d'une regex.

Un département français en métropole a un code formé de deux chiffres entre 01 (Ain) et 95 (Val d'Oise). Donc 96 mots pour cette langue, correspondants aux 96 départements métropolitains, rangés mollement dans l'ordre alphabétique : la Côte-d'Or précède les Côtes-d'Armor (anciennement Côtes-du-Nord), le préfixe « Haute(s)-» se comporte bizarrement, le Territoire de Belfort s'ajoute après l'Yonne et les cinq nouveaux départements obtenus par redécoupage de la Seine et de la défunte Seine-et-Oise redémarrent un ordre alphabétique.

En première approche, la langue formelle dont les mots sont les codes départementaux est décrite par l'expression régulière classique [0-9][0-9], où [0-9] capture tous les chiffres entre 0 et 9.

Suffit-il de compter jusqu'à 99 ?

Question rhétorique.

D'une part, la Corse et ses 2A et 2B ne rentrent pas dans les clous. Vous avez d'ailleurs la garantie de planter votre programme la première fois lorsque vous affirmez qu'un code départemental est un entier.

D'autre part, l'expression capture des codes qui ne sont pas valides : les codes départementaux commencent à 01 et terminent à 96. Et, au passage, il n'y a pas de 20 à cause de la Corse.

Amendons l'expression : un mot de la langue des codes départementaux s'écrit xy avec x un chiffre entre 0 et 9 et :

La regex correspondante est plus longue, mais supportable :

[13-8][0-9]|0[1-9]|2[AB1-9]|9[0-6].

Pensons aux ultramarins

Fiers de ce premier succès, nous ajoutons les cinq départements français d'outre-mer :

et, tant qu'à faire, les autres collectivités d'outre-mer :

En effet, il suffit d'ajouter aux mots précédents de la forme xy des mots de la forme 9yz avec y et z deux chiffres contraints :

[13-8][0-9]|0[1-9]|2[AB1-9]| 9([0-6]|7[1-8]|8[46-9]).

N'oublions pas les collectivités territoriales

Emportés par notre élan, nous enrichissons la langue formelle en incluant les collectivités territoriales à statut particulier, une finasserie administrative que je découvre en même temps que vous, comme par exemple la collectivité de Corse 20R (mais pourquoi pas 2R ?). Pour aboutir à l'ajout d'expressions du type xyz avec y et z des lettres (afin de capturer la collectivité européenne d’Alsace) ou 97zw avec z un chiffre et w une lettre (pour la collectivité territoriale unique de Martinique, de Guyane et le département de Mayotte). C'est-à-dire :

[13-8][0-9]|0[1-9]|2([AB1-9]|0R)|69M|GAE|75C| 9([0-6]|7([14578]|[236]R?)|8[46-9]).

L'effort peut alors se prolonger à Monaco et à la principauté d'Andorre ...

Pour augmenter un peu la tolérance et faciliter le remplissage d'un formulaire administratif, il suffit d'inclure des mots proches de mots déjà existant. Par exemple, si le code renseigné possède un seul chiffre, alors en préfixant avec un 0 on obtient un code valide. De même, 2a, 2b, 20A et 20B peuvent être considérés comme acceptables.

Ça n'était pas si facile

Bref, la langue formelle des codes départementaux possède une structure, historiquement très simple à décrire, qui s'est dégradée au cours du temps - avec un vieux fichier, on a besoin de tenir compte de la date pour amender ces codes. Vu la regex, mieux vaut passer par une liste où tous les codes sont relevés un par un.

À la recherche du mot perdu

Admettons qu'on aimerait savoir si un texte cite le nom de l'inventeur officiel des expressions régulières, Stephen Kleene.

Contrôle + F

Il suffit pour cela de chercher dans le texte la présence de mots qui identifient explicitement ce dernier. Nous allons ainsi définir à l'aide de regex une langue formelle finie, formée de quelques mots, mais avec une combinatoire plus compliquée que l'unaire ou le binaire.

Les regexes traitent l'espace comme un caractère normal, donc la chaîne de caractères Stephen Kleene est considérée comme un seul mot. En première approche, la langue des mots qui désigne Stephen Kleene est donc restreint à cet unique mot.

Parfois, la citation est entièrement en majuscules ou, au contraire, en minuscules. Il suffit alors d'ajouter les deux mots stephen kleene et STEPHEN KLEENE. Les trois mots qui définissent maintenant notre langue peuvent être désignées par une seule regex :

Stephen Kleene|stephen kleene|STEPHEN KLEENE.

En plus compact :

[Ss](tephen|TEPHEN) [Kk](leene|LEENE).

Par contre, des mots qui n'étaient pas prévus initialement se sont insinués subrepticement, comme sTEPHEN kLEENE. Tant pis.

Un détour par les noms

In 2010, Patrick McKenzie wrote the now-famous blog “Falsehoods Programmers Believe About Names”, in which he listed 40 things that were not universally true about names. Patrick McKenzie, cited here

On se limite au second prénom ici, situation classique chez les nord-américains. Stephen Kleene avait un second prénom, Cole. Dans les citations, ce deuxième prénom est parfois présent, parfois abrégé. De plus, le premier prénom peut aussi être abrégé ou absent et, s'il est absent, alors le second prénom l'est également. La regex est modifiée en

(([Ss](.|tephen|TEPHEN) (C(.|ole|OLE) )?)?[Kk](leene|LEENE)

afin de capturer, par exemple, Stephen C. Kleene.

Complexifions un peu : si le premier prénom est abrégé, alors le second ne peut pas ne pas l'être :

([Ss]((. (C. )?)|((tephen|TEPHEN) (C(.|ole|OLE) )?)))?[Kk](leene|LEENE).

Avec cette regex, l'algorithme va considérer que Stephen Kleene est cité si le texte contient le mot kleenex, ce qui n'a rien à voir. On va donc interdire tout caractère final qui n'est pas un signe de ponctuation ou d'espace, grâce au chapeau ^ :

([Ss]((. (C. )?)|((tephen|TEPHEN) (C(.|ole|OLE) )?)))?[Kk](leene|LEENE)[^ .!?;\r\n\t].

Ce faisant, on a généralisé la notion de mot.

Et nous pourrions finasser en interdisant que le prénom soit en majuscules si le nom ne l'est pas, etc.

Remarque : il y a sûrement des regexes plus intelligentes pour repérer les citations de Stephen Kleene, mais je doute qu'elles améliorent vraiment la lisibilité. D'autre part, trouver la plus petite expression régulière classique qui engendre une langue finie est un problème compliqué.

Les dates sont mal écrites

Autre tâche fréquente, voire récurrente, en traitement de données : analyser les dates.

Une date peut s'écrire de nombreuses façons. Par exemple, nous sommes aujourd'hui le mardi 2 avril, le 2 avril 2024 précisément, ce qui s'affichera comme 02/04/2024 en haut à droite de ce billet, 04/02/2024 pour la version anglaise si le site est bien conçu.

Contrairement au cas des codes départementaux, il n'est pas question de lister les dates, même si l'ensemble est probablement fini (pas sûr qu'on utilisera encore le calendrier terrestre dans dix mille ans).

On peut tenter d'écrire une expression qui représenterait les dates valides, mais on sent bien qu'elle va être dure à décrire si on veut tenir compte de toutes les possibilités raisonnables.

Comme première ébauche : le format ISO 8601 adopte le format YYYY-MM-DD avec :

D'où l'expression régulière classique :

[0-9]{4}-(0[1-9]|1[012])-(0[1-9]|[12][0-9]|3[01]).

Alors, bien sûr, il faut tenir compte du nombre de jours dans le mois, qui elle-même dépend de l'année (bissextile ou non) et du siècle (1800 et 1900 n'étaient pas bissextiles mais 2000 l'était et 2400 le sera). Sinon, on risque de reproduire le bug de l'an 2000. Nous épargnerons au lecteur l'expression finale. Elle est pénible.

De plus, les dates ne sont pas toujours au format YYYY-MM-DD, mais par exemple suivre les formats DD/MM/YYYY ou DD/MM/YY. Les jours sont parfois écrits en toutes lettres (lundi, mardi, etc.) ou abrégés (Lun). Pareil pour les mois, voire les années pour les actes notariaux. L'année peut manquer. Le format peut soudainement basculer en anglais MM/DD/YYYY, sans prévenir.

Bref, les regexes ne sont pas du tout adaptées en général pour les dates.

Les adresses courriel sont une abomination

La validation d'une adresse courriel sur un formulaire web est parfois encore effectuée via une regex comme celle-ci :

([a-zA-Z0-9._%-]+@[a-zA-Z0-9.-]+.[a-zA-Z]{2,}).

Autrement dit :

Cependant, cette regex conduit à rejeter des adresses valides. Par exemple, cette adresse est valide : "Cette.adresse@est~valide!"@uibakery.foo.bar.baz.

Voici une regex qui fonctionne :

(?:[a-z0-9!#$%&'*+/=?^_`{|}~-]+(?:\\.[a-z0-9!#$%&'*+/=?^_`{|}~-]+)*|\"(?:[\\x01-\\x08\\x0b\\x0c\\x0e-\\x1f\\x21\\x23-\\x5b\\x5d-\\x7f]|\\\\[\\x01-\\x09\\x0b\\x0c\\x0e-\\x7f])*\")@(?:(?:[a-z0-9](?:[a-z0-9-]*[a-z0-9])?\\.)+[a-z0-9](?:[a-z0-9-]*[a-z0-9])?|\\[(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?|[a-z0-9-]*[a-z0-9]:(?:[\\x01-\\x08\\x0b\\x0c\\x0e-\\x1f\\x21-\\x5a\\x53-\\x7f]|\\\\[\\x01-\\x09\\x0b\\x0c\\x0e-\\x7f])+)\\])

J'avoue ne pas avoir vérifié moi-même. Même si vous la commentez abondamment, elle reste aride.

Il faut savoir retirer ses doigts des regexes

Moralité : ne tentez pas les regexes lorsque la tâche est trop complexe pour elles, ce qui arrive dès que la donnée suit une structure non triviale. Ça ne vaut pas le coup pour les adresses courriel, et encore moins pour parser du HTML. Il y a d'autres méthodes pour cela.

Vous vous méfierez des codes postaux, maintenant.
Et des noms.
Et des emails.
Et de vous-même quand vous déclamerez naïvement : « Boarf ! Une petite regex et c'est plié ! ».


Antoine