Expression régulière

En informatique, une expression régulière ou expression rationnelle ou expression normale ou motif est une chaîne de caractères qui décrit, selon une syntaxe précise, un ensemble de chaînes de caractères possibles. Les expressions régulières sont également appelées regex (un mot-valise formé depuis l'anglais ). Les expressions rationnelles sont issues des théories mathématiques des langages formels des années 1940. Leur capacité à décrire avec concision des ensembles réguliers explique qu’elles se retrouvent dans plusieurs domaines scientifiques dans les années d’après-guerre et justifie leur adoption en informatique. Les expressions régulières sont aujourd’hui utilisées pour programmer des logiciels avec des fonctionnalités de lecture, de contrôle, de modification, et d'analyse de textes ainsi que dans la manipulation des langues formelles que sont les langages informatiques.

Les expressions régulières ont la qualité de pouvoir être décrites par des formules ou motifs (en anglais ) bien plus simples que les autres moyens.

Histoire 
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 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, 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.

Utilisation 

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é  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.

Principes 
Une expression régulière est une suite de caractères typographiques (qu’on appelle plus simplement « motif » – «  » 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 » ;
 + qui définit un groupe qui existe une ou plusieurs fois : toto+ correspondant à « toto », « totoo », « totooo » 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).

Opérateurs

Standards 
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.

Classe de caractères 
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 « * ».

Standardisation et application 
Les classes de caractères les plus utilisées sont généralement fournies avec le moteur d'expression régulière. Un inventaire de ces classes est dressé dans la table ci-dessous.

La bibliothèque POSIX définit des classes au départ pour l'ASCII, puis, par extension, pour d'autres formes de codage de caractères, en fonction des paramètres régionaux.

Dans Unicode et des langages comme le perl, des ensembles de caractères sont définis au travers de la notion de propriétés de caractères. Cela permet de désigner un ensemble de caractères en fonction de sa catégorie (exemples : lettre, ponctuation ouvrante, ponctuation fermante, séparateur, caractère de contrôle), en fonction du sens d'écriture (par exemple de gauche à droite ou de droite à gauche), en fonction de l'alphabet (exemples : latin, cyrillique, grec, hiragana) ; en fonction de l'allocation des blocs, ou même selon les mêmes principes que les classes de caractères POSIX (à ce sujet, lire la section Expressions régulières et Unicode).

Par exemple, dans le standard POSIX, [[:upper:]ab] fait correspondre un caractère parmi l’ensemble formé par toutes les lettres majuscules ainsi que les lettres minuscules « a » et « b ». Dans le standard ASCII, cette expression régulière s'écrirait [A-Zab].

Classe d'équivalence 
La notion de classe d'équivalence ne doit pas être confondue avec la notion de classe de caractères.

Par exemple, dans la locale FR, la classe [=e=] regroupe l'ensemble des lettres {e, é, è, ë, ê}.

Ceci signifie que lorsqu'elles sont collationnées, les lettres {e, é, è, ë, ê} apparaissent dans le même jeu de caractères, après le d, et avant le f.

Fonctions avancées 
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 anban 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.

Notations : implémentations et standardisation 
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.

Standard POSIX 
Le standard POSIX a cherché à remédier à la prolifération des syntaxes et fonctionnalités, en offrant un standard d’expressions régulières configurables. On peut en obtenir un aperçu en lisant le manuel de regex sous une grande partie des dialectes Unix dont GNU/Linux. Toutefois, même cette norme n’inclut pas toutes les fonctionnalités ajoutées aux expressions régulières de Perl.

Enfin, POSIX ajoute le support pour des plateformes utilisant un jeu de caractère non basé sur l’ASCII, notamment EBCDIC, et un support partiel des locales pour certains méta-caractères.

Expressions régulières basiques 
Les utilitaires du monde Unix tels que sed, GNU grep, ed ou vi utilisent par défaut la norme BRE (« Basic Regular Expression ») de POSIX. Dans celle-ci, les accolades, les parenthèses, le symbole « ? » et le symbole « + » ne sont pas des métacaractères : ils ne représentent qu'eux-mêmes. Pour prendre leur sémantique de métacaractères, ils ont besoin d'être échappés par le symbole « \ ».

Exemple : l'expression régulière (ab.)+ reconnaît « (abc)+ » mais pas « abcabd », pour laquelle \(ab.\)\+ convient.

Expressions régulières étendues 

Les expressions régulières étendues POSIX (ERE pour « Extended Regular Expression ») sont souvent supportées dans les utilitaires des distributions Unix et GNU/Linux en incluant le drapeau -E dans la ligne de commande d’invocation de ces utilitaires. Contrairement aux expressions régulières basiques, elles reconnaissent les caractères vus précédemment comme des métacaractères. Ils doivent ainsi être échappés pour être interprétés littéralement.

La plupart des exemples donnés en présentation sont des expressions régulières étendues POSIX.

Séquences d’échappement 

Comme les caractères (, ), [, ], ., *, ?, +, ^, |, $ , - et \ sont utilisés comme symboles spéciaux, ils doivent être référencés dans une séquence d’échappement s’ils doivent désigner littéralement le caractère correspondant. Ceci se fait en les précédant avec une barre oblique inversée \.

Notation étendue dans vim et emacs 
Des extensions semblables sont utilisées dans l’éditeur emacs, qui utilise un jeu de commandes différent du standard POSIX ; mais reprend les mêmes expressions régulières en apportant une notation étendue. Les expressions régulières étendues sont maintenant supportées aussi dans vim, la version améliorée de vi.

De plus, de nombreuses autres séquences d’échappement sont ajoutées pour désigner des classes de caractères prédéfinies. Elles sont spécifiques à chaque utilitaire ou parfois variables en fonction de la version ou la plateforme (cependant elles sont stables depuis longtemps dans emacs qui a fait figure de précurseur de ces extensions, que d’autres auteurs ont partiellement implémentées de façon limitée ou différente).

Python 
Python utilise des expressions régulières basées sur les expressions régulières POSIX, avec quelques extensions ou différences.

Les éléments compatibles POSIX sont les suivants :
 opérateurs [ ], ., *, ?, +, |, ( )
 caractères \t, \n, \v, \f, \r
 \ooo : caractère littéral dont le code octal (entre 0 et 377, sur 1 à 3 chiffres) est ooo.
 \xNN : caractère littéral dont le code hexadécimal est NN (sur 2 chiffres).

La séquence \b désigne le caractère de retour arrière (0x08 avec un codage compatible ASCII) lorsqu'elle est utilisée à l'intérieur d'une classe de caractère, et la limite d'un mot autrement.

Bibliothèque BSD 

Le système d'exploitation BSD utilise la bibliothèque regex écrite par Henry Spencer. Compatible avec la norme POSIX 1003.2, cette bibliothèque est également utilisée par MySQL  (avec les opérateurs REGEXP et NOT REGEXP) et PostgreSQL (avec l'opérateur « ~ » et ses variantes).

