Expressions régulières

De Ensiwiki
Aller à : navigation, rechercher
Wait, forgot to escape a space. Wheeeeee[taptaptap]eeeeee.

De quoi ça parle

Les expressions régulières, tout le monde en a entendu parlé un jour, mais ça fait partie des features que personne n'ose vraiment aborder en profondeur.

Beaucoup de problèmes de la "vie de tous les jours" consistent, de près ou de loin, à traiter du texte : supprimer une ligne sur deux après un mauvais copier-coller, indenter correctement un paragraphe, remplacer un nom de variable par une autre, etc. Les expressions régulières ("regexps" ou RE en abrégé pour regular expressions).

Où et comment s'en servir

De nombreux outils et langages ont un support pour les expressions régulières. Elles sont au cœur d'outils comme grep ou sed, sont intimement liées à Perl, mais il existe plusieurs bibliothèques, dont la libc POSIX et la bibliothèque PCRE (Perl-Compatible Regular Expressions) qui permettent à des langages comme PHP ou C d'utiliser ces fonctions. De nombreux éditeurs de texte (au moins Vim et Emacs) permettent d'utiliser les expressions régulières pour généraliser les fonctions "rechercher" ou "rechercher et remplacer".

A noter : à l'exception de quelques concepts avancés, les notions sont communes à toutes les implémentations, mais la syntaxe employée diffère parfois un peu. Sous unixoïde, on rencontre entre autres les deux syntaxes normalisées par POSIX : les expressions régulières simples (p.ex. sed, grep, par défaut) et les expressions régulières étendues (p.ex. awk, egrep), sur lesquelles sont parfois (souvent ?) construites des extensions diverses. Mais des poids lourds tels que Perl ou Emacs emploient leur propre langage d'expressions régulières.

J'utiliserai la syntaxe de Perl, qui est aussi celle des PCRE. Pour les différences avec les regexps de Vim, j'essaierai de faire un petit récapitulatif.

NB : dans un premier temps, l'article sera assez spécifique à Perl, par exemple je ne sais pas si /x est supporté dans les PCRE... promis je vais vérifier.

Opérations avec les regexps

L'opération de base est le test : est-ce qu'une ligne correspond à un "motif" donné ?

Exemples :

  • est-ce que la ligne contient "chat" ?
  • est-ce que la ligne contient "chat" puis "chien" ?
  • est-ce que la ligne contient le mot "chat" (c'est différent du premier cas, celui-ci contenant les cas du genre "achat", "chaton", etc)
  • est-ce que la ligne contient des mots apparaissant plus d'une fois
  • etc

Une autre opération est la substitution, qui consiste à transformer une ligne en une autre.

Exemples :

  • remplacer toutes les occurrences de "bleu" par "rouge"
  • supprimer toutes les balises HTML d'un texte (pour faire simple, tout texte qui se trouve entre '<' et le '>' le plus proche)
  • éliminer les doublons, c'est à dire remplacer "comment vas vas tu ?" en "comment vas tu ?"
  • etc

Chercher du texte simple

Reprenons le premier exemple de tout a l'heure : cherchons si une chaîne contient "chat", au sens le plus large possible (c'est à dire, dans un texte, les 4 lettres c, h, a, t). La regexp décrivant cette recherche se note : /chat/. Les slashes ne font pas partie de la regexp, ils agissent comme délimiteur, comme les guillemets pour une chaîne de caractères.

À /chat/, correspondent les chaînes : "Je veux un chat !", "Bel achat...", "Joli chaton", mais pas "wouf", "chaaat" ou "Chat" (à cause de la majuscule).

