<.+> appliqué à <b>bold</b> and <i>italic</i> ne trouve pas <b>. Il trouve la chaîne entière, du premier < au tout dernier >. Rien n’est cassé. C’est exactement ce qu’un quantificateur greedy est censé faire, et c’est aussi le bug le plus courant de “mon regex matche trop”. Une fois que vous savez ce que fait le moteur pendant qu’il lit votre motif, ce bug et la plupart de ses cousins arrêtent d’être des mystères.

Comment un Moteur Regex Lit Votre Motif

Un moteur regex ne compare pas votre motif à la chaîne comme vous comparez deux chaînes pour l’égalité. Les moteurs que vous utilisez tous les jours (re de Python, RegExp de JavaScript, PCRE, .NET, Java) sont regex-directed : ils parcourent le motif de gauche à droite, jeton par jeton, et pour chaque jeton essaient de consommer des caractères de la chaîne à la position courante. Quand un jeton matche, le moteur avance à la fois le pointeur du motif et celui de la chaîne. Quand un jeton échoue, le moteur revient en arrière (backtracking) : il retourne au dernier point où il avait un choix, comme un quantificateur qui aurait pu matcher moins de caractères ou une branche d’alternance pas encore essayée, et prend l’autre option.

C’est pour ça que <.+> avale toute la ligne. .+ est greedy, donc il attrape d’abord tous les caractères restants de la chaîne, < et > compris. Le moteur a toujours besoin d’un > littéral pour terminer, donc il redonne des caractères un par un depuis la fin jusqu’à ce que le dernier > de la chaîne le satisfasse. Le moteur retourne la première correspondance qu’il trouve dans cet ordre greedy-first. Pour ce motif, c’est la plus longue possible, pas celle qui vous semble correcte.

Essayer d’abord l’option greedy, reculer d’un pas en cas d’échec : cette seule règle explique à la fois le matching quotidien normal et les ralentissements pathologiques plus bas. C’est la même dynamique d’exploration et d’annulation qu’une recherche récursive sans mémoïsation, le type d’explosion que la récursivité expliquée couvre du côté des appels de fonction.

Syntaxe Regex de Base : Ancres, Quantificateurs, Groupes, Lookarounds

Ancres et Classes de Caractères

^ et $ ancrent une correspondance au début et à la fin de la chaîne (ou de la ligne, avec le flag multiline). \d, \w et \s sont des abréviations de classes de caractères pour chiffre, caractère de mot et espace, et [...] permet d’écrire une classe directement.

1
2
3
4

import re

re.search(r"^\d{3}-\d{4}$", "555-0199")
# <re.Match object; span=(0, 8), match='555-0199'>

Sans les ancres, \d{3}-\d{4} matcherait aussi à l’intérieur de "call 555-0199 now". Les ancres transforment “contient” en “est exactement”.

Les classes de caractères opèrent sur ce que le moteur considère comme un caractère, et hors de l’ASCII pur ce n’est pas toujours ce que vous attendez. \w matche une lettre, un chiffre ou un underscore selon la notion de caractère du moteur, qui est la même distinction point de code contre octet que couvre ce qu’est Unicode et comment fonctionne l’UTF-8. Faites tourner un motif sur des octets UTF-8 bruts plutôt que sur du texte décodé et un caractère multi-octets se retrouve coupé en ce que le moteur croit être des caractères séparés.

Quantificateurs Greedy et Lazy

+, * et {m,n} sont greedy par défaut : ils prennent tout ce qu’ils peuvent, puis reviennent en arrière si cela casse le reste du motif. Mettez un ? après l’un d’eux et le quantificateur devient lazy. Il prend le minimum possible et ne s’étend que lorsqu’il y est obligé.

1
2
3

s = "<b>bold</b> and <i>italic</i>"
re.findall(r"<.+>", s)    # ['<b>bold</b> and <i>italic</i>']
re.findall(r"<.+?>", s)   # ['<b>', '</b>', '<i>', '</i>']

Un caractère de différence, un résultat complètement différent. Quand vous voulez la chose la plus courte qui satisfait le reste du motif, utilisez la forme lazy. Si ce que vous matchez est du markup, lisez la dernière section d’abord.

Groupes Capturants, Non Capturants et Nommés

(...) capture ce qu’il matche pour que vous puissiez l’extraire ensuite. (?:...) groupe pour la structure, par exemple pour appliquer un quantificateur à tout un sous-motif, sans créer de capture. (?P<name>...) en Python ((?<name>...) en JavaScript, Java et .NET) nomme un groupe pour que vous n’ayez pas à compter les parenthèses pour le retrouver plus tard.

1
2
3

m = re.match(r"(?P<year>\d{4})-(?P<month>\d{2})-(?P<day>\d{2})", "2026-10-28")
m.groupdict()
# {'year': '2026', 'month': '10', 'day': '28'}

1
2
3

const m = "2026-10-28".match(/(?<year>\d{4})-(?<month>\d{2})-(?<day>\d{2})/);
m.groups;
// [Object: null prototype] { year: '2026', month: '10', day: '28' }

Vous lisez le résultat par nom, avec groupdict() en Python ou .groups en JavaScript (les groupes nommés y sont arrivés avec ES2018), plutôt que match[1], match[2]. Dès qu’un motif a plus de deux groupes, les caractères en plus se rentabilisent.

Lookahead et Lookbehind

Un lookaround vérifie une position, pas des caractères. Il vérifie que quelque chose est (ou n’est pas) présent sans le consommer. (?=...) est un lookahead positif, (?!...) négatif ; (?<=...) et (?<!...) sont les équivalents pour le lookbehind.