Tcl 
Le moteur d'expressions régulières du langage Tcl est issu de développements d'Henry Spencer postérieurs à ceux de la bibliothèque BSD. Les expressions régulières sont appelées Expressions régulières avancées (ou ARE, Advanced Regular Expressions) et sont légèrement différentes des expressions régulières étendues de POSIX. Les expressions régulières basiques et étendues sont également supportées.

Perl 
Perl offre un ensemble d’extensions particulièrement riche. Ce langage de programmation connaît un succès très important dû à la présence d’opérateurs d’expressions régulières inclus dans le langage lui-même. Les extensions qu’il propose sont également disponibles pour d’autres programmes sous le nom de lib PCRE (, littéralement bibliothèque d’expressions régulières compatible avec Perl). Cette bibliothèque a été écrite initialement pour le serveur de courrier électronique Exim, mais est maintenant reprise par d’autres projets comme Python, Apache, Postfix, KDE, Analog, PHP et Ferite.

Les spécifications de Perl 6 régularisent et étendent le mécanisme du système d’expressions régulières.
De plus il est mieux intégré au langage que dans Perl 5. Le contrôle du retour sur trace y est très fin. Le système de regex de Perl 6 est assez puissant pour écrire des analyseurs syntaxiques sans l’aide de modules externes d’analyse. Les expressions régulières y sont une forme de sous-routines et les grammaires une forme de classe. Le mécanisme est mis en œuvre en assembleur Parrot par le module PGE dans la mise en œuvre Parrot de Perl 6 et en Haskell dans la mise en œuvre Pugs. Ces mises en œuvre sont une étape importante pour la réalisation d’un compilateur Perl 6 complet. Certaines des fonctionnalités des regexp de Perl 6, comme les captures nommées, sont intégrées depuis Perl 5.10.

