Expression régulière

Dans les années 1940, Warren McCulloch et Walter Pitts ont décrit le système nerveux en modélisant les neurones par des automates simples. En 1956, le logicien Stephen Cole Kleene[3] - [note 2] a ensuite décrit ces modèles en termes d’ensembles réguliers et d'automates. Il est considéré comme l'inventeur des expressions régulières. En 1959, Michael O. Rabin et Dana Scott proposent le premier traitement mathématique et rigoureux de ces concepts[4], ce qui leur vaudra le prix Turing en 1976.

Dans ce contexte, les expressions régulières correspondent aux grammaires de type 3 (voir grammaire formelle) de la hiérarchie de Chomsky ; elles peuvent donc être utilisées pour décrire la morphologie d’une langue.

Ken Thompson a mis en œuvre la notation de Kleene dans l’éditeur qed, puis l’éditeur ed sous Unix, et finalement dans grep. Depuis lors, les expressions régulières ont été largement utilisées dans les utilitaires tels que lex ainsi que dans les langages de programmation nés sous Unix, tels que expr, awk, Perl, Tcl, Python, etc.

En sortant du cadre théorique, les expressions régulières ont acquis des fonctionnalités permettant de décrire des langages non rationnels. Un glissement sémantique s'est ainsi produit : la notion d'expression régulière n'a pas le même sens dans le contexte de l'informatique appliquée et dans la théorie des langages formels.

Initialement créées pour décrire des langages formels, les expressions régulières sont utilisées dans l’analyse et la manipulation des langages informatiques ; compilateurs et interprètes sont ainsi basés sur celles-ci.

Utilisée à la manière des outils de recherche de texte dans un document, une expression régulière décrit des chaînes de caractères ayant des propriétés communes, dans le but de les trouver dans un bloc de texte pour leur appliquer un traitement automatisé, comme un ajout, leur remplacement, leur modification ou leur suppression.

Beaucoup d'éditeurs de texte et la plupart des environnements de développement intégrés permettent de mettre en œuvre les expressions régulières. Un grand nombre d’utilitaires Unix savent les utiliser nativement. Les plus connus sont GNU grep ou GNU sed qui, à la manière des éditeurs de texte, utilisent ces expressions pour parcourir de façon automatique un document à la recherche de morceaux de texte compatibles avec le motif de recherche, et éventuellement effectuer un ajout, une substitution ou une suppression.

Les interfaces en ligne de commande (ou shells) utilisent un système apparenté mais distinct et moins expressif appelé glob (en) ou globbing.

Les expressions régulières sont fréquemment employées dans les activités d'administration système, de développement logiciel et de traitement automatique du langage naturel. Elles ont vu un nouveau champ d’application avec le développement d’Internet, et la diffusion de code malveillant ou de messages pourriels. Des filtres et des robots utilisant ces expressions sont utilisés pour détecter les éléments potentiellement nuisibles.

En théorie des langages formels, une expression régulière est une expression représentant un langage rationnel. Dans ce contexte, les expressions régulières ont un pouvoir expressif plus limité : cette notion a un sens plus large en informatique appliquée qu'en théorie des langages formels.

Une expression régulière est une suite de caractères typographiques (qu’on appelle plus simplement « motif » – « pattern » en anglais) décrivant un ensemble de chaînes de caractères. Par exemple l’ensemble de mots « ex-équo, ex-equo, ex-aequo et ex-æquo » peut être condensé en un seul motif « ex-(a?e|æ|é)quo ». Les mécanismes de base pour former de telles expressions sont basés sur des caractères spéciaux de substitution, de groupement et de quantification.

Une barre verticale sépare le plus souvent deux expressions alternatives : « equo|aequo » désigne soit equo, soit aequo. Il est également possible d’utiliser des parenthèses pour définir le champ et la priorité de la détection, « (ae|e)quo » désignant le même ensemble que « aequo|equo » et de quantifier les groupements présents dans le motif en apposant des caractères de quantification à droite de ces groupements.

Les quantificateurs les plus répandus sont :

