Expressions rationnelles

Une expression rationnelle ou expression régulière^[1] est en informatique une chaîne de caractères que l’on appelle parfois un motif et qui décrit un ensemble de chaînes de caractères possibles selon une syntaxe précise. Les expressions rationnelles sont issues des théories mathématiques des langages formels des années 1940. Leur puissance à décrire des ensembles réguliers explique qu’elles se retrouvent dans plusieurs domaines scientifiques dans les années d’après-guerre et justifie leur forte adoption en informatique. Les expressions rationnelles sont aujourd’hui utilisées par les informaticiens dans l’édition et le contrôle de texte ainsi que dans la manipulation de langues formelles que sont les langages de l’informatique.

Sommaire 1 Origine 2 Utilisation 3 Principes de base 4 Théorie 5 Notations 5.1 Notation simplifiée des shells Unix ou Linux 5.1.1 Exemples 5.2 Notation usuelle de grep, ed, sed et vi 5.2.1 Exemples 5.3 Notation étendue dans vim et emacs 5.3.1 Exemples 5.4 Expressions rationnelles étendues POSIX 5.4.1 Séquences d’échappement POSIX 5.4.2 Classes de caractères POSIX 5.5 SQL 5.6 Python 5.7 Tcl 5.8 Perl 5.9 PHP 5.10 ICU 6 Expressions rationnelles et Unicode 7 Notes et références 8 Voir aussi 8.1 Articles connexes 8.2 Liens externes 8.3 Bibliographie

Origine

L’origine et la justification mathématique des expressions rationnelles se situent dans la théorie des automates et des langages formels.^{[réf. nécessaire]} Ces champs d’étude couvrent des modèles de calcul (automates) et des façons de décrire et de classifier des langages formels. Un langage formel est ici simplement défini comme un ensemble de chaînes de caractères.

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. Le logicien Stephen Cole Kleene a ensuite décrit ces modèles en termes d’ensembles réguliers, notion qu’il a introduite avec une certaine notation. En 1959, Michael Rabin et Dana Scott proposent le premier traitement mathématique et rigoureux de ces concepts dans un article célèbre qui leur vaut le Prix Turing et qui contribue à faire démarrer l’étude de ces langages.

Ken Thompson a mis en œuvre cette notation dans l’éditeur qed, puis l’éditeur ed sous Unix, et finalement dans grep. Depuis lors, les expressions rationnelles 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… Ils reposent sur la bibliothèque regex, ou la bibliothèque PCRE qui est plus puissante.

Les expressions rationnelles ont été mises en œuvre à une époque où les caractères se confondaient avec les octets. Des variantes existent dans bash, perl, ICU (Unicode, où les caractères sont codés sur 2, 4 ou un nombre variable d’octets).

Utilisation

Initialement créées pour décrire des langages formels, les expressions rationnelles sont naturellement utilisées dans l’interprétation des langages informatiques ; compilateurs et interprètes sont ainsi basés dessus.

La puissance des expressions rationnelles pour la simple manipulation du texte les rend incontournables dans les éditeurs de texte, notamment ceux en mode texte ne disposant pas d’environnement graphique. Pour cette même raison, un grand nombre d’utilitaires Unix savent utiliser nativement les expressions rationnelles. Parmi eux, les shells UNIX (bash, ksh, csh, sh, etc.) utilisent ce genre d’expressions dans leurs recherches de fichiers. D’autres utilitaires (grep, sed), à 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 expressions rationnelles 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.

Principes de base

Une expression rationnelle est une suite de caractères typographiques (qu’on appelle plus simplement « motif » ou « pattern » dans sa forme anglaise) chargée de décrire une chaîne de caractères pour la trouver dans un bloc de texte et lui appliquer un traitement automatisé, comme un ajout, un remplacement ou une suppression. Par exemple l’ensemble de mots « ex-équo, ex-equo, ex-aequo et ex-æquo » peut être condensée 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 quantifieurs les plus répandus sont :

• ? qui définit un groupe qui existe zéro ou une fois : toto? correspondant alors à « tot » ou « toto » ;
• * qui définit un groupe qui existe zéro fois ou une ou plusieurs fois : toto* correspondant à « tot », « toto », « totoo », « totooo », etc. ;
• + qui définit un groupe qui existe une ou plusieurs fois, toto+ correspondant à « toto », « totoo », « totooo », etc.

