Comment l'expression régulière "(aa)+\1" correspond-elle à "aaaaaa" ?

Question

Quelqu'un peut-il expliquer le processus par lequel un moteur d'expressions régulières associe (aa)+\1 à aaaaaa? Je sais qu'il existe un processus appelé retour en arrière lorsque vous utilisez + ou * mais je ne suis pas sûr comment cela fonctionne dans cet exemple.

Answer 1

Lorsque vous mettez le quantificateur en dehors du groupe de capture, il ne capture pas l'ensemble de la chaîne correspondant à ce motif avec le quantificateur. Il correspond plutôt à la dernière répétition que le motif a trouvé.

Ainsi, (aa)+ ne capturera pas aaaa dans le groupe de capture, mais juste la dernière paire - aa, afin de satisfaire le reste du motif regex.

Par conséquent, avec (aa)+\1, le motif correspond d'abord à - aaaa, puis la référence arrière \1 correspond au groupe capturé - aa. Ainsi, cela correspond à la chaîne - aaaaaa. Ainsi, (aa)+ ne correspondra pas à tous les a, car il ne resterait rien à faire correspondre avec \1.

Voici la décomposition de l'expression régulière (aa)+\1 :

• (aa)+ correspond aux deux premiers aa dans la chaîne. Chaîne restante - aaaa.
• Il reste des correspondances à faire avec (aa)+, donc il continue pour correspondre au prochain aa. Chaîne restante - aa.
• Encore une fois, (aa)+ peut correspondre à la chaîne restante. Il correspond donc au prochain aa. Chaîne restante - "". Rappelez-vous, les quantificateurs agissent par défaut de manière gourmande. Ils correspondent autant qu'ils le peuvent.
• Maintenant, (aa)+ ne peut plus correspondre davantage.
• Ensuite dans le motif vient \1. Mais il ne reste rien à faire correspondre.
• Revenir en arrière sur le dernier motif correspondant par (aa)+. Chaîne restante - "aa".
• Maintenant, \1 essaie de correspondre à nouveau, et il correspond avec succès à aa, car c'est ce qui se trouve actuellement dans le 1er groupe de capture.

---

Références :

• Regular-Expressions.info - Backtracking catastrophique

Answer 2

Le quantifieur + signifie "1 ou plus". Le \1 se réfère au groupe capturé, qui est la même chose à laquelle le quantifieur se réfère. Donc en effet, cela signifie "groupe aa, 1 ou plusieurs fois, et ensuite une fois de plus". Ce qui revient à dire "2 ou plusieurs fois".

Donc le regex pourrait être plus clair comme ceci : /(aa){2,}/

Puisque aaaaaa est trois ensembles du groupe aa, le regex correspond à la chaîne.

Answer 3

Scénario :

aa           # le groupe est trouvé
aaaa         # le groupe est répété une fois, à cause du quantificateur +
aaaaaa       # le groupe est encore une fois répété, toujours à cause 
             # du quantificateur + (et parce qu'il est gourmand et prend tout ce qu'il peut.)
             # Mais puisque tous les caractères sont consommés, et qu'il y a \1
             # le motif échouera.
aaaa         # le moteur regex doit faire machine arrière pour essayer une autre approche à cause de \1
aaaaaa       # Tu es arrivé ! (les 2 derniers "a" sont pour le \1)

Vous pouvez vérifier ce comportement en utilisant un quantificateur possessif (++) qui interdit les retours en arrière :

(aa)++\1            # ne correspondra jamais