1
2

"$40 bill".match(/(?<=\$)\d+/);
// [ '40', index: 1, ... ]   -- trouve "40", pas "$40"

Le re de Python exige que le lookbehind soit à largeur fixe : (?<=\$) fonctionne, (?<=\$+) lève une erreur, parce que le moteur doit savoir exactement de combien reculer avant de vérifier. JavaScript, qui a ajouté le lookbehind en ES2018 en même temps que les groupes nommés, n’a pas cette limite, donc (?<=\$+) fonctionne là-bas. En Python, le package tiers regex sur PyPI lève la restriction si vous avez besoin d’un lookbehind à largeur variable.

Pourquoi Certains Regex Bloquent : le Catastrophic Backtracking

Prenez la règle de backtracking du début et donnez-lui un cas dont elle ne peut pas se sortir. Imbriquez deux quantificateurs pour que le moteur ait de nombreuses façons de diviser la même séquence de caractères entre eux, puis faites échouer la correspondance juste à la fin. Le moteur n’échoue pas vite. Il essaie chaque division avant d’abandonner.

1
2
3
4
5
6
7
8

import re, time

pattern = re.compile(r"(a+)+b")
for n in (20, 24, 26, 28):
    s = "a" * n  # pas de "b" finale, donc ça ne matche jamais
    start = time.perf_counter()
    pattern.match(s)
    print(n, f"{(time.perf_counter() - start) * 1000:.1f} ms")

1
2
3
4

20 41.6 ms
24 525.8 ms
26 2083.6 ms
28 8369.3 ms

Chaque a supplémentaire double à peu près le temps : deux caractères de plus, quatre fois plus lent. C’est une croissance exponentielle, la courbe que la notation Big O place de l’autre côté de O(n^2). (a+)+ peut diviser une séquence de 28 a en groupes de 2^27 façons différentes, et sans b dans la chaîne le moteur les essaie une par une avant de pouvoir signaler “aucune correspondance”. Suivez la même courbe jusqu’à 40 caractères et l’attente est d’environ neuf heures.

Quand l’entrée vient d’un utilisateur plutôt que de vos fixtures de test, c’est une vulnérabilité exploitable : ReDoS, regular expression denial of service. Le déclencheur habituel est exactement cette forme, deux quantificateurs empilés sans rien entre eux pour forcer une division unique.

Trois façons de l’arrêter, de la moins coûteuse à la plus coûteuse :

  1. Supprimez l’ambiguïté. (a+)+b et a+b matchent les mêmes chaînes valides ici ; le + extérieur n’apporte rien. La plupart des motifs catastrophiques ont une couche redondante comme celle-ci dès qu’on la cherche.

  2. Rendez le quantificateur intérieur possessif, ou enveloppez-le dans un groupe atomique. Les deux disent au moteur “une fois que ceci matche, ne pas revenir en arrière à l’intérieur”. Cela élimine l’explosion exponentielle, au prix de rejeter occasionnellement une chaîne que la version avec backtracking aurait acceptée. Le re de Python supporte les deux depuis la 3.11 :

    1
2
3
4
5
6
7

    pattern = re.compile(r"(?>a+)+b")   # groupe atomique
# ou : re.compile(r"a++b")          # quantificateur possessif, Python 3.11+
for n in (28, 1_000, 100_000):
    s = "a" * n
    start = time.perf_counter()
    pattern.match(s)
    print(n, f"{(time.perf_counter() - start) * 1000:.3f} ms")

    1
2
3

    28 0.002 ms
1000 0.001 ms
100000 0.026 ms

    La même correspondance échouée sur 100 000 caractères prend 26 microsecondes. Le RegExp natif de JavaScript n’a ni l’une ni l’autre de ces fonctionnalités. Le package npm regex ajoute les groupes atomiques et les quantificateurs possessifs en syntaxe étendue si vous en avez besoin sans changer de moteur.

  3. Bornez les quantificateurs sans limite. {1,50} au lieu de + plafonne la gravité du pire cas, même sans réécrire la logique.

Si la chaîne peut venir de l’extérieur de votre code, comme le corps d’une requête ou une valeur de configuration écrite par quelqu’un d’autre, traitez les quantificateurs imbriqués comme vous traiteriez une boucle sans limite sur une entrée externe. Testez le motif contre une longue séquence du caractère qui déclenche l’ambiguïté, pas seulement contre vos fixtures du chemin heureux.

Quand Ne Pas Utiliser le Regex

Un regex n’a aucune mémoire de sa profondeur. C’est bien pour du texte plat et à forme fixe comme une date ou une ligne de log avec des champs connus. C’est aussi pour ça que <.+> ne peut pas sauter de façon fiable un seul tag HTML : il n’a pas le concept de “ce < ouvre un tag que le prochain > correspondant ferme”, seulement “prendre jusqu’au dernier > qu’il trouve”. Les structures imbriquées comme HTML, JSON, le code source et les parenthèses équilibrées ont besoin d’une grammaire, pas d’un motif. L’échec typique est un regex qui passe tous les cas de test que vous avez écrits, puis rencontre un fichier réel avec un commentaire contenant un > et matche silencieusement le mauvais passage au lieu de lever une erreur.

Utilisez le parser qui existe déjà : un parser HTML pour le HTML, json.loads pour le JSON, le module AST de votre langage pour le code. Gardez le regex pour valider ou extraire du texte à forme plate, et passez à un parser dès que “équilibré” ou “imbriqué” apparaît dans la description de ce que vous matchez.

Articles associés