Théorie

Les expressions rationnelles 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.

Notations

Notation simplifiée des shells Unix ou Linux

Prenons comme exemple le shell libre bash utilisé sous Linux. Les expressions rationnelles de base sous Unix et Linux omettent l’union ensembliste (ici en général appelée « opérateur de choix » ou « alternative »). Les expressions rationnelles sont utilisées pour trouver des accords uniquement sur la totalité du nom des fichiers présents dans les lignes de commande qu’ils cherchent à interpréter et étendre automatiquement avec les noms de fichiers correspondant à l’expression rationnelle (ainsi en précisant l’expression rationnelle la plus simple "a" sur une ligne de commande, ils ne peuvent trouver que le seul fichier nommé "a" mais aucun des fichiers nommés "ab" ou "ba" ou "a.out" par exemple).

Ces shells supportent :

Opérateur standard	Description	Exemple
[ ]	Indique une classe de caractères et fait correspondre un seul des caractères listés entre les crochets [ et ].	[abc] trouve un seul des caractères correspondants, en gras dans "abracadabra", et donc trouve "a" ou "b" ou "c" mais pas "d'.
[^ ]	Un ^ au début d’une classe de caractères entre crochets signifie qu’on considère le complément de cette classe (l’ensemble des caractères qui ne sont pas listés dans la classe). Ailleurs dans la classe de caractères, le ^ est pris littéralement	[^abc] correspond par exemple à "d", mais pas à "a", ni "b", ni "c".
.	Ce joker, qui n’est reconnu comme tel qu’en dehors d’une classe de caractères (où il est considéré littéralement), est une classe de caractères particulière et correspond à un caractère unique quelconque (sauf les caractères de fin de ligne, et les caractères de contrôle en dehors de la tabulation). Il est équivalent à la classe [^\x00-\x08\x0A-\x1F\7F].	c.r trouve une correspondance par exemple dans "carte", "décor", "chrétien" ou "cirer, mais pas pas dans "cri" ni dans "c<saut de ligne>r".
*	Ce quantificateur fait correspondre zéro, une ou plusieurs fois ce qui précède. Si de multiples correspondances existent dans un texte, il trouve d’abord ceux placé en tête du texte et retourne alors la plus grande longueur possible à partir de cette position initiale. L’élément précédent peut être un caractère littéral, ou une séquence d’échappement, ou une classe, ou un joker.	ba* trouve "b" ou "ba", "baa", "baaa", etc.
?	Ce quantificateur fait correspondre zéro ou une seule fois ce qui le précède. Si de multiples correspondances existent dans un texte, il trouve d’abord ceux placé en tête du texte et retourne alors la plus grande longueur possible à partir de cette position initiale. L’élément précédent peut être un caractère littéral, ou une séquence d’échappement, ou une classe, ou un joker.	ba?c trouve soit "bc" soit "bac", mais pas "baac" ni "boc", "bric", "brac", etc.

Exemples

• .ac : représente les chaînes de 3 caractères qui se terminent par « ac ».
• [a-z] : correspond à n’importe quelle lettre minuscule (non-accentuée).
• [^a-z] : correspond à n’importe quel caractère qui n’est pas une lettre minuscule non-accentuée.
• [st]ac : représente entre autres « sac » et « tac ».
• [^f]ac : représente les mots de trois lettres qui se terminent par « ac » et ne commencent pas par « f ».

Notation usuelle de grep, ed, sed et vi

L’utilitaire de recherche grep du monde Unix utilise les mêmes expressions rationnelles , cependant elles sont utilisées pour trouver des occurrences n’importe où dans un texte. Il partage les mêmes fonctionnalités de recherche que l’éditeur le plus simple du monde Unix, ed (qui travaille ligne à ligne sur un fichier texte), et ses extensions comme sa version de traitement automatique en ligne de commande sed, ou l’éditeur plus avancé vi qui étend ed avec un mode d’insertion interactive et le support de l’édition en mode plein écran.

Aussi, ces outils étendent la liste précédente pour fixer des conditions supplémentaires ou faciliter les recherches avec :