PHP 
PHP supporte deux formes de notations : la syntaxe POSIX (POSIX 1003.2) et celle, beaucoup plus riche et performante, de la bibliothèque PCRE (Perl Compatible Regular Expression).

Un des défauts reprochés à PHP est lié à son support limité des chaînes de caractères, alors même qu’il est principalement utilisé pour traiter du texte, puisque le texte ne peut y être représenté que dans un jeu de caractères codés sur , sans pouvoir préciser clairement quel codage est utilisé. En pratique, il faut donc adjoindre à PHP des bibliothèques de support pour le codage et le décodage des textes, ne serait-ce que pour les représenter en UTF-8.

ICU 

ICU définit une bibliothèque portable pour le traitement de textes internationaux. Celle-ci est développée d’abord en langage C (version nommée ICU4C) ou pour la plateforme Java (version nommée ICU4J). Des portages (ou adaptations) sont aussi disponibles dans de nombreux autres langages, en utilisant la bibliothèque développée pour le langage C (ou C++).

Les expressions régulières utilisables dans ICU reprennent les caractéristiques des expressions régulières de Perl, mais les complètent pour leur apporter le support intégral du jeu de caractères Unicode (voir la section suivante pour les questions relatives à la normalisation toujours en cours). Elles clarifient également leur signification en rendant les expressions régulières indépendantes du jeu de caractère codé utilisé dans les documents, puisque le jeu de caractères Unicode est utilisé comme codage pivot interne.

En effet, les expressions régulières de Perl (ou PCRE) ne sont pas portables pour traiter des documents utilisant des jeux de caractères codés différents, et ne supportent pas non plus correctement les jeux de caractères codés multi-octets (à longueur variable tels que ISO 2022, Shift-JIS, ou UTF-8), ou codés sur une ou plusieurs unités binaires de plus de  (par exemple UTF-16) puisque le codage effectif de ces jeux sous forme de séquences d’octets dépend de la plateforme utilisée pour le traitement (ordre de stockage des octets dans un mot de plus de ).

ICU résout cela en adoptant un traitement utilisant en interne un jeu unique défini sur  et supportant la totalité du jeu de caractères universel (UCS), tel qu’il est défini dans la norme ISO/IEC 10646 et précisé sémantiquement dans le standard Unicode (qui ajoute à la norme le support de propriétés informatives ou normatives sur les caractères, et des recommandations pour le traitement automatique du texte, certaines de ces recommandations étant optionnelles ou informatives, d’autres étant devenues standards et intégrées au standard Unicode lui-même, d’autres enfin ayant acquis le statut de norme internationale à l’ISO ou de norme nationale dans certains pays).

ICU supporte les extensions suivantes, directement dans les expressions régulières, ou dans l’expression régulière d’une classe de caractères (entre […]) :
 \uhhhh : correspond à un caractère dont le point de code (selon ISO/IEC 10646 et Unicode) a la valeur hexadécimale hhhh.
 \Uhhhhhhhh : correspond à un caractère dont le point de code (selon ISO/IEC 10646 et Unicode) a la valeur hexadécimale hhhhhhhh ; exactement huit chiffres hexadécimaux doivent être fournis, même si le point de code le plus grand accepté est \U0010ffff.
 \N{NOM DU CARACTÈRE UNICODE} : correspond au caractère désigné par son nom normalisé, c’est-à-dire tel qu’il est défini de façon irrévocable dans la norme ISO/IEC 10646 (et repris dans le standard Unicode). Cette syntaxe est une version simplifiée de la syntaxe suivante permettant de désigner d’autres propriétés sur les caractères :
 \p{code d’une propriété Unicode} : correspond à un caractère doté de la propriété Unicode spécifiée.
 \P{code d’une propriété Unicode} : correspond à un caractère non doté de la propriété Unicode spécifiée.
 \s : correspond à un caractère séparateur ; un séparateur est défini comme [\t\n\f\r\p{Z}].

