Worldlex Wiki Le concept d'expressions régulières a vu le jour dans les années 1950, lorsque le mathématicien américain Stephen Cole Kleene a formalisé la notion de langage régulier . Elles se sont rapidement répandues dans les utilitaires de traitement de texte Unix . Différentes syntaxes d'écriture d'expressions régulières existent depuis les années 1980, notamment la norme POSIX et la syntaxe Perl , largement utilisée .
Les expressions régulières sont utilisées dans les moteurs de recherche , dans les boîtes de dialogue de recherche et de remplacement des traitements de texte et des éditeurs de texte , dans les utilitaires de traitement de texte tels que sed et AWK , ainsi que dans l'analyse lexicale . Elles sont prises en charge par de nombreux langages de programmation. Les implémentations en bibliothèque sont souvent appelées « moteurs » , et nombre d'entre elles sont réutilisables.
Les expressions régulières ont vu le jour en 1951, lorsque le mathématicien Stephen Cole Kleene a décrit les langages réguliers à l'aide de sa notation mathématique appelée événements réguliers . Elles sont apparues en informatique théorique , dans les sous-domaines de la théorie des automates (modèles de calcul) et de la description et de la classification des langages formels , motivées par la tentative de Kleene de décrire les premiers réseaux de neurones artificiels . (Kleene l'a introduite comme une alternative au terme « préhensible » de McCulloch et Pitts , mais a admis : « Nous serions ouverts à toute suggestion concernant un terme plus descriptif. » ) Parmi les autres implémentations anciennes de la correspondance de motifs , on peut citer le langage SNOBOL , qui n'utilisait pas d'expressions régulières, mais ses propres constructions de correspondance de motifs.
Les expressions régulières se sont popularisées à partir de 1968, notamment pour la recherche de motifs dans un éditeur de texte et l'analyse lexicale dans un compilateur . Parmi les premières apparitions des expressions régulières dans un programme, on peut citer l'intégration de la notation de Kleene dans l'éditeur QED par Ken Thompson , permettant ainsi la recherche de motifs dans les fichiers texte Par souci de rapidité, Thompson a implémenté la recherche d'expressions régulières par compilation à la volée (JIT) sur le système IBM 7094 du Compatible Time-Sharing System , un exemple précoce et important de compilation JIT . Il a ensuite ajouté cette fonctionnalité à l'éditeur Unix ed , ce qui a finalement conduit à l'utilisation des expressions régulières par l'outil de recherche grep (« grep » est un terme dérivé de la commande de recherche d'expressions régulières dans l'éditeur ed : signifiant « Recherche globale d'expressions régulières et affichage des lignes correspondantes »). À peu près au même moment où Thompson a développé QED, un groupe de chercheurs, dont Douglas T. Ross, a mis en œuvre un outil basé sur des expressions régulières qui est utilisé pour l'analyse lexicale dans la conception de compilateurs . g/re/p
De nombreuses variantes de ces formes originales d'expressions régulières ont été utilisées dans les programmes Unix des laboratoires Bell dans les années 1970, notamment lex , sed , AWK et expr , ainsi que dans d'autres programmes tels que vi et Emacs (qui possède sa propre syntaxe et son propre comportement, incompatibles avec ceux des expressions régulières). Les expressions régulières ont ensuite été adoptées par un large éventail de programmes, et ces premières formes ont été normalisées dans la norme POSIX.2 en 1992.
Dans les années 1980, les expressions régulières plus complexes sont apparues en Perl , dérivées d'une bibliothèque d'expressions régulières écrite par Henry Spencer (1986), qui a ensuite développé une implémentation pour Tcl appelée Advanced Regular Expressions . Cette bibliothèque Tcl est une implémentation hybride NFA / DFA aux performances améliorées. Parmi les projets logiciels ayant adopté l'implémentation Tcl des expressions régulières de Spencer figure PostgreSQL . Perl a par la suite enrichi la bibliothèque originale de Spencer en y ajoutant de nombreuses nouvelles fonctionnalités . L'un des objectifs de la conception de Raku (anciennement Perl 6) est d'améliorer l'intégration des expressions régulières dans Perl et d'étendre leur portée et leurs capacités afin de permettre la définition de grammaires d'expressions syntaxiques . Il en résulte un mini-langage appelé règles Raku , qui servent à définir la grammaire Raku et constituent un outil précieux pour les programmeurs. Ces règles conservent les fonctionnalités existantes des expressions régulières Perl 5.x, mais permettent également la définition de style BNF d'un analyseur syntaxique descendant récursif via des sous-règles.
L'utilisation des expressions régulières dans les normes d'information structurée pour la modélisation de documents et de bases de données a débuté dans les années 1960 et s'est développée dans les années 1980 avec la consolidation de normes industrielles telles que l'ISO SGML (précurseur de l'ANSI « GCA 101-1983 »). Le cœur des normes de spécification de langage de structure repose sur les expressions régulières. Leur utilisation est manifeste dans la syntaxe des groupes d'éléments des DTD . Avant l'avènement des expressions régulières, de nombreux langages de recherche autorisaient l'utilisation de caractères génériques simples, par exemple « * » pour correspondre à n'importe quelle séquence de caractères et « ? » à un seul caractère. On en retrouve encore des traces aujourd'hui dans la syntaxe glob pour les noms de fichiers et dans l' opérateur SQLLIKE .
À partir de 1997, Philip Hazel a développé PCRE (Perl Compatible Regular Expressions), qui tente d'imiter de près la fonctionnalité regex de Perl et est utilisé par de nombreux outils modernes, notamment PHP et le serveur HTTP Apache .
Aujourd'hui, les expressions régulières sont largement prises en charge par les langages de programmation, les logiciels de traitement de texte (notamment les analyseurs lexicaux ), les éditeurs de texte avancés et d'autres programmes. La prise en charge des expressions régulières fait partie de la bibliothèque standard de nombreux langages de programmation, dont Java et Python , et est intégrée à la syntaxe d'autres, comme Perl et ECMAScript . À la fin des années 2010, plusieurs entreprises ont commencé à proposer des implémentations matérielles ( FPGA [ et GPU de moteurs d'expressions régulières compatibles PCRE plus rapides que les implémentations sur CPU .
Motifs
L'expression « expressions régulières » (ou regexes ) désigne la syntaxe textuelle standard permettant de représenter des motifs pour la correspondance de texte, par opposition à la notation mathématique décrite ci-dessous. Chaque caractère d'une expression régulière (c'est-à-dire chaque caractère de la chaîne décrivant son motif) est soit un métacaractère , ayant une signification particulière, soit un caractère ordinaire ayant une signification littérale. Par exemple, dans l'expression régulière b.`b5`, `b` est un caractère ordinaire qui correspond à `b`, tandis que `.` est un métacaractère qui correspond à tous les caractères sauf un saut de ligne. Ainsi, cette expression régulière correspond, par exemple, à `b%`, `bx` ou `b5`. L'utilisation conjointe de métacaractères et de caractères ordinaires permet d'identifier un texte correspondant à un motif donné ou de traiter plusieurs occurrences de ce motif. La correspondance peut varier d'une égalité précise à une similarité très générale, selon les métacaractères. Par exemple, `a` .est un modèle très général [a-z](correspond à toutes les lettres minuscules de « a » à « z »), `b` est moins général et b`b` est un modèle précis (correspond uniquement à « b »). La syntaxe des métacaractères est spécifiquement conçue pour représenter des cibles prédéfinies de manière concise et flexible afin de diriger l'automatisation du traitement de texte de diverses données d'entrée, sous une forme facile à saisir à l'aide d'un clavier ASCII standard .
Un cas très simple d'utilisation d'une expression régulière dans cette syntaxe consiste à localiser un mot orthographié de deux manières différentes dans un éditeur de texte ; par exemple, l'expression régulière seriali[sz]ecorrespond à la fois à « serialise » et à « serialize ». Les caractères génériques permettent également d'obtenir ce résultat, mais leurs possibilités sont plus limitées, car ils possèdent moins de métacaractères et une base linguistique plus simple.
L'utilisation habituelle des caractères génériques consiste à rechercher des noms similaires dans une liste de fichiers, tandis que les expressions régulières sont généralement employées dans des applications qui effectuent une correspondance de motifs sur des chaînes de caractères. Par exemple, l'expression régulière ` ` correspond aux espaces superflus en début ou en fin de ligne. Une expression régulière avancée qui correspond à n'importe quel chiffre est ` ` . Un processeur d'expressions régulières traduit une expression régulière, selon la syntaxe ci-dessus, en une représentation interne exécutable et comparable à une chaîne de caractères représentant le texte à rechercher. Une approche possible consiste à utiliser l'algorithme de Thompson pour construire un automate fini non déterministe (AFN), qui est ensuite rendu déterministe . L'automate fini déterministe (AFD) ainsi obtenu est exécuté sur la chaîne de caractères cible afin d'identifier les sous-chaînes correspondant à l'expression régulière. L'illustration montre le schéma de l'AFN obtenu à partir de l'expression régulière , où s désigne une expression régulière plus simple, elle-même préalablement traduite récursivement en l'AFN N ( s ).N(s*)s*
Concepts de base
Une expression régulière, souvent appelée motif , spécifie un ensemble de chaînes de caractères nécessaires à un usage particulier. Une manière simple de spécifier un ensemble fini de chaînes consiste à lister ses éléments . Cependant, il existe souvent des méthodes plus concises : par exemple, l’ensemble contenant les trois chaînes « Handel », « Händel » et « Haendel » peut être spécifié par le motifH(ä|ae?)ndel ; on dit que ce motif correspond à chacune des trois chaînes. Toutefois, il existe plusieurs façons d’écrire une expression régulière pour le même ensemble de chaînes : par exemple, (Hän|Han|Haen)delspécifie également le même ensemble de trois chaînes dans cet exemple.
La plupart des formalismes proposent les opérations suivantes pour construire des expressions régulières.
- Opérateur booléen « ou »
- Une barre verticale sépare les alternatives. Par exemple, peut correspondre à « gris » ou « gris ».
Les parenthèses servent notamment à définir la portée et la priorité des opérateurs . Par exemple, `gray|greya` et `b` sont des expressions équivalentes qui décrivent toutes deux l'ensemble des valeurs « gris » ou « gris ».quantificateur placé après un élément (tel qu'un jeton , un caractère ou un groupe) indique combien de fois cet élément peut se répéter. Les quantificateurs les plus courants sont le point d'interrogation?, l' astérisque*(dérivé de l' étoile de Kleene ) et le signe plus+( plus de Kleene ). ?Le point d'interrogation indique zéro ou une occurrence de l'élément précédent. Par exemple, colou?ril correspond à la fois à « color » et à « colour ».*L'astérisque indique zéro ou plusieurs occurrences de l'élément précédent. Par exemple, ab*cil correspond à « ac », « abc », « abbc », « abbbc », etc.+Le signe plus indique une ou plusieurs occurrences de l'élément précédent. Par exemple, ab+cil correspond à « abc », « abbc », « abbbc », etc., mais pas à « ac ».{n}L'élément précédent correspond exactement n fois. {min,}L'élément précédent correspond à min fois ou plus. {,max}L'élément précédent correspond jusqu'à un maximum de fois. {min,max}L'élément précédent est reproduit au moins min fois, mais pas plus de max fois. - joker
- Le caractère générique
.correspond à n'importe quel caractère. Par exemple,a.bcorrespond à toute chaîne contenant un « a », puis n'importe quel caractère, puis « b ».a.*bCorrespond à toute chaîne de caractères contenant un « a », puis le caractère « b » à un moment donné.
Ces constructions peuvent être combinées pour former des expressions arbitrairement complexes, tout comme on peut construire des expressions arithmétiques à partir de nombres et des opérations +, −, × et ÷.
La syntaxe précise des expressions régulières varie selon les outils et le contexte ; plus de détails sont donnés dans les langages réguliers en théorie des langages formels . Elles possèdent le même pouvoir expressif que les grammaires régulières . Cependant, le langage des expressions régulières lui-même est un langage hors contexte .
Définition formelle
Les expressions régulières sont composées de constantes, qui désignent des ensembles de chaînes de caractères, et de symboles d'opérateurs, qui désignent des opérations sur ces ensembles. La définition suivante est standard et se retrouve telle quelle dans la plupart des manuels de théorie des langages formels. Étant donné un alphabet fini Σ, les constantes suivantes sont définies comme des expressions régulières :
- ( ensemble vide ) ∅ désignant l'ensemble ∅.
- ( chaîne vide ) ε désignant l'ensemble contenant uniquement la chaîne « vide », qui ne contient aucun caractère.
- ( caractère littéral )
adans Σ désignant l'ensemble contenant uniquement le caractère a .
Étant donné les expressions régulières R et S, les opérations suivantes sont définies sur celles-ci pour produire des expressions régulières :
- La concaténation désigne
(RS)l'ensemble des chaînes de caractères obtenues en concaténant une chaîne acceptée par R et une chaîne acceptée par S (dans cet ordre). Par exemple, si R représente {"ab", "c"} et S représente {"d", "ef"}, alors la(RS)concaténation désigne {"abd", "abef", "cd", "cef"}. - ( alternance )
(R|S)désigne l' union des ensembles décrits par R et S. Par exemple, si R décrit {"ab", "c"} et S décrit {"ab", "d", "ef"}, l'expression(R|S)décrit {"ab", "c", "d", "ef"}. - L' étoile de Kleene
(R*)désigne le plus petit sur-ensemble de l'ensemble décrit par R contenant ε et stable par concaténation de chaînes. Il s'agit de l'ensemble de toutes les chaînes que l'on peut obtenir en concaténant un nombre fini quelconque (y compris zéro) de chaînes de l'ensemble décrit par R. Par exemple, si R désigne {"0", "1"}, l'étoile de Kleene(R*)désigne l'ensemble de toutes les chaînes binaires finies (y compris la chaîne vide). Si R désigne {"ab", "c"}, l'étoile de Kleene(R*)désigne {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "abcab", ...}.
Pour éviter les parenthèses, on considère que l'étoile de Kleene est prioritaire, suivie de la concaténation, puis de l'alternance. En l'absence d'ambiguïté, les parenthèses sont omises. Par exemple, peut s'écrire et (ab)c. abcDe nombreux manuels utilisent les symboles ∪, + ou ∨ pour l'alternance au lieu de la barre verticale.a|(b(c*))a|bc*
Exemples :
a|b*désigne {ε, "a", "b", "bb", "bbb", ...}(a|b)*désigne l'ensemble de toutes les chaînes de caractères ne contenant aucun symbole autre que « a » et « b », y compris la chaîne vide : {ε, "a", "b", "aa", "ab", "ba", "bb", "aaa", ...}ab*(c|ε)désigne l'ensemble des chaînes commençant par "a", puis zéro ou plusieurs "b" et enfin éventuellement un "c" : {"a", "ac", "ab", "abc", "abb", "abbc", ...}(0|(1(01*0)*1))*désigne l'ensemble des nombres binaires qui sont des multiples de 3 : { ε, "0", "00", "11", "000", "011", "110", "0000", "0011", "0110", "1001", "1100", "1111", "00000", ...}
La dérivée d'une expression régulière peut être définie à l'aide de la dérivée de Brzozowski .
Puissance expressive et compacité
La définition formelle des expressions régulières est volontairement minimale et évite de définir `a` ?et +`b` — ceux-ci peuvent être exprimés comme suit : a+`a = b` aa*et a?`b = c` (a|ε). Parfois, l’ opérateur de complément est ajouté pour obtenir une expression régulière généralisée ; ici, `R <sub>c</sub>` correspond à toutes les chaînes sur `Σ*` qui ne correspondent pas à `R` . En principe, l’opérateur de complément est redondant, car il n’apporte aucun pouvoir d’expression supplémentaire. Cependant, il peut rendre une expression régulière beaucoup plus concise — la suppression d’un seul opérateur de complément peut entraîner une augmentation exponentielle double de sa longueur.
Les expressions régulières, au sens strict, peuvent exprimer les langages réguliers, c'est-à-dire la classe de langages reconnus par les automates finis déterministes . Il existe cependant une différence significative en termes de compacité. Certaines classes de langages réguliers ne peuvent être décrites que par des automates finis déterministes dont la taille croît exponentiellement avec celle des expressions régulières équivalentes les plus courtes. L'exemple classique est celui des langages L <sub>k</sub> constitués de toutes les chaînes de caractères de l'alphabet { a , b } dont la k -ième lettre en partant de la fin est égale à a . Une expression régulière décrivant L<sub> 4 </sub> est donnée par …
En généralisant ce modèle à L k, on obtient l'expression :
D'autre part, on sait que tout automate fini déterministe reconnaissant le langage L <sub>k</sub> doit posséder au moins 2<sup> k</sup> états. Heureusement, il existe une transformation simple des expressions régulières vers les automates finis non déterministes (AFN), plus généraux, qui n'entraîne pas une telle explosion de taille ; c'est pourquoi les AFN sont souvent utilisés comme représentations alternatives des langages réguliers. Les AFN sont une variante simple des grammaires de type 3 de la hiérarchie de Chomsky .
À l'inverse, de nombreux langages facilement décrits par un automate fini déterministe (AFD) ne le sont pas par une expression régulière. Par exemple, déterminer la validité d'un ISBN donné nécessite le calcul du reste de la division d'un entier par 11 et peut être facilement implémenté avec un AFD à 11 états. Cependant, sa conversion en expression régulière génère un fichier de 2,14 mégaoctets.
Étant donné une expression régulière, l'algorithme de construction de Thompson calcule un automate fini non déterministe équivalent. La conversion inverse est réalisée par l'algorithme de Kleene .
Enfin, de nombreux moteurs d'« expressions régulières » utilisés dans le monde réel implémentent des fonctionnalités qui ne peuvent être décrites par les expressions régulières au sens de la théorie des langages formels ; ils implémentent plutôt des regex . Voir ci-dessous pour plus de détails.
Déterminer l'équivalence des expressions régulières
Comme on l'a vu dans plusieurs des exemples ci-dessus, il existe plusieurs façons de construire une expression régulière pour obtenir les mêmes résultats.
Il est possible d'écrire un algorithme qui, pour deux expressions régulières données, décide si les langages décrits sont égaux ; l'algorithme réduit chaque expression à une machine à états finis déterministe minimale et détermine si elles sont isomorphes (équivalentes).
Les lois algébriques des expressions régulières peuvent être obtenues par une méthode de Gischer, qu'il est préférable d'illustrer par un exemple : pour vérifier si ( X + Y ) * et ( X * Y * ) * désignent le même langage régulier, pour toutes expressions régulières X et Y , il est nécessaire et suffisant de vérifier si les expressions régulières particulières ( a + b ) * et ( a * b * ) * désignent le même langage sur l'alphabet Σ = { a , b }. Plus généralement, une équation E = F entre termes d'expressions régulières avec variables est vérifiée si, et seulement si, son instanciation avec différentes variables remplacées par différentes constantes symboliques est également vérifiée.
Toute expression régulière peut être écrite uniquement à l'aide de l' étoile de Kleene et des unions d'ensembles sur les mots finis. Il s'agit d'un problème étonnamment difficile. Malgré leur simplicité apparente, les expressions régulières ne peuvent être systématiquement réécrites sous une forme normale. L'absence d'axiomes a conduit par le passé au problème de la hauteur de l'étoile . En 1991, Dexter Kozen a axiomatisé les expressions régulières en tant qu'algèbre de Kleene , en utilisant des axiomes équationnels et des clauses de Horn . Dès 1964, Redko avait démontré qu'aucun ensemble fini d'axiomes purement équationnels ne peut caractériser l'algèbre des langages réguliers.
Syntaxe
Un motif d' expression régulière (regex) correspond à une chaîne cible . Ce motif est composé d'une séquence d' atomes . Un atome est un point unique du motif que celui-ci tente de faire correspondre à la chaîne cible. L'atome le plus simple est une valeur littérale, mais le regroupement de parties du motif pour correspondre à un atome nécessite l'utilisation de métacaractères. Les métacaractères permettent de former : des atomes ; des quantificateurs indiquant le nombre d'atomes (et s'il s'agit d'un quantificateur gourmand ou non) ; un caractère OU logique, qui propose un ensemble d'alternatives, et un caractère NON logique, qui nie l'existence d'un atome ; et des références arrières pour faire référence aux atomes précédents d'un motif complet. Une correspondance est établie non pas lorsque tous les atomes de la chaîne correspondent, mais plutôt lorsque tous les atomes du motif dans l'expression régulière correspondent. L'idée est de faire en sorte qu'un petit motif de caractères représente un grand nombre de chaînes possibles, plutôt que de compiler une longue liste de toutes les possibilités littérales.()
Selon le processeur d'expressions régulières, il existe environ quatorze métacaractères, des caractères dont la signification littérale peut varier selon le contexte, ou qui peuvent être « échappés » (c'est-à-dire précédés d'une séquence d'échappement , ici la barre oblique inverse) \. Les expressions régulières modernes et étendues POSIX utilisent plus fréquemment les métacaractères que leur signification littérale. Afin d'éviter les erreurs de saisie (ou « syndrome du cure-dent incliné ») , elles disposent d'une fonction permettant d'échapper les métacaractères à leur signification littérale. Initialement, elles utilisent les quatre métacaractères d'encadrement et ont une signification principalement littérale, les caractères « échappant » à leur signification habituelle pour devenir des métacaractères. Les normes courantes implémentent les deux approches. Les métacaractères usuels sont `\` et `\` . Les caractères usuels qui deviennent des métacaractères lorsqu'ils sont échappés sont `\` et `\ `.(){} {}[]()^$.|*+?\dswDSWN
Délimiteurs
Lorsqu'on saisit une expression régulière dans un langage de programmation, elle peut être représentée comme une chaîne de caractères littérale classique, généralement entre guillemets ; c'est le cas en C, Java et Python, par exemple, où l' expression régulière s'écrit ` regex` re. Cependant , on"re" utilise souvent des barres obliques comme délimiteurs , comme dans ` /re/regex re. ... Dans certains cas, comme avec sed et Perl, des délimiteurs alternatifs peuvent être utilisés pour éviter les conflits avec le contenu et pour s'affranchir de l'échappement des occurrences du caractère délimiteur dans le contenu. Par exemple, avec sed, la commande remplacera un caractère par un autre , en utilisant la virgule comme délimiteur.//re/g/re/ps/re/replacement//re1/,/re2/s,/,X,/X
Norme IEEE POSIX
La norme IEEE POSIX comprend trois ensembles de conformité : BRE (expressions régulières de base), ERE (expressions régulières étendues) et SRE (expressions régulières simples). L’utilisation de SRE est déconseillée [ au profit de BRE, les deux assurant la rétrocompatibilité . La sous-section ci-dessous, relative aux de caractères, s’applique à la fois à BRE et à ERE.
BRE et ERE fonctionnent de concert. ERE ajoute les caractères `\` ?, +`\` et `| \`, et supprime la nécessité d'échapper les métacaractères `\` et `\`, requis par BRE. De plus, tant que la syntaxe standard POSIX des expressions régulières est respectée, il peut exister, et existe souvent, une syntaxe supplémentaire pour des applications spécifiques (tout en restant conformes à POSIX). Bien que POSIX.2 laisse certains détails d'implémentation indéfinis, BRE et ERE fournissent une norme qui a depuis été adoptée comme syntaxe par défaut par de nombreux outils, où le choix entre les modes BRE et ERE est généralement une option prise en charge. Par exemple, GNU propose les options suivantes : ` \` pour ERE, `\ ` pour BRE (par défaut) et `\ ` pour les expressions régulières Perl .(){}grepgrep -Egrep -Ggrep -P
Les expressions régulières Perl sont devenues un standard de facto, grâce à leur ensemble riche et puissant d'expressions atomiques. Perl ne possède pas de niveaux « basique » ou « étendu ». Comme dans les expressions régulières POSIX, les caractères `\` et `\` sont traités comme des métacaractères, sauf s'ils sont échappés ; les autres métacaractères sont interprétés comme littéraux ou symboliques selon le contexte. Parmi les fonctionnalités supplémentaires, on trouve la correspondance paresseuse , les références arrière , les groupes de capture nommés et les motifs récursifs .(){}
POSIX de base et étendu
Dans la norme POSIX , la syntaxe régulière de base ( BRE ) exige que les métacaractères et soient désignés et , alors que la syntaxe régulière étendue ( ERE ) ne le fait pas.(){}\(\)\{\}
| Métapersonnage | Description | |||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
^ | Correspond à la position de départ dans la chaîne. Dans les outils fonctionnant ligne par ligne, elle correspond à la position de départ de n'importe quelle ligne. | |||||||||||||||||||||||||||||||||||||||||
. | Correspond à n'importe quel caractère unique (de nombreuses applications excluent les sauts de ligne , et la définition précise de ces sauts de ligne dépend du système, de l'encodage et de la plateforme, mais on peut supposer sans risque que le caractère de saut de ligne est inclus). Dans les expressions entre crochets POSIX, le point correspond à un point littéral. Par exemple, a.ccorrespond à « abc », etc., mais [a.c]correspond uniquement à « a », « . » ou « c ». | |||||||||||||||||||||||||||||||||||||||||
[] | Une expression entre crochets. Correspond à un seul caractère contenu entre crochets. Par exemple, [abc]correspond à « a », « b » ou « c ». [a-z]Spécifie une plage qui correspond à n'importe quelle lettre minuscule de « a » à « z ». Ces formes peuvent être combinées : [abcx-z]correspond à « a », « b », « c », « x », « y » ou « z », tout comme [a-cx-z]. Le | |||||||||||||||||||||||||||||||||||||||||
[^] | Correspond à un caractère unique qui n'est pas contenu entre crochets. Par exemple, [^abc]correspond à tout caractère autre que « a », « b » ou « c ». [^a-z]Correspond à tout caractère unique qui n'est pas une lettre minuscule de « a » à « z ». De même, les caractères littéraux et les plages peuvent être combinés. | |||||||||||||||||||||||||||||||||||||||||
$ | Correspond à la position de fin de la chaîne ou à la position juste avant un saut de ligne. Dans les outils fonctionnant ligne par ligne, correspond à la position de fin de n'importe quelle ligne. | |||||||||||||||||||||||||||||||||||||||||
( ) | Définit une sous-expression marquée, également appelée groupe de capture, essentielle pour extraire la partie de texte souhaitée (voir aussi l'entrée suivante ). Le mode BRE requiert …\n[^hc]atcorrespond à toutes les chaînes de caractères correspondant à .atautre que « chapeau » et « chat ».^[hc]atCorrespond à « chapeau » et « chat », mais seulement au début de la chaîne ou de la ligne.[hc]at$Correspond à « chapeau » et « chat », mais seulement à la fin de la chaîne ou de la ligne.\[.\]correspond à n'importe quel caractère unique entouré de "[" et "]" puisque les crochets sont échappés, par exemple : "[a]", "[b]", "[7]", "[@]", "[]]", "[ ]" (crochet espace crochet).s.*correspond à s suivi de zéro ou plusieurs caractères, par exemple : "s", "saw", "seed", "s3w96.7", et "s6#h%(>>>mn mQ".Selon Russ Cox, la spécification POSIX exige que les sous-expressions ambiguës soient traitées différemment de Perl. Le comité a remplacé les règles de Perl par des règles simples à expliquer, mais ces nouvelles règles « simples » sont en réalité plus complexes à mettre en œuvre : elles étaient incompatibles avec les outils existants et rendaient pratiquement impossible la définition d’une extension de « correspondance paresseuse » (voir ci-dessous). De ce fait, très peu de programmes implémentent les règles de sous-expressions POSIX (même lorsqu’ils implémentent d’autres parties de la syntaxe POSIX). Métacaractères dans POSIX étenduLa signification des métacaractères échappés par une barre oblique inverse est inversée pour certains caractères dans la syntaxe des expressions régulières étendues ( ERE ) POSIX. Avec cette syntaxe, une barre oblique inverse entraîne le traitement du métacaractère comme un caractère littéral. Ainsi, par exemple, `\ r` vaut désormais ` ` et ` ` vaut désormais ` ` . De plus, la prise en charge des références arrières est supprimée et les métacaractères suivants sont ajoutés :
Exemples :
Les expressions régulières étendues POSIX peuvent souvent être utilisées avec les utilitaires Unix modernes en incluant l' option de ligne de commande -E . classes de personnagesLa classe de caractères est le concept le plus élémentaire des expressions régulières après la correspondance littérale. Elle permet à une petite séquence de caractères de correspondre à un ensemble plus large de caractères. Par exemple, « a » En Python et dans certaines autres implémentations (par exemple Java), les trois quantificateurs courants ( « Ganymède », poursuivit-il, « est la plus grande lune du système solaire. » correspond à la ligne entière (car la ligne entière commence et se termine par un guillemet double) au lieu de ne correspondre qu'à la première partie En Java et Python 3.11+, les quantificateurs peuvent être rendus possessifs en ajoutant un signe plus, ce qui désactive le retour arrière (dans un moteur de retour arrière), même si cela permettrait à la correspondance globale de réussir : Alors que l’expression régulière « Ganymède », poursuivit-il, « est la plus grande lune du système solaire. » L'expression régulière `&` correspond à la ligne entière, tandis que `&` Une autre extension courante remplissant la même fonction est le groupement atomique, qui désactive le retour arrière pour un groupe entre parenthèses. La syntaxe typique est (? > groupe) . Par exemple, alors que ^(wi|w)i$ correspond à la fois à wi et à wii , ^(? > wi|w)i$ ne correspond qu'à wii car le moteur n'est pas autorisé à effectuer de retour arrière et ne peut donc pas tenter de définir le groupe sur « w » après avoir trouvé « wi ». langages réguliers . Par exemple, de nombreuses implémentations permettent de regrouper des sous-expressions entre parenthèses et de rappeler la valeur à laquelle elles correspondent dans la même expression ((références arrière ). Cela signifie que, entre autres, un motif peut correspondre à des chaînes de mots répétés comme « papa » ou « WikiWiki », appeléescarrésen théorie des langages formels. Le motif pour ces chaînes est Le langage des carrés n'est ni régulier, ni hors contexte , en raison du lemme de pompage . Cependant, la recherche de motifs avec un nombre illimité de références arrière, prise en charge par de nombreux outils modernes, reste sensible au contexte . Le problème général de la recherche d'un nombre quelconque de références arrière est NP-complet , et le temps d'exécution des algorithmes connus croît exponentiellement avec le nombre de groupes de références arrière utilisés. Cependant, de nombreux outils, bibliothèques et moteurs proposant de telles constructions utilisent encore le terme « expression régulière » pour désigner leurs modèles. Il en résulte une nomenclature où l'expression régulière revêt différentes significations en théorie des langages formels et en correspondance de modèles. C'est pourquoi certains utilisent les termes « regex » , « regexp » ou simplement « modèle » pour décrire ces derniers. Larry Wall , auteur du langage de programmation Perl, écrit dans un essai sur la conception de Raku : Les « expressions régulières » […] n’ont qu’un rapport marginal avec les véritables expressions régulières. Néanmoins, le terme s’est développé au rythme des capacités de nos moteurs de correspondance de modèles, aussi ne vais-je pas m’opposer ici à une nécessité linguistique. Je les appellerai cependant généralement « regexes » (ou « regexen », lorsque je suis d’humeur anglo-saxonne). Parmi les autres fonctionnalités absentes de la description des langages réguliers figurent les assertions. Celles-ci incluent les assertions omniprésentes ` La méthode la plus ancienne et la plus rapide repose sur un résultat de la théorie des langages formels permettant de transformer tout automate fini non déterministe (AFN) en un automate fini déterministe (AFD). L'AFD peut être construit explicitement, puis exécuté symbole par symbole sur la chaîne d'entrée résultante. La construction de l'AFD pour une expression régulière de taille m a un coût temporel et mémoire de O (2<sup> m</sup> ), mais son exécution sur une chaîne de taille n s'effectue en O ( n ). Il est important de noter que la taille de l'expression est sa taille après développement des abréviations, telles que les quantificateurs numériques. Une autre approche consiste à simuler directement l'automate fini non déterministe (AFN), en construisant chaque état de l'automate fini déterministe (AFD) à la demande, puis en le supprimant à l'étape suivante. Cette méthode préserve l'AFD de manière implicite et évite le coût exponentiel de sa construction, mais le coût d'exécution passe à O ( mn ). L'approche explicite est appelée algorithme AFD et l'approche implicite, algorithme AFN. L'ajout d'un système de cache à l'algorithme AFN est souvent appelé algorithme « AFD paresseux », ou simplement algorithme AFD, sans distinction. Ces algorithmes sont rapides, mais leur utilisation pour le rappel de sous-expressions groupées, la quantification paresseuse et autres fonctionnalités similaires est complexe. Parmi les implémentations modernes, on trouve la famille re1- re2 -sregex, basée sur le code de Cox. Le troisième algorithme consiste à comparer le motif à la chaîne d'entrée par retour arrière . Cet algorithme est communément appelé automate fini non déterministe (AFN), mais cette terminologie peut prêter à confusion. Son temps d'exécution peut être exponentiel, ce que présentent les implémentations simples lors de la comparaison avec des expressions contenant à la fois des alternances et des quantifications non bornées, obligeant ainsi l'algorithme à considérer un nombre exponentiellement croissant de sous-cas. Ce comportement peut engendrer une faille de sécurité appelée attaque par déni de service par expression régulière (ReDoS). Bien que les implémentations avec retour arrière n'offrent qu'une garantie exponentielle dans le pire des cas, elles offrent une flexibilité et une expressivité bien supérieures. Par exemple, toute implémentation autorisant l'utilisation de références arrière ou implémentant les diverses extensions introduites par Perl doit inclure une forme de retour arrière. Certaines implémentations tentent de combiner les avantages des deux algorithmes en exécutant d'abord un automate fini déterministe (AFD) rapide, puis en revenant à un algorithme avec retour arrière potentiellement plus lent uniquement lorsqu'une référence arrière est rencontrée lors de la recherche. GNU grep (et l'AFD sous-jacent de gnulib) utilise une telle stratégie. Des algorithmes à complexité sous-linéaire ont été obtenus grâce à des algorithmes basés sur l'algorithme de Boyer-Moore (BM) et des techniques d'optimisation d'automates finis déterministes (AFD) associées, telles que le balayage inverse. GNU grep, compatible avec une grande variété de syntaxes et d'extensions POSIX, utilise BM pour un préfiltrage initial, puis un AFD implicite. Wu agrep , qui implémente la correspondance approximative, intègre le préfiltrage à l'AFD dans BDM (correspondance DAWG inverse). BNDM de NR-grep étend la technique BDM avec un parallélisme binaire de type Shift-Or. Il existe quelques alternatives théoriques au retour arrière pour les références arrière, et leurs « exposants » sont plus modérés car ils ne dépendent que du nombre de références arrière, une propriété fixe de certains langages d'expressions régulières comme POSIX. Une méthode naïve qui duplique un automate fini non déterministe (AFN) sans retour arrière pour chaque référence arrière a une complexité et spatiale de ASCII , bien que les bibliothèques d'expressions régulières aient pris en charge de nombreux autres jeux de caractères . De nombreux moteurs d'expressions régulières modernes offrent une prise en charge partielle d'Unicode . Dans la plupart des cas, le jeu de caractères importe peu, mais l'extension des expressions régulières pour prendre en charge Unicode peut engendrer des problèmes. Certains logiciels de PAO haut de gamme permettent d'utiliser des expressions régulières pour appliquer automatiquement des styles de texte, évitant ainsi au maquettiste une tâche fastidieuse : l'application manuelle des styles correspondant aux caractères pouvant être identifiés par une expression régulière est grandement facilitée. Par exemple, en définissant un style de caractère convertissant le texte en petites capitales , puis en appliquant Bien que les expressions régulières soient utiles pour les moteurs de recherche Internet , leur traitement à l'échelle de la base de données peut consommer des ressources informatiques excessives, selon leur complexité et leur conception. Si, dans de nombreux cas, les administrateurs système peuvent exécuter des requêtes basées sur des expressions régulières en interne, la plupart des moteurs de recherche ne proposent pas cette fonctionnalité au public. Google Code Search et Exalead constituent des exceptions notables . Cependant, Google Code Search a été fermé en janvier 2012. Les règles de syntaxe spécifiques varient selon l'implémentation, le langage de programmation ou la bibliothèque utilisés. De plus, les fonctionnalités des expressions régulières peuvent varier d' une version à l'autre . Les expressions régulières étant souvent difficiles à expliquer et à comprendre sans exemples, les sites web interactifs permettant de les tester constituent une ressource précieuse pour les apprendre par l'expérimentation. Cette section présente une description sommaire de certaines propriétés des expressions régulières à titre d'illustration. Les conventions suivantes sont utilisées dans les exemples. Ces expressions régulières utilisent toutes une syntaxe similaire à celle de Perl. Les expressions régulières POSIX standard sont différentes. Sauf indication contraire, les exemples suivants sont conformes au langage de programmation Perl , version 5.8.8, du 31 janvier 2006. Cela signifie que d'autres implémentations peuvent ne pas prendre en charge certaines parties de la syntaxe présentée ici (par exemple, les expressions régulières de base par rapport aux expressions régulières étendues, ou l'absence de ` La syntaxe et les conventions utilisées dans ces exemples coïncident également avec celles d'autres environnements de programmation. Sortir: Sortir: Sortir: Sortir: Sortir: Sortir: Sortir: Sortir: Sortir: Sortir: Sortir: Sortir: Sortir: Sortir: Sortir: Sortir: Sortir: Sortir: Sortir: Sortir: Sortir: |