Opérateur standard	Description	Exemple
^	Ce prédicat ne correspond à aucun caractère mais fixe une condition nécessaire permettant de trouver un accord sur ce qui le suit en indiquant que ce doit être au début d’une ligne (donc être au début du texte d’entrée ou après un saut de ligne). Il ne peut être considéré ainsi qu’au début de l’expression rationnelle, ailleurs il est considéré littéralement. Il s’applique comme condition qu’à la totalité du reste de l’expression rationnelle (et concerne donc toutes les alternatives représentées).	^a trouve "a" en début de ligne mais pas dans "ba".
$	Ce prédicat ne correspond à aucun caractère mais fixe une condition nécessaire permettant de trouver un accord sur ce qui le précède en indiquant que ce doit être à la fin d’une ligne (donc être à la fin du texte d’entrée ou juste avant un saut de ligne). Il ne peut être considéré ainsi qu’à la fin de l’expression rationnelle, ailleurs il est considéré littéralement. Il s’applique comme condition qu’à la totalité du reste de l’expression rationnelle (et concerne donc toutes les alternatives représentées).	a$ trouve "a" en fin de ligne mais pas dans "ab".
+	Ce quantificateur est l’opérateur + décrit dans la partie théorie du langage et correspond à ce qui le précède, répété au moins une ou plusieurs fois. Si de multiples correspondances existent dans un texte, il trouve d’abord ceux placé en tête du texte et retourne alors la plus grande longueur possible à partir de cette position initiale.	ba+c trouve "bac", ou "baac", "baaac", etc. mais pas "bc"" ni "boc".
|	C’est l’opérateur de choix entre plusieurs alternatives, c’est-à-dire l’union ensembliste. Il peut être combiné autant de fois que nécessaire pour chacune des alternatives possibles. Il fait corrrespondre l’une des expressions placées avant ou après l’opérateur. Ces expressions peuvent éventuellement être vides, et donc (x|) équivaut à x?; toutefois les parenthèses de groupement ne sont pas supportées sans support de la notation étendue supportée par egrep (et non grep), vim (et non le vi classique), ou emacs.	peu|prou|nombres? trouve "peu", "prou", "nombre" ou "nombres".

Exemples

• chat|chien : correspond au mot « chat » ou au mot « chien » (et seulement eux) ; cependant il peut les trouver n’importe où dans le texte, et donc trouvera “chat” dans « chatte ».
• [cC]hat|[cC]hien : correspond à un des mots « chat », « Chat », « chien » ou « Chien » (et seulement eux) ; cependant il peut les trouver n’importe où dans le texte, et donc trouvera “Chat” dans « Chats et chiens ».
• ch+t : correspond à “cht”, “chht”, “chhht”, etc. n’importe où dans le texte.
• a[ou]+ : correspond à « aou », « ao », « auuu », « aououuuoou », etc. n’importe où dans le texte.
• peu[xt]? : correspond à un des mots « peu », « peux » et « peut » (et seulement eux) n’importe où dans le texte. La recherche retourne le plus long possible en cas d’occurrence multiples à la même position.
• ^[st]ac : représente les mots « sac » et « tac » en début de ligne.
• [st]ac$ : représente les mots « sac » (ou « ressac », etc.) et « tac » uniquement s’ils sont en fin de ligne ou de texte.
• ^trax$ : représente le mot « trax » seul sur une ligne.

Notation étendue dans vim et emacs

Des extensions semblables sont utilisées dans l’éditeur alternatif emacs qui utilise un jeu de commandes différent mais reprend les mêmes expressions rationnelles en apportant une notation étendue. Les expressions rationnelles étendues sont maintenant supportées aussi dans vim, la version améliorée de vi.

Opérateur étendu (non POSIX)	Description	Exemple
\{m,n\}	Dans la notation étendue, cela crée un quantificateur borné personnalisé, permettant de faire correspondre exactement de m à n occurrences de ce qui précède, m et n étant deux entiers tels que m < n. Chacun des deux paramètres peut être omis : si le premier paramètre m est omis, il prend la valeur par défaut 0 ; si le second paramètre n est omis, mais la virgule est présente, il est considéré comme infini ; si le second paramètre n est omis ainsi que la virgule séparatrice, il prend la valeur par défaut égale au premier paramètre m.	Voir exemples ci-dessous.
\( \)	Dans la notation étendue, les parenthèses de groupement (dans une séquence d’échappement) permettent de délimiter un ensemble d’alternatives, ou toute sous-expression rationnelle (à l’exception des conditions de début et fin de ligne) pour leur appliquer un quantificateur. De plus, ces parenthèses délimitent un groupe de capture numéroté qui peut être utilisé pour les substitutions (on référence alors les groupes capturés dans la chaîne de substitution avec $n où n est le numéro de groupe de capture entre 1 et 9, la totalité de la chaîne trouvée étant représentée par $&).	Voir exemples ci-dessous.

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 plate-forme (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).

