Expression régulière
Les expressions régulières, aussi appelées expressions rationnelles — traductions controversées de l'anglais regular expressions (abrégé regexp) — 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.
Une erreur fréquente est de croire que les shells UNIX (bash,ksh,csh,etc.) utilisent nativement ces expressions. Mais on peut utiliser ces shells pour lancer certaines commandes regexp (awk,perl,sed,etc.) et il faut alors 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'). Les expressions natives des shells s'appellent en anglais "globs" ou "wildcards".
L'origine et la justification mathématique des expressions régulières 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. Un mathématicien, 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. 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 régulières ont été largement utilisées dans les utilitaires ainsi que dans les langages de programmations 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 régulières 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.
| Sommaire |
Les expressions régulières en théorie des langages formels
On considère un ensemble fini de lettres, ou alphabet, Σ. L'ensemble des chaînes de caractères (souvent appelées mots ou phrases) que l'on peut former avec ces lettres est noté Σ*.
Les expressions régulières 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 Σ*) et des opérations sur ces ensembles.
Les constantes suivantes sont définies :
- ensemble vide (noté ∅ ) : désigne l'ensemble vide (aucune chaîne de caractère n'est dans ∅) ;
- chaîne vide (notée ε ) : désigne l'ensemble {ε} qui contient un unique élément, la chaîne vide ε ;
- caractère littéral (noté a) : lorsque a est un élément de Σ, désigne l'ensemble {"a"} qui est la chaîne formée par le caractère a seul.
Les opérations suivantes sont aussi définies (soient R et S deux ensembles) :
- 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*): 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 pose que l'étoile de Kleene a la plus haute priorité, suivie par la concaténation puis par l'union. Par exemple, (ab)c peut s'écrire abc et a U (b(c*)) peut s'écrire a U bc*.
Parfois on inclut aussi l'opérateur '+' défini comme suit: R+ est le plus petit ensemble contenant R et clos pour l'opération de concaténation. Cet opérateur peut en fait se définir à partir des autres: R+ = R R*.
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 Σ* 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).
Σ* muni des opérateurs décrits ci-dessus forme une algèbre de Kleene.
Exemples
- 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;
- (ab*)* est une autre façon de décrire le même ensemble;
- 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;
- ( bb U a(bb)*aa U a(bb)*(ab U ba)(bb)*(ab U ba) )* désigne l'ensemble des chaînes formées uniquement de 'a' et de 'b', avec un nombre pair de 'a' et un nombre de 'b' divisible par trois.
Les expressions régulières sont capables de décrire exactement les mêmes langages que ceux exprimés par les automates finis (déterministes ou non) : ces langages sont appelés langages réguliers.
Il y a cependant une différence significative entre ces deux approches en termes de compacité de représentation : certaines familles de langages réguliers nécessitent pour leur description une famille d'automates dont la taille croît exponentiellement, alors que la taille des expressions régulières nécessaires ne croît que linéairement.
On peut également s'intéresser au pouvoir d'expression à l'intérieur du formalisme. Comme l'exemple ci-dessus le montre, des expressions régulières différentes peuvent désigner le même langage: le formalisme est redondant. Dans quelle mesure cette redondance peut-elle être éliminée ? Pouvons-nous trouver un sous-ensemble d'expressions régulières intéressant et toujours capable d'engendrer tous les langages réguliers ? L'étoile de Kleene et la concaténation ne peuvent pas être entièrement omises des opérations de base, mais peut-être peut-on restreindre leur usage. Ce problème est en fait d'une difficulté surprenante. Aussi simples que soient les expressions régulières, il n'existe pas de méthode systématique pour les ramener à une forme normale. Il faut donc avoir recours à d'autres techniques ; on arrive ainsi au problème de degré d'étoile.
Les expressions régulières sous Unix
Les expressions régulières 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 (xxx 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
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.
Exemple
- "\*" : 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 d'étoile 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 régulières 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 régulières « normales » présentées ici.
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érateur d'expressions régulières 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 régulières 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 régulières 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 fonctionalités ajoutées aux expressions régulières de Perl.
Annexes
Liens externes
- http://www.xrce.xerox.com/competencies/content-analysis/fsCompiler/fssyntax.html -- (en anglais) Xerox regular expressions
- http://www.pcre.org/ -- PCRE : Perl Compatible Regular Expressions
- Labo-Linux: Regex Les expressions régulières
Bibliographie
- Jeffrey E. F. Friedl : Maîtrise des expressions régulières (O'Reilly) ISBN 2-84177-236-5
| Image manquante Wikimedal.png | Cet article a été défini comme article de qualité faisant honneur à l’encyclopédie Wikipédia libre, universelle et gratuite. Pour toute information complémentaire, consulter sa page de discussion ainsi que celle de la liste des articles de qualité. |