Expression rationnelle

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

Les expressions rationnelles (en anglais regular expressions dont l'abrégé est regexp ou regex, parfois traduites erronément par 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.

Les expressions rationnelles ont été inventées à 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).

[modifier] Utilisation

Les shells Unix (bash, ksh, csh, sh, 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').

[modifier] 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 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 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… Ils reposent sur la bibliothèque regex, ou la bibliothèque PCRE qui est plus puissante.

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.

[modifier] Expressions rationnelles et Unicode

Les expression rationnelles ont originellement été utilisées avec les caractères ASCII. Beaucoup de moteurs d'expressions rationelles peuvent maintenant gérer l'Unicode. Sur plusieurs points, le jeu de caractères ne fait aucune différence, mais certains problèmes surgissent dans l'extension des expressions régulières pour l'Unicode.

Une question est de savoir quel format de représentation interne d'Unicode est supporté. Tous les moteurs d'expressions régulières en ligne de commande attendent de l'UTF-8, mais pour les bibliothèques, certaines attendent aussi de l'UTF-8, mais d'autres attendent de l'UCS-2 ou UCS-4.

Une deuxième question est de savoir si l'intégralité de la plage des valeurs d'une version d'Unicode est supporté. Beaucoup de moteurs ne supportent que le Basic Multilingual Plane, c'est-à-dire, les caractères encodables sur 16 bits. Seuls peu de 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 implémentations ASCII, les plages de valeurs de la forme [x-y] sont valides quelque soient x et y dans la plage [0x00,0x7F] et codepoint(x) <= codepoint(y). L'extension naturelle de ces plages de valeur Unicode changerait simplement l'exigence sur la plage de valeur [0x00,0x7F] en exigence [0,0x1FFFFF]. Cependant, en pratique ce n'est souvent pas le cas. Certaines implémentations, telle que celle de gawk, ne permettent pas aux plages de valeur de couvrir plusieurs blocs Unicode. Une plage de valeurs telle que [0x61,0x7F] est valide puisque les deux bornes tombent à l'intérieur du bloc Basic Latin, comme [0x0530,0x0560] qui tombe dans le bloc Arménien, mais une plage telle que [0x0061,0x0532] est invalide puisque elle est à cheval sur plusieurs blocs Unicode. 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.

Un autre domaine dans lequel des variations existent est l'interpretation des flags d'insensibilité à la casse. De tels flags n'affectent que les caractères ASCII; d'autres affectent tous les caractères. Certains moteurs ont deux flags 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 Unicodes et les propriété 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{Armenian} valide n'importe quel caractère du bloc Arménien. Similairement, \p{X} valide n'importe quel caractère ayant la propriété générale du caractère X et \P{X} le complément. Par exemple, \p{Lu} valide n'importe quel caractère majuscule (upper-case letter).

[modifier] Théorie

[modifier] Définition

Étant donné un ensemble fini de caractères ou lettres appelé alphabet et noté $\Sigma\,$ , une chaîne (de caractères) est une suite finie (éventuellement vide) de caractères. Par exemple, la chaîne $(a, b, a)$ formée des caractères 'a' puis 'b', puis 'a' 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é $\Sigma^*\,$ .

Les expressions rationnelles (dont il existe une théorie) 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 $\Sigma^*\,$ ) et des opérations sur ces ensembles.

[modifier] Notations

Notons :

L'ensemble vide $\varnothing$ : désigne l'ensemble qui n'a aucun élément (aucune chaîne de caractère n'est dans $\varnothing\,$ ) ;
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 $\Sigma\,$ , désigne la chaîne formée par le caractère a seul.

[modifier] Opérations

Les opérations suivantes sont aussi définies (soient R et S deux sous-ensembles de $\Sigma^*\,$ ) :

La 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"} ;
L'union des ensembles R et S est notée $R \cup S$

[modifier] Propriétés

R ε = εR = R
(RS)T = R(ST)
R U $\varnothing$ = $\varnothing$ U R = R
(R U S) U T = R U (S U T).

Donc $Σ *$ muni de la concaténation a comme élément neutre ε (c'est un monoïde). De même $Σ *$ muni de l'union ensembliste a comme élément neutre $\varnothing$ .

La 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",… }.

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 $\Sigma^*\,$ 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).

$\Sigma^*\,$ 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;

voir aussi théorie des expressions rationnelles

[modifier] Notations

[modifier] bash

Le shell 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.

[modifier] 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 »

« ^[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

« ^trax$ » représente le mot « trax » seul sur une ligne

[modifier] 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.

[modifier] 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 ».

[modifier] PHP

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.

[modifier] 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.

[modifier] 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 caractère doté de la propriété Unicode spécifiée.

\P{UNICODE PROPERTY NAME} Correspond au 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}].

\uhhhh Correspond à un caractère dont la valeur hexadécimale est hhhh.

\Uhhhhhhhh Correspond à un caractère dont la valeur hexadécimale est hhhhhhhh. Exactement huit chiffres héxa doivent être fournis, même si le code point unicode le plus grand est \U0010ffff.

[modifier] Ruby

Un Exemple complet :

[] 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
{m, n} 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 à {0,1}
| alternative: soit ce qui précède soit ce qui suit
() groupe

[modifier] 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 implanté en assembleur Parrot par le module PGE dans l'implantation Parrot de Perl 6 et en Haskell dans l'implantation Pugs. Ces implantations 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.

[modifier] POSIX

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.

[modifier] SQL

MySQL utilise les expressions rationnelles étendues avec les opérateurs REGEXP et NOT REGEXP (voir Appendix G. Regular Expressions).

[modifier] Voir aussi

[modifier] Liens externes

[modifier] Bibliographie

Jeffrey E. F. Friedl : Maîtrise des expressions régulières (O'Reilly) ISBN 2-84177-236-5

Récupérée de « http://fr.wikipedia.org../../../e/x/p/Expression_rationnelle.html »

Catégories : Algorithmique • Langage formel

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Expression rationnelle

Un article de Wikipédia, l'encyclopédie libre.

Sommaire

[modifier] Utilisation

[modifier] Origine

[modifier] Expressions rationnelles et Unicode

[modifier] Théorie

[modifier] Définition

[modifier] Notations

[modifier] Opérations

[modifier] Propriétés

[modifier] Notations

[modifier] bash

[modifier] Exemples

[modifier] Grep

[modifier] Exemples

[modifier] PHP

[modifier] Exemples

[modifier] ICU

[modifier] Ruby

[modifier] Perl

[modifier] POSIX

[modifier] SQL

[modifier] Voir aussi

[modifier] Liens externes

[modifier] Bibliographie

Views

Navigation

Contribuer

Recherche

Autres langues