Exemples

• p\(ss\)+t : correspond à « psst », « psssst », « psssssst », etc. n’importe où dans le texte, mais pas à « pst » ni à « pssst », etc. (car ces derniers ont un nombre impair de “s”).

Expressions rationnelles étendues POSIX

Le standard POSIX a cherché à remédier à la prolifération des syntaxes et fonctionnalités, en offrant un standard d’expressions rationnelles 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 rationnelles de Perl.

Les expressions rationnelles étendues POSIX sont souvent supportées dans les utilitaires des distributions Unix et Linux en incluant le drapeau -E dans la ligne de commande d’invocation de ces utilitaires. Toutefois les métacaractères ci-dessus sont maintenant souvent reconnus aussi dans les utilitaires Unix et Linux, la norme POSIX définissant le jeu minimum de métacaractères à supporter.

Les expressions rationnelles étendues (ERE) de POSIX, telles que définies par le standard POSIX 1003.2 de l’IEEE, sont semblables par leur syntaxe aux expressions rationnelles Unix (voir Grep ci-dessus), avec quelques exceptions (pour l’instant ce standard ne fait pas encore l’objet d’une norme internationale ISO, et les normes nationales actuelles peuvent également varier sur la définition exacte de certaines caractéristiques essentielles ou optionnelles).

De plus, certaines barres obliques inversées sont supprimées pour les délimiteurs de groupement utilisés dans les utilitaires Unix ou Linux : \{...\} devient {...} et \(...\) devient (...). Les opérateurs spéciaux { et }, utilisés dans certaines expressions rationnelles d’Unix pour les quantificateurs étendus (bornés) ou comme délimiteurs de groupement sans capture, ne sont pas reconnus directement dans la version POSIX.

Enfin, POSIX ajoute le support pour des plates-formes 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.

Les métacaractères suivants ont été ajoutés à la notation usuelle Unix (celle de grep, ed, sed, vi, et non celle de la notation étendue) :

Opérateur étendu POSIX	Description	Exemple
?	Ce quantificateur, qui n’est reconnu comme tel qu’en dehors d’une classe de caractères (dans une classe il désigne littéralement le caractère correspondant), fait correspondre zéro ou une seule fois l’élément qui le précède. Contrairement à l’opérateur standard, l’élément qui précède peut être aussi un groupe.	ba? correspond à "b" ou "ba".
+	Ce quantificateur, qui n’est reconnu comme tel qu’en dehors d’une classe de caractères (dans une classe il désigne littéralement le caractère correspondant), fait correspondre une ou plusieurs fois l’élément qui le précède. Contrairement à l’opérateur standard, l’élément qui précède peut être aussi un groupe.	ba+ correspond à "ba", "baa", "baaa", etc.
|	L’opérateur de choix (aussi appelé opérateur d’alternation ou d’union d’ensembles) fait correspondre l’expression avant ou après l’opérateur.	abc|def correspond à "abc" ou "def".
( )	Dans la notation étendue, les parenthèses de groupement (utilisées sans recourir à des séquences d’échappement) permettent de délimiter un ensemble d’alternatives, ou toute sous-expression rationnelle (à l’exception des conditions de début et fin de ligne) pour leur appliquer un quantificateur. De plus, ces parenthèses délimitent un groupe de capture numéroté qui peut être utilisé pour les substitutions (on référence alors les groupes capturés dans la chaîne de substitution avec $n où n est le numéro de groupe de capture entre 1 et 9, la totalité de la chaîne trouvée étant représentée par $&).	Voir exemples ci-dessous.

Exemples :

