Quantificateurs gourmands ou paresseux : pourquoi .* en avale trop

Vous écrivez <.+> pour attraper une balise HTML, vous le lancez sur <b>bold</b>, et il trouve toute la chaîne : les deux balises et le texte entre elles. Rien n'est cassé. Le quantificateur a fait exactement ce pour quoi il est conçu : prendre tout ce qu'il peut.

Cet article explique ce que font vraiment les quantificateurs gourmands (greedy) et paresseux (lazy), pourquoi la différence ne se voit que dans ce qui est trouvé, et pourquoi la meilleure solution n'est souvent ni l'un ni l'autre.

01Gourmand : tout prendre, puis rendre

Les quantificateurs *, +, ? et {n,m} sont gourmands par défaut. Ils prennent autant de caractères que possible, et n'en rendent que si la suite du motif échoue.

Voici ce que fait le moteur avec <.+> :

1. < correspond au premier caractère.
2. .+ avale tout jusqu'à la fin de la ligne.
3. > n'a plus rien à quoi correspondre, donc le moteur fait du backtracking (retour arrière) : .+ rend un caractère à la fois jusqu'à ce que > trouve sa place.
4. Le premier > rencontré en reculant est le dernier de la ligne. Correspondance trouvée.

02Paresseux : prendre le moins possible

Ajoutez un ? après n'importe quel quantificateur et il devient paresseux : il prend le moins de caractères possible, et n'en prend davantage que si la suite du motif échoue.

Les versions paresseuses de chaque quantificateur :

Gourmand	Paresseux	Signification
*	*?	zéro ou plus
+	+?	un ou plus
?	??	facultatif
{2,5}	{2,5}?	entre 2 et 5

Même chose avec les chaînes entre guillemets. La version gourmande va du premier guillemet au dernier. La version paresseuse s'arrête au guillemet suivant :

03Souvent mieux que les deux : une classe négative

Les quantificateurs paresseux essaient quand même de faire correspondre . à chaque caractère, y compris celui où vous voulez vous arrêter. Une classe de caractères négative énonce directement la règle d'arrêt : « tout sauf > ».

<[^>]+> et "[^"]*" sont généralement le meilleur choix :

• Plus clair. Le motif dit ce qu'est une balise, pas comment le moteur doit la chercher.
• Plus rapide. Aucun backtracking : [^>]+ s'arrête au premier > par définition.
• Fonctionne sur plusieurs lignes. Par défaut, . ne correspond pas à un saut de ligne : <.+?> rate donc une balise coupée sur deux lignes. [^>], lui, accepte aussi les sauts de ligne.

04La surprise : paresseux ne veut pas dire « correspondance la plus courte »

Paresseux signifie aussi court que possible à partir du point de départ de la correspondance. Cela ne déplace pas ce point de départ. Le moteur renvoie toujours la correspondance la plus à gauche qu'il trouve :

Si vous voulez le a…b le plus court sans a à l'intérieur, dites-le encore avec une classe : a[^a]*b.

05Pourquoi c'est sans importance au golf de regex

Voici un fait utile pour les golfeurs : gourmand ou paresseux, cela ne change jamais si une chaîne correspond ou non. a.*b et a.*?b trouvent exactement le même ensemble de mots. Ils ne diffèrent que par la partie du texte qu'ils renvoient. Comme une chasse demande seulement « ce mot correspond-il ? », un ? après un quantificateur vous coûte un caractère et ne rapporte rien.

Ce qui aide vraiment sur les plateaux, c'est la classe négative, parce qu'elle change ce qui peut correspondre. Sur ce plateau, chaque monstre contient exactement un a :

06Aide-mémoire

• Gourmand (.*, .+) : prend le plus possible, puis recule. Le comportement par défaut.
• Paresseux (.*?, .+?) : prend le moins possible, puis s'étend. Ajoutez ?.
• Classe négative ([^>]*) : prend tout sauf le caractère d'arrêt. Généralement le meilleur outil quand vous savez où vous arrêter.
• Paresseux et gourmand trouvent les mêmes chaînes. Ils diffèrent par ce qu'ils capturent, extraient ou remplacent.

07Continuez à vous entraîner

• La section du guide sur les quantificateurs propose d'autres exemples interactifs.
• La chasse du jour vous attend.