Un article de Wikipedia.y-project.com.
Les expressions rationnelles (en anglais regular expressions dont l'abrégé est regexp ou regex, et dont une mauvaise traduction fréquemment employée est expressions régulières) sont une famille de notations compactes et puissantes pour décrire certains ensembles de chaînes de caractères. Ces notations sont utilisées par plusieurs éditeurs de texte et utilitaires (particulièrement sous Unix), par exemple Vim, Emacs, sed et awk, pour parcourir de façon automatique des textes à la recherche de morceaux de texte ayant certaines formes, et éventuellement remplacer ces morceaux de texte par d'autres.
[] Implémentations
Les expressions rationnelles ont été inventées à une époque où les caractères se confondaient avec les octets.
Outre les variantes propres à chaque langage (grep perl et bash), de nouvelles formes d'expressions pourraient apparaître avec unicode.
Des expressions rationnelles pour unicode semblent exister dans ICU.
Aujourd'hui, avec internet et des langages modernes tels que java et le futur Python 3.0, Unicode est de plus en plus utilisé. Dans ce système, les caractères sont codés sur deux, quatre, ou un nombre variable d'octet. Or peu de bibliothèques d'expressions rationnelles sont orientées Unicode plutôt que octet.
[] Utilisation
Les shells Unix (bash, ksh, csh, etc.) utilisent nativement ce genre d'expressions dans leurs recherches de fichiers. Mais certaines commandes regexp (awk, perl, sed, etc.) utilisent aussi ce genre d'expressions, et il faut alors, pour éviter l'interprétation par le shell, protéger chaque caractère spécial de ces expressions par un \, ou plus simplement protéger l'ensemble par un couple d'apostrophes ('regexp').
[] Origine
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 propose 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 implémenté 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, Python... Une bonne partie d'entre eux reposent sur la bibliothèque regex, créée par Henry Spencer.
Les expressions rationnelles correspondent aux grammaires de type 3 de la hiérarchie de Chomsky ; elles peuvent donc être utilisées pour décrire la morphologie d'une langue.
[] Théorie
On considère un ensemble fini de caractères ou lettres, ou alphabet, <math>\Sigma\,</math>. Une chaîne de caractères (ou chaîne tout court) est une suite finie, éventuellement vide, de caractères. La chaîne formée de 'a' puis 'a', puis 'b' se note "aba".
L'ensemble des chaînes de caractères (aussi appelées mots ou phrases) que l'on peut former avec ces lettres est noté <math>\Sigma^*\,</math>.
Les expressions rationnelles sont composées de constantes et d'opérateurs qui décrivent des ensembles de chaînes de caractères (c'est-à-dire des parties de <math>\Sigma^*\,</math>) et des opérations sur ces ensembles.
[] Notations théoriques
Les constantes suivantes sont définies :
- ensemble vide (noté <math>\,\varnothing</math>) : désigne l'ensemble qui n'a aucun élément (aucune chaîne de caractère n'est dans <math>\varnothing\,</math>) ;
- mot vide ou chaîne vide (noté ? ) : désigne la chaîne de caractères qui ne contient aucune lettre ;
- caractère littéral (noté a) : lorsque a est un élément de <math>\Sigma\,</math>, désigne la chaîne formée par le caractère a seul.
Les opérations suivantes sont aussi définies (soient R et S deux sous-ensembles de <math>\Sigma^*\,</math>) :
- concaténation (notée RS) : désigne l'ensemble { ?? où ? appartient à R et ? appartient à S }. Par exemple {"ab", "c"}{"d", "ef"} = {"abd", "abef", "cd", "cef"} ;
- union ensembliste (notée R U S) : désigne l'union des ensembles R et S;
- fermeture de Kleene (notée R*, aussi appelée étoile de Kleene): désigne le plus petit ensemble qui contient R comme sous-ensemble, ? comme élément, et est clos pour l'opération de concaténation. En d'autres termes, c'est l'ensemble de toutes les chaînes de caractères qui peuvent être formées en concaténant zéro, une ou plusieurs chaînes de R. Par exemple, {"ab", "c"}* = {?, "ab", "c", "abab", "abc", "cab", "cc", "ababab", ... }.
On remarque que R ? = ?R = R, que (RS)T = R(ST), que R U <math>\,\varnothing</math> = <math>\,\varnothing</math> U R = R et que (R U S) U T = R U (S U T). Donc <math>\Sigma^*\,</math> muni de la concaténation avec comme élément neutre ? est un monoïde de même que <math>\Sigma^*\,</math> muni de l'union ensembliste avec comme élément neutre <math>\,\varnothing</math>.
Pour éviter le recours excessif aux parenthèses, on décide d'omettre les parenthèses résultant de l'associativité et de donner la plus haute priorité à l'étoile de Kleene, suivie de la concaténation, puis de l'union. Par exemple, (ab)c s'écrira abc et a U (b(c*)) s'écrira a U bc*. On omet aussi les accolades autour des singletons et les guillemets autour des mots.
On ajoute aussi la fermeture '+' définie comme suit: R+ est le plus petit ensemble contenant R et clos pour l'opération de concaténation. '+' se définit à partir des autres opérations par R+ = R R*. Informellement, la fermeture '+' est la fermeture de Kleene dans lequel on ne prend pas ?.
Un autre opérateur redondant souvent inclus est l'opérateur complément noté ~, tel que ~R désigne l'ensemble des chaînes de caractères de <math>\Sigma^*\,</math> qui ne sont pas dans R. (Pour montrer que ~ est redondant, il faut faire un détour, par exemple par la théorie des automates déterministes à états finis).
<math>\Sigma^*\,</math> muni des opérateurs décrits ci-dessus forme une algèbre de Kleene.
- a U b* désigne {"a", ?, "b", "bb", "bbb", ...};
- (a U b)* désigne l'ensemble des chaînes qui ne contiennent que des 'a' et des 'b', y compris la chaîne vide ?;
- (a* b*)* désigne exactement le même ensemble (que des 'a' et des 'b', le mot vide compris);
- (ab*)* décrit tous les mots ne contenant que des 'a' et des 'b', commençant par 'a', y compris la chaîne vide ?;
- ab*(c U ?) désigne l'ensemble des chaînes qui commencent par 'a', suivi de zéro ou plus 'b', et se terminent éventuellement par un 'c' optionnel;
[] notation dans les langages de programmation
[] Bases en bash
Les expressions rationnelles de base sous Unix omettent l'union ensembliste (ici en général appelée "opérateur de choix" ou "alternative") et ajoutent :
- '.' : un joker, qui représente un caractère unique quelconque (sauf caractères de contrôle et fin de ligne).
- '[ ]' : des classes de caractères entre crochets [ ].
- '^' : 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 dans la classe).
- '^' et '$' : représentent respectivement un début et une fin de ligne.
[] Exemples
- ".ac" représente les mots de trois lettres 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"
- "^[st]ac" représente les mots "sac" et "tac" en début de ligne
- "[st]ac$" représente les mots "sac" et "tac" en fin de ligne
- "^trac$" représente le mot "trac" seul sur une ligne
[] Grep
L'utilitaire egrep du monde Unix étend cette liste avec :
- '+' : spécificateur de quantité: est l'opérateur '+' décrit dans la partie théorie du langage et exprime "ce qui précède, répété une fois ou plus".
- '*' : spécificateur de quantité: "zéro, une fois ou plus ce qui précède."
- '?' : spécificateur de quantité: "zéro ou une fois ce qui précède".
- '|' : l'opérateur de choix, c'est-à-dire l'union ensembliste.
[] Exemples
- "chat|chien" : représente les mots "chat" et "chien" (et seulement eux).
- "([cC]hat|[cC]hien)" : représente "chat", "Chat", "chien" et "Chien".
- "ch+t" : représente "cht", "chht", "chhht", etc.
- "a[ou]+" : représente "aou", "ao", "auuu", "aououuuoou" etc.
- "peu[xt]?" : représente "peu", "peux" et "peut".
Puisque les caractères '(', ')', '[', ']', '.', '*', '?', '+', '|', '^' et '$' sont utilisés comme caractères spéciaux, 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.
[] Exemples
- "\*" : représente uniquement la chaîne "*" ("\" rend "*" littéral)
- "\\*" : représente 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.
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 ici.
[] ICU
D'après: http://icu.sourceforge.net/userguide/regexp.html :
ICU a les capacités suivantes:
\N{UNICODE CHARACTER NAME} Correspond au caractère nommé
\p{UNICODE PROPERTY NAME} Correspond au carctère doté de la propriété Unicode spécifiée.
\P{UNICODE PROPERTY NAME} Correspond au carctè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].
\uhhhh Correspond à un caractère dont la valeur hexa est hhhh.
\Uhhhhhhhh Correspond à un caractère dont la valeur hexa est hhhhhhhh. Exactement huit chiffres
héxa doivent être fournis, même si le code point unicode le plus grand est \U0010ffff.
[] Un Exemple complet le cas de Ruby
- [] spécification d'intervalle (par ex: [a-z] indique une lettre dans l'intervalle a à z)
- \w lettre ou chiffre; équivaut à [0-9A-Za-z]
- \W ni lettre ni chiffre
- \s caractère espace; équivaut à[ \t\n\r\f]
- \S caractère non espace
- \d chiffre; équivaut à [0-9]
- \D non-chiffre
- \b backspace (0x08) (seulement dans un intervalle)
- \b limite de mot (sauf dans un intervalle)
- \B limite autre que de mot
- '*' zero, 1 ou n occurrences de ce qui précède
- + 1 ou n occurrences de ce qui précède
- au moins m et au plus n occurrences de ce qui précède
- ? Au plus une occurrence de ce qui précède; équivaut à
- | alternative: soit ce qui précède soit ce qui suit
- () groupe
Perl, par exemple, 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.
La norme POSIX a cherché à remédier à la prolifération des syntaxes et fonctionalité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.
[] Annexes
[] Liens externes
[] Bibliographie
DernierMirror
Le Texte ci-dessus est disponible sous GNU Free Documentation License.
La source est wikipedia http://fr.wikipedia.org/wiki/expression rationnelle