• [hc]+at correspond à "hat", "cat", "hhat", "chat", "hcat", "ccchat", etc. mais pas à "at".
• [hc]?at correspond à "hat", "cat" et "at".
• ch(at|ien) correspond à "chat" ou "chien" (de plus les parenthèses délimitent un groupement de capture de la valeur effective de chaque alternative et permet d’utiliser cette capture pour les opérations de remplacement automatique après une recherche de correspondance utilisant les expressions rationnelles).

Séquences d’échappement POSIX

Puisque 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 \ (qui doit donc être délimitée elle-même de la même façon pour la faire correspondre littéralement).

Les séquences d’échappement suivantes sont ainsi supportées :

Séquence POSIX	Description	Classe équivalente dans le jeu ASCII et la locale "C"
\b	Caractère de contrôle retour arrière (correction). Le caractère reconnu dépend du jeu de caractères codés utilisé sur la plate-forme hôte.	[\x08]
\t	Caractère de contrôle de tabulation horizontale. Le caractère reconnu dépend du jeu de caractères codés utilisé sur la plate-forme hôte.	[\x09]
\n	Caractère de contrôle de saut de ligne. Le caractère reconnu dépend du jeu de caractères codés utilisé sur la plate-forme hôte.	[\x0A]
\v	Caractère de contrôle de tabulation verticale. Le caractère reconnu dépend du jeu de caractères codés utilisé sur la plate-forme hôte.	[\x0B]
\f	Caractère de contrôle de saut de page. Le caractère reconnu dépend du jeu de caractères codés utilisé sur la plate-forme hôte.	[\x0C]
\r	Caractère de contrôle de retour chariot. Le caractère reconnu dépend du jeu de caractères codés utilisé sur la plate-forme hôte.	[\x0D]
\ooo	Caractère littéral désigné par son code octal sur 8 bits (de 0 à 377 en octal), ooo pouvant être exprimé sur 1 à 3 chiffres octaux (entre 0 et 7, ou entre 0 et 3 pour le premier chiffre d’un nombre octal sur 3 chiffres). Le caractère reconnu dépend du jeu de caractères codés utilisé sur la plate-forme hôte.
\xNN	Caractère littéral désigné par son code hexadécimal sur 8 bits, N étant un chiffre hexadécimal (voir ci-dessous la classe [:xdigit:]). Le caractère reconnu dépend du jeu de caractères codés utilisé sur la plate-forme hôte.
\autre	autre caractère considéré littéralement. Pour des raisons de portabilité (et pour éviter des problèmes avec d’autres extensions) cette syntaxe ne devrait être utilisée que pour coder sous forme de séquence d’échappement un caractère à prendre littéralement qui autrement serait l’un des métacaractères reconnus par la norme POSIX. Tout autre caractère que ceux-ci peuvent suivant les cas être interprétés littéralement, auquel cas la séquence d’échappement est inutile, ou pour créer des métacaractères extensions supplémentaires (voir les sections suivantes pour les extensions possibles). Puisque les caractères ( ) [ ] . * ? + | ^ $ sont utilisés comme méta-caractères dans la syntaxe POSIX, il est nécessaire d’introduire une distinction syntaxique pour pouvoir les utiliser dans un sens littéral. Cela se fait en les faisant précéder de '\' (antislash). '\' devient donc lui-même un caractère spécial, qu’on peut lui aussi faire précéder de \, lui-même, pour le prendre en un sens littéral.	Voir notes ci-dessous.

Notes :

• \* : représente uniquement la chaîne « * » (le \ rend littéral le * qui le suit).
• \\* : représente la chaîne vide, ou les chaînes « \ », « \\ », « \\\ » etc. (le premier \ rend le second \ littéral ; * garde son sens de fermeture de Kleene).
• .\.(\(|\)) : représente les chaînes « a.) » et « a.( » et « b.) » et d’autres chaînes de 3 caractères (le premier caractère peut varier et être n’importe quel caractère espace ou graphique, le second caractère doit être un point littéral, le troisième est une des deux parenthèses prises littéralement).

POSIX ne définit aucune façon standard de désigner littéralement des caractères par leur code numérique dans des jeux de caractères à plus de 8 bits (par exemple Unicode). Aussi, nombre d’implémentations de POSIX compatibles Unicode ou ISO 10646 acceptent aussi les séquences \uNNNN (où NNNN désigne sur 4 chiffres hexadécimaux le point de code Unicode d’un caractère du plan multingue de base) ou \UNNNNNNNN (où NNNNNNNN désigne sur 8 chiffres hexadécimaux le point de code Unicode d’un caractère quelconque du jeu).

