Expression rationnelle

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Regex)
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir régulier et rationnel.

Une expression rationnelle (ou expression régulière par traduction de l'anglais regular expression) 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 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 des langues formelles que sont les langages de l’informatique.

Origine[modifier | modifier le code]

L’origine et la justification mathématique des expressions rationnelles se situent dans la théorie des automates et des langages formels. 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[modifier | modifier le code]

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’interface graphique. Pour cette même raison, un grand nombre d’utilitaires Unix savent utiliser nativement les expressions rationnelles, les plus connus desquels étant (GNU grep, 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.

Notable exception, les shells UNIX (bash, ksh, csh, shetc.) n'utilisent pas ce genre d’expressions dans leurs recherches de fichiers : en effet, les métacaractères reconnus par les shells, bien que servant le même objectif de fournir des motifs de recherche, ne font pas partie de ce qu'on appelle les expressions rationnelles et ne doivent pas être confondus avec elles.

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[modifier | modifier le code]

Une expression rationnelle est une suite de caractères typographiques (qu’on appelle plus simplement « motif » ou « pattern » dans sa forme anglaise) décrivant une chaîne de caractères dans le but de la trouver dans un bloc de texte pour lui appliquer un traitement automatisé, comme un ajout, son remplacement ou sa suppression. 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.

Les variables mises ainsi entre parenthèses peuvent être rappelées ultérieurement par le caractère "$" (comme en PHP). Par exemple si on veut désigner les caractères répondant à la description du contenu des parenthèses du texte "Début([a-z].+)fin" (c'est-à-dire tout type de caractères alphanumériques ou espaces), voici la formule : "Début$1fin". Ceci peut servir à modifier son entourage, par exemple en remplaçant le texte initial par "Début<a>$1</a>fin" (si le texte était "Début milieu fin" il devient "Début<a> milieu </a>fin").

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 (Exception avec le ? rendra le caractère qui le précède optionnel) : toto? correspondant alors à « tot » ou « toto » ;
  • * qui définit un groupe qui existe zéro, 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.

Classe de caractères[modifier | modifier le code]

Une classe de caractères définit un ensemble de caractères. Les langages d'expressions rationnelles permettent de rechercher dans des chaînes, des caractères ou séquences de caractères en se basant sur leur appartenance à certaines classes.

Ces classes de caractères peuvent par la suite être combinées dans la logique de l'expression rationnelle pour effectuer une recherche particulière.

Principes[modifier | modifier le code]

Certaines classes de caractères correspondent à des notions ayant un sens commun (les caractères alphabétiques, les caractères non-alphabétiques, les caractères numériques, les caractères alphanumériques, les caractères grecs.

Une classe de caractères peut se définir de plusieurs manières :

  • avec la liste ou les plages de caractères en faisant partie ;
  • avec la liste ou les plages de caractères n'en faisant pas partie.

Si l'utilisateur peut parfois définir lui-même des classes de caractères, les classes de caractères les plus utilisées sont généralement fournies avec un moteur d'expression rationnelle.

Certaines bibliothèques permettent de faire des opérations sur ces classes de caractères : union et intersection de classes.

Standardisation[modifier | modifier le code]

La bibliothèque POSIX définit des classes au départ pour l'ASCII (lire la section #Classes_de_caract.C3.A8res_POSIX de ce même article), puis, par extensions, pour d'autres formes de codages de caractères, en fonction de la régionalisation du logiciel (locale).

Dans des langages comme le Perl, et Unicode, 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[1] (à ce sujet, lire la section #Expressions_rationnelles_et_Unicode de ce même article).

Classe d'équivalence[modifier | modifier le code]

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.

Utilisation[modifier | modifier le code]

Les classes de caractères présentent l'intérêt de permettre la définition facile et intuitive de concepts intuitifs:

  • Un mot est une séquence de lettres
  • Un identificateur peut se définir comme une séquence de lettres ou encore comme une séquences de caractères alphanumériques

La mise en œuvre des expressions rationnelles permet ensuite de les utiliser de manière simple et efficace.

Théorie[modifier | modifier le code]

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.

Article détaillé : Langage rationnel.

Notations : implémentations et standardisation[modifier | modifier le code]

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.

En particulier, le standard C++2011 reconnaît l'existence de plusieurs moteurs d'expressions rationnelles : ECMAScript : ECMA-262; basic : POSIX basique; extended : POSIX étendu; awk : compatible awk; grep : compatible "grep"; egrep : compatible "extended grep".

Notation usuelle de grep, ed, sed et vi[modifier | modifier le code]

L'utilitaire de recherche GNU 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 à la totalité du reste de l’expression rationnelle (et concerne donc toutes les alternatives représentées).

Si toutefois il apparaît au début d'une classe de caractères, il indique que l'expression rationnelle correspond à tout caractère sauf ceux qui sont compris dans cette liste.

^a trouve "a" en début de ligne mais pas dans "ba".

a[^bcd]e correspond à "afe" mais pas à "ace".

$ 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 à 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 correspondre 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[modifier | modifier le code]

  • chat|chien : correspond aux chaînes de caractères « chat » ou « chien » (et seulement à celles-ci), n'importe où dans le texte (exemple : « chatte »).
  • [cC]hat|[cC]hien : correspond aux chaînes « chat », « Chat », « chien » ou « Chien » (et seulement à celles-ci), n'importe où dans le texte (exemple : « Chat » dans « Chats et chiens »).
  • chu+t : correspond à « chut », « chuut », « chuuut », etc., n’importe où dans le texte.
  • a[ou]+ : correspond à « aou », « ao », « auuu », « aououuuoou », etc., n’importe où dans le texte.
  • peu[xt]? : correspond à « peu », « peux » et « peut » (et seulement à ces chaînes), n’importe où dans le texte. La recherche retourne le texte le plus long possible en cas d’occurrences multiples à la même position.
  • ^[st]ac : représente les chaînes « sac » et « tac » en début de ligne.
  • [st]ac$ : représente les chaînes « sac » et « tac » en fin de ligne ou de texte (par exemple à l'intérieur de « ressac »).
  • ^trax$ : représente la chaîne « trax » seule sur une ligne.

Notation étendue dans vim et emacs[modifier | modifier le code]

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 $nn 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[modifier | modifier le code]

  • 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[modifier | modifier le code]

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 GNU/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 GNU/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 GNU/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 $nn 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, ccchatetc., 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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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

Python[modifier | modifier le code]

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_] (n'équivaut pas à 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[modifier | modifier le code]

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

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[modifier | modifier le code]

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 depuis Perl 5.10[3].

PHP[modifier | modifier le code]

PHP supporte deux formes de notations : la syntaxe POSIX[4] (POSIX 1003.2) et celle, beaucoup plus riche et performante[5], de la bibliothèque PCRE[6] (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.[réf. nécessaire] 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).[réf. nécessaire]

ICU[modifier | modifier le code]

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 plate-forme 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 rationnelles utilisables dans ICU reprennent les caractéristiques des expressions rationnelles 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 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éfini 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 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 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[modifier | modifier le code]

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 codepoint(x) ≤ codepoint(y).
  • L’extension naturelle de ces plages de valeurs Unicode changerait simplement l’exigence sur la plage de valeurs [0..0x7F] en exigence sur la plage étendue à 0..0x1FFFFF.

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

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

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

  • De tels indicateurs n’affectent que les caractères ASCII ; d’autres affectent tous les caractères (et prennent en compte la correspondance de casse soit caractère par caractère dans les implémentations les plus simples, soit au niveau du texte entier dans les implémentations respectant les contraintes de langues, ceci pouvant utiliser les correspondances d’un sous-ensemble d’une version donnée d’Unicode, d’autres pouvant utiliser toutes les correspondances de n’importe quelle version d’Unicode, éventuellement précisable au sein même de l’expression 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 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 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 correspondances simples de casse (caractère par caractère), ou de la catégorie générale du caractère. Dans bien des cas, ces propriétés ne sont pas adaptées à toutes les langues.
  • D’autres propriétés sont informatives, et peuvent faire l’objet de révision d’une version d’Unicode à l’autre : ce sont essentiellement les propriétés définies dans les tables supplémentaires d’Unicode. En particulier elles sont adaptables en fonction de la langue utilisée et désignent par exemple les propriétés de correspondances de casse étendues (traitant le texte dans sa globalité), ou les propriétés d’ordonnancement (collation).
  • Cependant certaines de ces dernières tables ont acquis le statut de standard (en étant intégrées dans des annexes standards du standard Unicode) et sont même utilisées dans la définition de certaines normes), ou bien d’autres propriétés historiques sont encore maintenues mais d’usage non recommandé. Consulter le standard Unicode pour connaître le statut actuel de ces propriétés.

Notes et références[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

Sur les autres projets Wikimedia :

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

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