Les expressions régulières d’ICU sont actuellement parmi les plus puissantes et les plus expressives dans le traitement des documents multilingues. Elles sont largement à la base de la normalisation (toujours en cours) des expressions régulières Unicode (voir ci-dessous) et un sous-ensemble est supporté nativement dans la bibliothèque standard du langage Java (qui utilise en interne un jeu de caractères portable à codage variable, basé sur UTF-16 avec des extensions, et dont les unités de codage sont sur ).

ICU est une bibliothèque encore en évolution. En principe, elle devrait adopter toutes les extensions annoncées dans Perl (notamment les captures nommées), dans le but d’assurer l’interopérabilité avec Perl 5, Perl 6, et PCRE, et les autres langages de plus en plus nombreux qui utilisent cette syntaxe étendue, et les auteurs d’ICU et de Perl travaillent en concert pour définir une notation commune. Toutefois, ICU adopte en priorité les extensions adoptées dans les expressions régulières décrites dans le standard Unicode, puisque ICU sert de référence principale dans cette annexe standard d’Unicode.

Toutefois, il n’existe encore aucun standard ou norme technique pour traiter certains aspects importants des expressions régulières dans un contexte multilingue, notamment :
 La prise en compte de l’ordonnancement propre à chaque locale (c’est-à-dire l’ordre de tri, éventuellement multiniveau, des textes en fonction de la langue et de l’écriture, et des unités inséparables de texte qui peuvent comprendre un ou plusieurs caractères codés éventuellement de plusieurs façons possibles mais toutes équivalentes dans cette langue) ; ce manque de normalisation (expérimentation toujours en cours) fait apparaître des différences de traitement et donc de portabilité des classes de caractères contenant des étendues (de la forme [a-b]). Actuellement, ICU ne supporte encore que les étendues dans l’ordre binaire des points de code Unicode, un ordre qui n’est pas du tout approprié pour le traitement correct de nombreuses langues puisqu’il contrevient à leur ordre de collation standard.
 L’ordre des occurrences multiples trouvées dans le texte quand celles-ci peuvent se chevaucher totalement ou partiellement. Cela résulte de l’utilisation de quantificateurs variables, et influe sur le contenu des sous-chaînes capturées. Si cet ordre peut changer, et que seule la première occurrence trouvée est utilisée par exemple dans une opération de recherche et substitution automatique ou le traitement des captures, alors le traitement dépendra de l’implémentation. En théorie, les expressions régulières désignent chacune un ensemble non ordonné de textes, et les accords trouvés dans un texte source peuvent être eux aussi à des positions quelconques dans le texte source, puisque le résultat d’une recherche contient en fait non seulement les captures, mais aussi les positions relatives.

Pour préciser ces derniers aspects manquants, des métacaractères supplémentaires devraient pouvoir être utilisés pour contrôler ou filtrer les occurrences trouvées, ou bien un ordre normalisé imposé à la liste des occurrences retournées. Les auteurs d’applications doivent donc être vigilants sur ces points et s’assurer de lire toutes les occurrences trouvées et pas seulement la première, afin de pouvoir décider laquelle des occurrences est la mieux appropriée à une opération donnée.

Expressions régulières et Unicode 

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 . Seuls quelques moteurs peuvent (dès 2006) gérer les plages de valeurs Unicode sur .

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  sont valides quels que soient x et y dans la plage  et .
 L’extension naturelle de ces plages de valeurs Unicode changerait simplement l’exigence sur la plage de valeurs  en exigence sur la plage étendue à .

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  est valide puisque les deux bornes tombent à l’intérieur du même bloc Basic Latin, comme  qui tombe dans le bloc arménien, mais une plage telle que  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 ().
 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.

Implémentations et complexité algorithmique 
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(2m) 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.

 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.

Notes et références

Notes

Références

Voir aussi

Articles connexes 
 Filtrage par motif
 Algèbre de Kleene

Bibliographie 
 
 
 .
 .
 .

Liens externes 

Langage formel
Automates finis et langages réguliers
Programmation informatique