La norme ne précise pas non plus si les caractères désignés par un code hexadécimal désignent ceux du fichier source, ou si leur code résulte d’un transcodage du jeu de caractères codés d’entrée vers un jeu commun (tel qu’Unicode). Unicode ou le jeu de base ASCII est presque toujours utilisé en tant que codage interne, mais ce n’est pas toujours vrai sur les systèmes à codage basé sur EBCDIC avec les expressions rationnelles POSIX.

De plus, les jeux de caractères sur 8 bits peuvent différer largement notamment dans la zone haute (non ASCII) et l’interprétation des caractères de contrôle (en fonction du système utilisé). Cela constitue un problème d’interopérabilité, qui est résolu le plus souvent en utilisant, dans les utilitaires de traitement de texte, un jeu de caractère interne commun unique basé sur Unicode et un transcodage du jeu de caractères d’entrée vers ce codage interne commun : avec ce système, les expressions rationnelles peuvent devenir indépendantes des jeux de caractères codés utilisés dans différents documents.

Classes de caractères POSIX

Puisque de nombreux sous-ensembles et étendues de caractères sont dépendants de la locale utilisée (par exemple, dans certaines configurations, les lettres sont organisées en abc...zABC...Z, mais comme aAbBcC...zZ dans d’autres), le standard POSIX définit certaines classes ou catégories de caractères comme montré dans la table ci-dessous :

Classe POSIX	Description	Classe équivalente dans le jeu ASCII et la locale "C"
[:cntrl:]	Caractère de contrôle	[\x00-\x1F\x7F]
[:space:]	Espace blanc ou séparateur de ligne ou de paragraphe	[ \t\r\n\v\f]
[:blank:]	Espace blanc ou tabulation non séparateur de ligne ou de paragraphe	[ \t]
[:print:]	Espace simple ou caractère graphique visible (voir ci-dessous la différence avec Perl).	[\x20-\x7E]
[:graph:]	Caractère graphique visible	[\x21-\x7E]
[:punct:]	Caractère de ponctuation	[!"#$%&'()*+,-./:;?@[\\\]_`{|}~]
[:alnum:]	Caractère alphanumérique	[0-9a-zA-Z]
[:digit:]	Chiffre décimal	[0-9]
[:xdigit:]	Chiffre hexadécimal	[0-9a-fA-F]
[:alpha:]	Caractère alphabétique	[a-zA-Z]
[:lower:]	Lettre minuscule	[a-z]
[:upper:]	Lettre capitale	[A-Z]

Par exemple, [[:upper:]ab] fait correspondre un caractère parmi l’ensemble formé par l’union des lettres minuscules « a » et « b » et du sous-ensemble des lettres capitales.

Dans les expressions rationnelles de Perl, la classe [:print:] est définie différemment et correspond à [:graph:] union [:space:] (Perl y inclut donc les tabulations et séparateurs de lignes ou de paragraphes, contrairement à POSIX).

Une classe additionnelle non POSIX, supportée par certains outils, est [:word:] qui est généralement définie comme [:alnum:] plus le soulignement ; cela traduit le fait que dans bien des langages de programmation, ce sont les caractères qui peuvent être utilisés dans un identificateur. L’éditeur de texte Vim distingue encore les classes [:word:] et [:word-head:] (en utilisant aussi les notations supportées \w et \h) puisque dans nombre de langages de programmation, les caractères utilisables au début d’un identificateur ne sont pas les mêmes que ceux utilisables dans les autres positions.

SQL

• MySQL utilise les expressions rationnelles étendues avec les opérateurs REGEXP et NOT REGEXP^[2].

Python

Python utilise des expressions rationnelles basées sur les expressions rationnelles POSIX, avec quelques extensions ou différences.

Les éléments compatibles POSIX sont les suivants :

• [ ] : spécification de classe de caractères (par ex. : [a-z] indique une lettre dans l’intervalle de a à z).
• . : la classe de caractère prédéfinie des caractères graphiques visibles ou blancs ou de contrôle (à l’exclusion des caractères de sauts de ligne).
• * : quantificateur pour zéro, une ou plusieurs occurrences de ce qui précède ; équivaut à {0,}.
• ? : quantificateur pour au plus une occurrence de ce qui précède ; équivaut à {0,1}.
• + : quantificateur pour une ou plusieurs occurrences de ce qui précède ; équivaut à {1,}.
• | : alternative: soit ce qui précède soit ce qui suit.
• ( ) : délimiteurs de groupe (avec capture).
• \autre : un des caractères spéciaux définis ci-dessus, mais interprétés littéralement.
• \t : tabulation horizontale.
• \n : saut de ligne.
• \v : tabulation verticale.
• \f : saut de page.
• \r : retour chariot.
• \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).