• ? qui définit un groupe qui existe zéro ou une fois : toto? correspondant alors à « tot » ou « toto » mais pas « totoo » ;
• * qui définit un groupe qui existe zéro, une ou plusieurs fois (l'étoile de Kleene) : toto* correspondant à « tot », « toto », « totoo », « totooo », etc. ;
• + qui définit un groupe qui existe une ou plusieurs fois : toto+ correspondant à « toto », « totoo », « totooo », etc. mais pas « tot ».

Les symboles dotés d'une sémantique particulière peuvent être appelés « opérateurs », « métacaractères » ou « caractères spéciaux ». Les caractères qui ne représentent qu'eux-mêmes sont dits « littéraux ».

Les expressions régulières peuvent être combinées, par exemple par concaténation, pour produire des expressions régulières plus complexes.

Lorsqu'une chaîne de caractères correspond à la description donnée par l'expression régulière, on dit qu'il y a « correspondance » entre la chaîne et le motif, ou que le motif « reconnaît » la chaîne. Cette correspondance peut concerner la totalité ou une partie de la chaîne de caractères. Par exemple, dans la phrase « Les deux équipes ont terminé ex-æquo et se sont saluées. », la sous-chaîne « ex-æquo » est reconnue par le motif « ex-(a?e|æ|é)quo ».

Par défaut, les expressions régulières sont sensibles à la casse. Lorsque c'est possible, elles tentent de reconnaître la plus grande sous-chaîne correspondant au motif : on dit qu'elles sont « gourmandes ». Par exemple, Aa+ reconnaît la totalité de la chaîne « Aaaaaaa » plutôt qu'une partie « Aaa » (gourmandise), mais elle ne reconnaît pas la chaîne « aaaA » (sensibilité à la casse).

Dans le domaine de l'informatique, un outil permettant de manipuler les expressions régulières est appelé un moteur d'expressions régulières ou moteur d'expressions rationnelles. Il existe des standards permettant d'assurer une cohérence dans l'utilisation de ces outils.

Le standard POSIX propose trois jeux de normes :

• BRE (Basic Regular Expressions) pour les expressions régulières basiques. C'est par exemple le standard par défaut pour sed et grep
• ERE (Extended Regular Expressions) pour les expressions régulières étendues.
• SRE (Simple Regular Expressions) qui est devenu obsolète.

Les expressions régulières de perl sont également un standard de fait, en raison de leur richesse expressive et de leur puissance. Tout en suivant leur propre évolution, elles sont par exemple à l'origine de la bibliothèque PCRE. ECMAScript propose également dans le document Standard ECMA-262 une norme employée par exemple par JavaScript.

Les notations ou leurs sémantiques peuvent varier légèrement d'un moteur d'expression régulière à l'autre. Ils peuvent ne respecter que partiellement ces normes, ou de manière incomplète, ou proposer leurs propres fonctionnalités, comme GNU ou le Framework .NET. Les spécificités de chacun sont abordées plus loin dans cet article.

Une classe de caractères désigne un ensemble de caractères. Elle peut être définie de différentes manières :

• en extension ([0123456789] pour les caractères de « 0 » à « 9 ») ;
• en intension ([0-9] en conservant cet exemple) ;
• négativement : les classes [^0123456789] et [^0-9] désignent chacune l'ensemble des caractères qui ne sont pas des chiffres décimaux.

Des unions de classes de caractères peuvent être faites : [0-9ab] désigne l'ensemble constitué des caractères « 0 » à « 9 » et des lettres « a » et « b ». Certaines bibliothèques permettent également de faire des intersections de classes de caractères.

Entre les crochets, les métacaractères sont interprétés de manière littérale : [.?*] désigne l'ensemble constitué des caractères « . », « ? » et « * ».

La plupart des standards et moteurs d'expressions régulières proposent des fonctions avancées. Notamment :

• Quantificateurs non gloutons : Par défaut, les quantificateurs « + » et « * » recherchent la plus grande séquence correspondant au motif recherché. Ces nouveaux quantificateurs, souvent notés « +? » et « *? », permettent à l'inverse de rechercher la plus petite séquence correspondante. Par exemple, l'expression régulière ab+? appliquée à la chaîne « abbbbc » entre en correspondance avec la sous-chaîne « ab » plutôt que « abbbb ».
• Capture des groupements : La capture des groupements permet de réutiliser un groupement entré en correspondance pour un traitement ultérieur, par exemple une substitution. Dans la plupart des syntaxes, il est possible d'accéder au n^ème groupement capturé par la syntaxe « \n » ou parfois « $n », où n est un entier.
• Groupements non capturants : Lorsqu'elle est implémentée, la capture des groupements est souvent le comportement par défaut. Comme elle a un coût algorithmique important, il est parfois possible de désactiver la capture de certains groupements. On peut par exemple citer la syntaxe « (?:groupement) ».
• Captures nommées : Les longues expressions régulières avec de nombreux groupements peuvent être complexes à lire et à maintenir. Pour faciliter cette tâche, certains moteurs permettent de nommer les groupements, par exemple avec la syntaxe « (?P<nom>groupement) » en Python.
• Références arrières : Les références arrières permettent de faire référence à un même groupement capturé. Par exemple « b(.)b\1 » entrera en correspondance avec « bébé » et « bobo » mais pas « baby ». Cette fonctionnalité, proposée par la plupart des moteurs, permet de reconnaître des langages non rationnels tels que aⁿbaⁿ pour tout n entier positif.
• Modificateurs de mode de correspondance : ces modificateurs permettent de faire varier localement le comportement de l'expression régulière. Par exemple, alors qu'elles sont normalement sensibles à la casse, l'expression perl « (?i:nom)-Prénom » entrera en correspondance avec « NOM-Prénom » et « Nom-Prénom » mais pas « Nom-prénom ». Parmi les autres modificateurs, on peut citer le mode multi-lignes, le mode non-gourmand ou le « free-spacing mode ».
• Conditions : certains moteurs permettent de construire des structures « if ... then ... else ... » au sein même des expressions régulières. Par exemple, en perl, l'expression « ^(?(?=[abc])[def]|[ghi]) » se lit : « si la chaîne commence par la lettre a, b ou c, chercher à leur suite la lettre d, e ou f, sinon chercher la lettre g, h ou i. »
• Commentaires : Dans un souci de lisibilité, des moteurs permettent de commenter les expressions régulières au sein même de celles-ci.
• Code embarqué : Lorsqu'une expression régulière est utilisée au sein d'un programme, cette fonctionnalité permet de déclencher des actions lorsqu'une partie de la chaîne est entrée en correspondance.

Les notations utilisées sont très variables. Ce chapitre regroupe d'une part les notations propres à différentes implémentations, et d'autre part, l'entreprise de normalisation.

Les expressions régulières ont originellement été utilisées avec les caractères ASCII. Beaucoup de moteurs d’expressions régulières peuvent maintenant gérer l’Unicode. Sur plusieurs points, le jeu de caractères codés utilisés ne fait aucune différence, mais certains problèmes surgissent dans l’extension des expressions régulières pour Unicode.

Une question est de savoir quel format de représentation interne d’Unicode est supporté. Tous les moteurs d’expressions régulières en ligne de commande attendent de l’UTF-8, mais pour les bibliothèques, certaines attendent aussi de l’UTF-8, mais d’autres attendent un jeu codé sur UCS-2 uniquement (voire son extension UTF-16 qui restreint aussi les séquences valides), ou sur UCS-4 uniquement (voire sa restriction normalisée UTF-32).

Une deuxième question est de savoir si l’intégralité de la plage des valeurs d’une version d’Unicode est supportée. Beaucoup de moteurs ne supportent que le Basic Multilingual Plane, c’est-à-dire, les caractères encodables sur 16 bits. Seuls quelques moteurs peuvent (dès 2006) gérer les plages de valeurs Unicode sur 21 bits.

Une troisième question est de savoir comment les constructions ASCII sont étendues à l’Unicode.

• Par exemple, dans les mises en œuvre ASCII, les plages de valeurs de la forme [x-y] sont valides quels que soient x et y dans la plage 0x0..0x7F et codepoint(x) ≤ codepoint(y).
• L’extension naturelle de ces plages de valeurs Unicode changerait simplement l’exigence sur la plage de valeurs [0..0x7F] en exigence sur la plage étendue à 0..0x1FFFFF.

Cependant, en pratique ce n’est souvent pas le cas :

• Certaines mises en œuvre, telles que celle de gawk, ne permettent pas aux plages de valeurs de couvrir plusieurs blocs Unicode. Une plage de valeurs telle que [0x61..0x7F] est valide puisque les deux bornes tombent à l’intérieur du même bloc Basic Latin, comme 0x530..0x560 qui tombe dans le bloc arménien, mais une plage telle que [0x61..0x532] est invalide puisqu’elle est à cheval sur plusieurs blocs Unicode. Cette restriction s’avère très gênante car de nombreuses langues nécessitent des caractères appartenant à des blocs différents, la définition même des blocs étant arbitraire et provenant seulement du processus historique d’allocation et d’évolution de la norme ISO/IEC 10646 (et en conséquence aussi, des évolutions du standard Unicode). Une telle restriction devrait être à terme levée par une amélioration de l’implémentation.
• D’autres moteurs tels que celui de l’éditeur Vim, permettent le chevauchement de blocs mais limitent le nombre de caractères d’une plage à 128, ce qui est encore plus pénalisant car cela ne permet pas de traiter directement certaines écritures, où il faudrait lister un nombre considérable de sous-plages, avec des conséquences importantes sur les performances. Là aussi, des améliorations sont attendues dans l’implémentation pour lever ces restrictions.

Un autre domaine dans lequel des variations existent est l’interprétation des indicateurs d’insensibilité à la casse.

• De tels indicateurs n’affectent que les caractères ASCII ; d’autres affectent tous les caractères (et prennent en compte la correspondance de casse soit caractère par caractère dans les implémentations les plus simples, soit au niveau du texte entier dans les implémentations respectant les contraintes de langues, ceci pouvant utiliser les correspondances d’un sous-ensemble d’une version donnée d’Unicode, d’autres pouvant utiliser toutes les correspondances de n’importe quelle version d’Unicode, éventuellement précisable au sein même de l’expression régulière).
• Certains moteurs ont deux indicateurs différents, l’un pour ASCII, l’autre pour Unicode.
• Les caractères exacts qui appartiennent aux classes POSIX varient également.

Une autre réponse à Unicode a été l’introduction des classes de caractères pour les blocs Unicode et les propriétés générales des caractères Unicode:

• En Perl et dans la bibliothèque java.util.regex de Java, les classes de la forme \p{InX} valident les caractères du bloc X et \P{InX} valide le complément. Par exemple, \p{Arabic} valide n’importe quel caractère de l’écriture arabe (dans l’un quelconque des blocs normalisés d’Unicode/ISO/IEC 10646 où de tels caractères sont présents).
• Similairement, \p{X} valide n’importe quel caractère ayant la propriété de catégorie générale de caractère X et \P{X} le complément. Par exemple, \p{Lu} valide n’importe quelle lettre capitale (upper-case letter).
• D’autres propriétés que la catégorie générale peuvent être désignées avec la notation \p{prop=valeur} et son complément \P{prop=valeur}, où prop est le code d’une propriété de caractères, et valeur sa valeur attribuée à chaque caractère.
• Enfin des extensions ont été proposées pour utiliser un autre opérateur que la seule égalité (ou différence) de valeur de propriété, en utilisant une syntaxe d’expression régulière ou une simple alternation pour la valeur.

Notes :

• Certaines propriétés de caractères sont normatives et ne devraient pas dépendre de la version utilisée, c’est le cas des propriétés définies dans ISO/IEC 10646 : le nom normalisé du caractère, le point de code, le nom du bloc où le caractère est codé.
• D’autres propriétés sont standards et correspondent à des propriétés normatives du standard Unicode : ce sont essentiellement les propriétés de base définies dans la table principale de caractères Unicode. En principe, elles sont invariables. C’est le cas des correspondances simples de casse (caractère par caractère), ou de la catégorie générale du caractère. Dans bien des cas, ces propriétés ne sont pas adaptées à toutes les langues.
• D’autres propriétés sont informatives, et peuvent faire l’objet de révision d’une version d’Unicode à l’autre : ce sont essentiellement les propriétés définies dans les tables supplémentaires d’Unicode. En particulier elles sont adaptables en fonction de la langue utilisée et désignent par exemple les propriétés de correspondances de casse étendues (traitant le texte dans sa globalité), ou les propriétés d’ordonnancement (collation).
• Cependant certaines de ces dernières tables ont acquis le statut de standard (en étant intégrées dans des annexes standards du standard Unicode) et sont même utilisées dans la définition de certaines normes, ou bien d’autres propriétés historiques sont encore maintenues mais d’usage non recommandé. Consulter le standard Unicode pour connaître le statut actuel de ces propriétés.

Il existe au moins trois familles d'algorithmes qui déterminent si une chaîne de caractères correspond à une expression régulière.

• La plus ancienne approche, dite explicite, repose sur la traduction de l'expression régulière en un automate fini déterministe (AFD). La construction d'un tel automate pour une expression régulière de taille m a une complexité en taille et en mémoire en O(2^m) mais peut être exécutée sur une chaîne de taille n en un temps O(n).

• Une approche alternative, dite implicite, consiste à simuler un automate fini non déterministe en construisant chaque AFD à la volée et en s'en débarrassant à l'étape suivante. Cette approche évite la complexité exponentielle de l'approche précédente, mais le temps d'exécution augmente en O(mn). Ces algorithmes sont rapides mais certaines fonctionnalités telles que la recapture de sous-chaînes et la quantification non gourmande sont difficiles à mettre en oeuvre[18].

• La troisième approche consiste à confronter le motif à la chaîne de caractères par séparation et évaluation ("backtracking"). Sa complexité algorithmique est exponentielle dans le pire des cas, par exemple avec des motifs tels que (a|aa)*b, mais donne de bons résultats en pratique. Elle est plus flexible et autorise un plus grand pouvoir expressif, par exemple en simplifiant la recapture de sous-chaînes.

Certaines implémentations tentent de combiner les qualités des différentes approches, en commençant la recherche avec un AFD, puis en utilisant la séparation et évaluation lorsque c'est nécessaire.