Si on veut rendre la correspondance insensible à la casse (c'est à dire ne pas faire de différence entre majuscules et minuscules), il suffit d'ajouter le modificateur /i (case Insensitive) à la regexp :

À /chat/i correspondent les chaînes "chat", "Chat", "chaton", "chAT", etc.

Bien sûr, un problème se pose si on cherche un motif contenant un slash. Pour chercher "1/2" par exemple, il faut échapper le slash en le faisant précéder d'un anti-slash. La regexp devient /1\/2/. D'autres caractères ont une signification spéciale dans les regexps, il faut donc les échapper, ce sont : / \ | . ^ $ ( ) [ et ] . De plus les mêmes "raccourcis" qu'en C sont disponibles : pour chercher une tabulation, on écrit \t.

Alternation, classes de caractères

Restons dans les animaux : supposons qu'on veuille tester les chaînes contenant "chien" ou "chat". On peut utiliser l'alternation, notée | : la regexp se note donc /chien|chat/.

L'alternation a une priorité très faible, on peut être amené à employer des parenthèses. Par exemple pour chercher "chi" suivi de "ot" ou "en", on écrit /chi(ot|en)/.

Pour chercher des voyelles, on peut utiliser l'alternation, avec /a|e|i|o|u|y/, mais c'est plutôt laborieux ; lorsqu'il s'agit d'alternations d'un caractère, on peut utiliser des classes de caractères : /[aeiouy]/.

Pour complémenter une classe, on met un ^ après le premier [ : /[^aeiouy]/ est tout ce qui n'est pas une voyelle (attention, ça inclut les caractères qui ne sont pas de lettres).

Lorsque les caractères sont contigus, le tiret sert de raccourci : /[abcdef]/ s'écrit /[a-f]/. De plus, certaines classes de caractères ont un nom particulier. Ainsi, pour chercher des nombres, au lieu d'écrire /[0-9]/, on peut écrire /[:digit:]/ ou /\d/ :

Classes de caractères
Description Extension Syntaxe longue Syntaxe courte Complémentaire
Nombres [0-9] [:digit:] \d \D
Element de mot [A-Za-z0-9_] [:word:] \w \W
Caractère "blanc" [ \t\n] [:space:] \s \S

Du coup, si on a besoin de chercher "n'importe quoi, même \n", on peut écrire [\d\D].

Ancres

Prenons un exemple concret : cherchons les chaînes qui commencent par "rofl" : "rofl", "roflerie", "roflcopter" mais pas "ah, mais rofl !". On utilise l'ancre de début de chaîne notée ^ : /^rofl/. '^' est un métacaractère qui ne correspond pas à un caractère dans la chaîne (on dit qu'il est de longueur nulle).

De la même manière, $ correspond à la fin de la chaîne. En combinant, on peut construire des RE comme "exactement cette chaîne" : /^chat$/ ne correspondra qu'à "chat".

Il y a une autre ancre utile, c'est \b pour "word boundary" : c'est une limite entre mot et non-mot ("mot" doit être pris au sens \w), autrement dit, il y a un \b "virtuel" entre chaque \w et chaque \W. Ça nous permet de décrire notre exemple "le mot chat, mais pas achat, chaton, etc" : /\bchat\b/.

/s et /m

Il existe 2 modificateurs qui permettent de contrôler la notion de "nouvelle ligne". Bien souvent, on utilise les regexps pour traiter du texte ligne-par-ligne : la chaîne à traiter n'a qu'un début de ligne (auquel ^ fait référence), qu'une fin de ligne (à laquelle $ fait référence), et ne contient pas de \n (la notion de "tout caractère sauf \n" est donc parfaite pour .).

Dans certains cas on peut vouloir traiter un texte de plusieurs lignes comme une seule chaîne. On voudrait donc que ^ corresponde au début d'une ligne, et $ à la fin d'une ligne. On obtient ce fonctionnement avec /m (Multiple lines).

De plus, un autre fonctionnement est parfois désirable, c'est de transformer . pour qu'il corresponde à n'importe quoi. Le modificateur /s (Single line) permet ceci. Par exemple, on utilise /s pour traiter des données binaires, où \n est aussi "commun" que n'importe quel autre caractère (il n'a pas la sémantique de fin de ligne).

Quantificateurs

Jusqu'ici, les regexps écrites ont toujours eu une longueur fixe. On peut "quantifier" un élément de regexp pour préciser combien de fois il faut le faire correspondre dans la chaîne. Les quantificateurs sont :

Quantificateurs
Métacaractère Plage Forme équivalente
? 0 ou 1 /x?/ == /|x/
+ 1 ou plus /x+/ == /x|xx|xxx|xxxx|.../
* 0 ou plus /x*/ == /|x|xx|xxx|xxxx|.../
{m,n} entre m et n (inclus) /x{2,4}/ == /xx|xxx|xxxx/

On peut ainsi chercher les nombres entiers : /\d+/, les mots : /\w+/, mais aussi les nombres flottants, /(+|-)?\d+(\.\d+)?(e\d+)?f/. Tout ça ne devient pas trop lisible. Pour améliorer la lisibilité, on peut utiliser le modificateur /x. Avec /x, tout les espaces sont ignorés (pour chercher la caractère espace ' ' il faut donc l'échapper), et on peut commenter (de # jusqu'à la fin de ligne. Attention, on ne peut pas mettre '/' dans les commentaires car il terminerait l'expression régulière).

/(+|-)?     # signe
\d+         # mantisse
(\.\d+)?    # partie décimale de la mantisse
(e\d+)?     # exposant
f           # 'f' terminal
/x

Capture

On peut se servir des regexps pour extraire des information depuis le texte. Par exemple, dans le cas des flottants, si on écrit un analyseur lexical, on aimerait récupérer le signe, la mantisse et l'exposant dans des variables séparées.

Partons d'un cas plus simple : on reconnait les "affectations", d'une manière très simple : "foo=3", "bar = 54", "rofl= 0". La regexp employée est /\w+\s*=\s*\d+/. Pour récupérer le nom de variable et le nombre affecté, rien de plus simple, il suffit de parenthéser l'expression à capturer : la regexp devient /(\w+)\s*=\s*(\d+)/. On récupère le résultat dans les variables $1 et $2.

Reprenons l'exemple des flottants, en mettant des parenthèses autour de ce qu'on veut capturer :

/(+|-)?
(\d+)
(\.(\d+))?
(e(\d+))?
f
/x

Plusieurs remarques :

  • tout d'abord, on a du rajouter des parenthèses autour des "endroits intéressants" (ici le signe et les suites de chiffres)
  • ensuite, il y a des parenthèses imbriquées, cela complique la numérotation : en fait, chaque paire de parenthèses est numérotée par sa parenthèse gauche :
 (+|-)?(\d+)(\.(\d+))?(e(\d+))?f
 1...1 2...23.......3 5......5
               4...4    6...6

  • enfin, de nombreuses parenthèses ne nous intéressent pas. Dans cet exemple, seul le contenu des parenthèses 1, 2, 4 et 6 est pertinent.

Pour résoudre ce problème, 2 options sont possibles : soit on fait comme s'il n'existait pas et on oublie $3 et $5, soit on utilise des parenthèses non capturantes pour ces couples-là. Les parenthèses non capturantes sont uniquement là pour délimiter des sections de regexp (ici, pour faire agir ? sur un grand pan de regexp et non uniquement sur \d+), sans affecter de variable. Les parenthèses non capturantes se notent (?: ). La regexp ainsi écrite devient :

/(+|-)?
(\d+)
(?:\.(\d+))?
(?:e(\d+))?
f
/x

La regexp devient imposante, mais on obtient en sortie exactement ce qu'on désire.

$`, $& et $'

(aussi appelés respectivement $PREMATCH, $MATCH et $POSTMATCH, mais bon).

On peut également récupérer le résultat de "toute la regexp", comme si elle était englobée dans les parenthèses les plus extérieures, dans $&. $` et $' correspondent aux parties de la chaîne avant et après $&.

Concrètement, si on fait correspondre "cette phrase contient 1 nombre et plusieurs mots" à /(\d+) nombre(s?)/, on aura en sortie :

  • $1 = 1
  • $2 = ""
  • $` = "cette phrase contient "
  • $& = "1 nombre"
  • $' = " et plusieurs mots"

Substitution

Pour transformer une chaîne en une autre, on utilise s///. La syntaxe est s/regexp/remplacement/modificateurs.

Prenons un exemple concret : on veut convertir une série d'affectations (voir ci-dessus) en pseudo-code : transformer "x = 4" en "4 -> x". Le code correspondant est :

s/(\w+)\s*=\s*(\d+)/$2 -> $1/

Il y a en fait 3 étapes dans l'exécution d'une substitution :

  • passage de la chaîne d'entrée dans la regexp de gauche (donc affectation aux variables $1, $2, etc)
  • remplacement des variables $1, $2, etc par leurs valeurs dans la partie de droite
  • remplacement de $& par la partie de droite

Substitutions multiples : /g

Par défaut, s/// ne réalise qu'une substitution (par exemple s/a/b/ sur "aaa" donnera "baa"). Pour réaliser des substitutions multiples, on utilise le modificateur /g : s/a/b/g.

Versions non-gourmandes

Prenons un exemple classique : on veut traiter du texte contenu dans un document HTML. Une approche simpliste est de supprimer toutes les balises (ou mieux, de les remplacer par un espace, pour ne pas "coller" deux mots qui ne l'étaient pas :

s/<.*>/ /g

Pourtant, en pratique, ça ne marche pas ! Sur le texte "<h1>Kikoo !</h1>lol... ASV ?", le texte "avalé" s'étale du premier '<' au dernier '>'. C'est en fait dû au fonctionnement interne du moteur d'expressions régulières, qui cherche toujours à aller le plus loin possible.

Pour pallier à cet inconvénient, il existe des quantificateurs "light", qui fonctionnent comme les quantificateurs normaux, au détail près qu'ils cherchent à avaler le moins possible. Ils s'écrivent avec un point d'interrogation après le signe habituel. Ainsi + devient +? (1 ou plusieurs fois, mais le moins possible), *?, ?? (0 ou 1 avec une préférence pour 0), mais aussi {n,m}?.

L'expression régulière correcte est donc :

s/<.*?>/ /g

Backreferences

Jusqu'ici, les expressions régulières correspondaient au modèle théorique (cf cours de Théorie des Langages de 1A) : les seules opérations réalisées (hors capture substitution) se modélisent grâce à un automate fini : on peut déterminer si un mot de longueur n correspond à une expression régulière en un temps O(n) et avec un encombrement mémoire O(1). En effet, à aucun moment la notion de mémoire n'apparaît !

En pratique, on est souvent amenés à rechercher des motifs plus complexes. Dans les premiers exemples, on avait évoqué l'élimination de doublons, qui nécessite une syntaxe particulière. Pour chercher 2 mots identiques séparés par un espace, on écrira par exemple l'expression régulière suivante :

/\b(\w+) \1\b/

\1 est une backreference, c'est à dire une référence vers une partie précédente de la regexp. Plus précisément, \1 correspond à "ce qu'il y a en ce moment dans $1".

Attention à ne pas confondre \1 et $1, ce sont deux choses différentes :

  • dans une regexp (y compris à gauche de s///), $1 est interpolé (remplacé par le contenu précédent de $1 avant même le lancement du moteur de RE) (cela peut changer selon le langage utilisé : $1 peut aussi correspondre à '$', '1' ou à 'fin de ligne', 1, c'est à dire souvent pas grand chose !). \1, au contraire est bien sûr une backreference.
  • dans une expression - en particulier dans la partie droite de s///, $1 est également interpolé. C'est pour ça qu'on s'en sert pour rappeler le contenu des parenthèses capturantes. \1, au contraire, n'a pas de sémantique précise. Selon le langage et les options, on peut obtenir le contenu de $1 (dans sed), le contenu de \1 mais avec un avertissement (Perl), ou le caractère ASCII numéro 1, c'est à dire Ctrl-A.

Look-ahead et look-behind

Il existe d'autres commandes de longueur zéro comme ^, $ et \b : look-ahead et look-behind. L'opérateur look-ahead, noté (?= ). Il sert à aller voir plus loin dans la chaîne, sans capturer l'expression en question. Par exemple, pour chercher les mots collés avant un nombre (comme "mdlol" dans "qsd mdlol38 43e"), on utilisera :

(\w+)(?=\d+)

Cela permet de garder $& "propre".

Look-behind est similaire, mais permet de chercher avant la chaîne. Il s'écrit (?<= ). Attention, à cause de l'algorithme de backtracking utilisé, on ne peut utiliser que des chaînes de longueur fixe dans un look-behind.

En utilisant ces opérateurs, on peut remarquer que \b peut aussi s'écrire :

/
(?<=\w) (?=\W) # un     mot suivi d'un non-mot
       |       #           ou bien
(?<=\W) (?=\w) # un non-mot suivi d'un     mot
/x

Références

perlre(1), perlrequick(1), perlretut(1)

perlcheat(1) :

REGEX METACHARS            REGEX MODIFIERS
^     string begin         /i case insens.
$     str. end (before \n) /m line based ^$
+     one or more          /s . includes \n
*     zero or more         /x ign. wh.space
?     zero or one          /g global
{3,7} repeat in range
()    capture          REGEX CHARCLASSES
(?:)  no capture       .  == [^\n]
[]    character class  \s == [\x20\f\t\r\n]
|     alternation      \w == [A-Za-z0-9_]
\b    word boundary    \d == [0-9]
\z    string end       \S, \W and \D negate