Les différences avec POSIX sont les suivantes :

• \b : caractère de retour arrière, 0x08 avec un codage compatible ASCII (comme dans POSIX, mais seulement dans une classe de caractères).
• \b : condition vraie à la limite d’un mot (sauf dans une classe de caractères).

Les extensions non POSIX sont les suivantes :

• \B : condition vraie sauf à la limite d’un mot, l’opposé de \b (non reconnu dans une classe de caractères).
• \w : un caractère lettre ou chiffre ; équivaut à [0-9a-zA-Z] (équivaut à la classe [[:alnum:]] de POSIX).
• \W : un caractère ni lettre, ni chiffre, le complément de \w (équivaut à la classe [^[:alnum:]] de POSIX).
• \s : un caractère espace ; équivaut à[ \t\n\r\f] (équivaut à la classe [[:space:]] de POSIX).
• \S : un caractère non espace, le complément de \s (équivaut à la classe [^[:space:]] de POSIX).
• \d : un chiffre ; équivaut à [0-9] (équivaut à la classe [[:digit:]] de POSIX).
• \D : un caractère non-chiffre, le complément de \d (équivaut à la classe [^[:digit:]] de POSIX).
• {m,n} : quantificateur borné pour au moins m et au plus n occurrences de ce qui précède.

Tcl

Tcl intègre le moteur d’expressions rationnelles développé par Henry Spencer.

Exemples :

• . : n’importe quel caractère unique
• ^ : début d’une chaîne de caractères
• $ : fin d’une chaîne de caractères
• \x : correspond au caractère x
• [a-z] : correspond à n’importe quelle lettre minuscule (non-accentuée)
• * : 0 ou plus de l’atome qui précède
• + : 1 ou plus de l’atome qui précède
•  ? : 0 ou l’atome qui précède
• r1|r2 : alternative entre r1 ou r2

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 rationnelles 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 (Perl-Compatible Regular Expressions, littéralement bibliothèque d’expressions rationnelles 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 rationnelles. 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 rationnelles 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 dans le prochain Perl 5.10.

PHP

PHP supporte deux formes de notation : la syntaxe POSIX^[3] (POSIX 1003.2) et celle, beaucoup plus riche et performante^[4], de la bibliothèque PCRE^[5] (Perl Compatible Regular Expression).

D’autres utilitaires ajoutent souvent leurs propres conventions. Le pouvoir d’expression dépasse alors souvent celui des expressions rationnelles telles que définies ci-dessus, c’est-à-dire qu’ils deviennent capable de décrire des ensembles de chaînes de caractères inaccessibles aux expressions rationnelles « normales » présentées dans les sections précédentes sur les expressions rationnelles POSIX (supportées dans le module regex par défaut de la syntaxe PHP, dans toutes ses versions) et les expressions rationnelles Perl (supportées dans le module pcre optionnel de PHP, présent dans toutes les versions récentes de PHP4 et supérieur).

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 8 bits, 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. Toutefois, même en UTF-8, le problème se pose immédiatement avec la sémantique des expressions rationnelles puisque les caractères ont alors un codage de longueur variable, qui nécessite de complexifier les expressions rationnelles. Des extensions optionnelles de PHP sont donc développées pour créer un nouveau type de donnée pour le texte, afin de faciliter son traitement (et être à terme compatible avec Perl6 qui, comme Haskell, disposera nativement du support intégral d’Unicode). Ainsi, l’intégration d’ICU (ci-dessous) en tant que module d’extension pour PHP a été testée avec succès, et sera intégrée dans PHP6^[6].

ICU

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

Les expressions rationnelles utilisables dans ICU reprennent les caractéristiques des expressions rationnelles de Perl, mais les complète 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 rationnelles 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 rationnelles 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 8 bits (par exemple UTF-16) puisque le codage effectif de ces jeux sous forme de séquences d’octets dépend de la plate-forme utilisée pour le traitement (ordre de stockage des octets dans un mot de plus de 8 bits).

ICU résout cela en adoptant un traitement utilisant en interne un jeu unique défini sur 32 bits 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 ^[7], directement dans les expressions rationnelles, ou dans l’expression rationnelle 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éfinit comme [\t\n\f\r\p{Z}].

Les expressions rationnelles 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 rationnelles 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 16 bits).

ICU est une librairie 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 rationnelles 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 rationnelles 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 rationnelles désignent chacune un ensemble non ordonné de textes, et les accords trouvés dans un texte source peuvent être eux aussi à des positions quelconque 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 rationnelles et Unicode

Les expressions rationnelles ont originellement été utilisées avec les caractères ASCII. Beaucoup de moteurs d’expressions rationnelles 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 rationnelles pour Unicode.

Une question est de savoir quel format de représentation interne d’Unicode est supporté. Tous les moteurs d’expressions rationnelles 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 {{{1}}}.
• 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 le mappage 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 mappages d’un sous-ensemble d’une version donnée d’Unicode, d’autres pouvant utiliser tous les mappages de n’importe quelle version d’Unicode, éventuellement précisable au sein même de l’expression rationnelle).
• 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 quel 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 rationnelle 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 mappages 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 mappages de casse étendus (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.

Notes et références

Voir aussi

Articles connexes

• Théorie des expressions rationnelles
• Filtrage par motif
• Algèbre de Kleene
• EBNF

Liens externes

• (fr) Les expressions rationnelles en php
• (en) Sur les expressions rationnelles
• (en) Regex++
• (fr) Tester les expressions rationnelles

Bibliographie

• Bernard Desgraupes, Introduction aux expressions rationnelles, Vuibert, Paris, septembre 2001, broché, 248 p. (ISBN 2-7117-8680-3) 
• Jeffrey E. F. Friedl (trad. Laurent Dami), Maîtrise des expressions rationnelles [« Mastering regular expressions »], O'Reilly, Paris, avril 2001 (réimpr. 2003), broché, 364 p. (ISBN 2841771261) 

Informatique théorique
Théorie du calcul	Calculabilité Décidabilité et indécidabilité • Ensemble récursif • Problème de l'arrêt • Récursivement énumérable Modèle de calcul Automate fini • Automate cellulaire • Machine de Turing • Thèse de Church Modes de calcul Concurrence • Parallèlisme • Théorie de l'ordonnancement Mesure et échelle de complexité Réduction polynomiale • Problème NP-complet
Logique, syntaxe et sémantique	Logique mathématique Assistant de preuve • Calcul des prédicats • Correspondance de Curry-Howard • Fonction récursive • Lambda-calcul • Théorème d'incomplétude de Gödel • Théorie des types Grammaire formelle et systèmes de réécriture Compilation • Expression rationnelle • Grammaire formelle • Langage rationnel • Théorie des langages Sémantique Sémantique des langages de programmation • Sémantique dénotationnelle • Sémantique axiomatique • Sémantique opérationnelle Spécifier, vérifier et concevoir des programmes Interprétation abstraite • Méthodes formelles • Model checking
Algorithmique, complexité et mathématiques discrètes	Algorithmique Algorithme génétique • Algorithme glouton • Algorithme probabiliste • Complexité algorithmique • Diviser pour régner • Heuristique • Programmation dynamique Problèmes et algorithmes numériques Algorithme du simplexe • Géométrie algorithmique • Algorithme d'Euclide • Test de primalité Problèmes et algorithmes non-numériques Algorithmes de la théorie des graphes • Arbre (informatique) • Liste (informatique) • Table de hachage • Tas (informatique) Théorie des graphes Coloration de graphe • Problèmes de cheminement Recherche opérationnelle Optimisation • Optimisation combinatoire • Théorie de l'ordonnancement Données et codage Codage • Codage de l'information • Compression de données • Cryptage • Cryptanalyse • Cryptographie • Théorie de l'information

• Portail de l’informatique