Quantificateurs Greedy vs Reluctant vs. Possessive

J’ai trouvé cet excellent tutoriel sur les expressions régulières et bien que je comprenne intuitivement ce que font les quantificateurs “gourmands”, “réticents” et “possessifs”, il semble y avoir un grave trou dans ma compréhension.

Plus précisément, dans l’exemple suivant:

Enter your regex: .*foo // greedy quantifier Enter input ssortingng to search: xfooxxxxxxfoo I found the text "xfooxxxxxxfoo" starting at index 0 and ending at index 13. Enter your regex: .*?foo // reluctant quantifier Enter input ssortingng to search: xfooxxxxxxfoo I found the text "xfoo" starting at index 0 and ending at index 4. I found the text "xxxxxxfoo" starting at index 4 and ending at index 13. Enter your regex: .*+foo // possessive quantifier Enter input ssortingng to search: xfooxxxxxxfoo No match found. 

L’explication mentionne de manger toute la chaîne de saisie, les lettres ont été consommées , le matcher a reculé , l’occurrence la plus à droite de “foo” a été régurgitée , etc.

Malheureusement, malgré les belles métaphores, je ne comprends toujours pas ce qui est mangé par qui … Connaissez-vous un autre tutoriel qui explique (de manière concise) le fonctionnement des moteurs d’expressions régulières?

Sinon, si quelqu’un peut expliquer, dans une formulation quelque peu différente, le paragraphe suivant, cela serait très apprécié:

Le premier exemple utilise le quantificateur gourmand. * Pour trouver “n’importe quoi”, zéro ou plusieurs fois, suivi des lettres “f” “o” “o”. Comme le quantificateur est gourmand, la partie. * De l’expression mange d’abord toute la chaîne d’entrée. À ce stade, l’expression globale ne peut pas réussir, car les trois dernières lettres (“f” “o” “o”) ont déjà été consommées ( par qui? ). Ainsi, le matcher recule lentement ( de droite à gauche? ) Une lettre à la fois jusqu’à ce que l’occurrence la plus à droite de “foo” ait été régurgitée ( qu’est-ce que cela signifie? ).

Le deuxième exemple, cependant, est réticent, donc il commence par consumr ( par qui? ) D’abord “rien”. Parce que “foo” n’apparaît pas au début de la chaîne, il est obligé d’avaler ( qui avale?) La première lettre (un “x”), qui déclenche la première correspondance à 0 et 4. Notre harnais de test continue le processus jusqu’à ce que la chaîne d’entrée soit épuisée. Il trouve un autre match à 4 et 13.

Le troisième exemple ne parvient pas à trouver une correspondance car le quantificateur est possessif. Dans ce cas, toute la chaîne d’entrée est consommée par. * +, ( Comment? ) Ne laissant rien pour satisfaire le “foo” à la fin de l’expression. Utilisez un quantificateur possessif pour les situations où vous voulez saisir tout sans rien reculer ( qu’est-ce que cela signifie? ); il surperformera le quantificateur gourmand équivalent dans les cas où la correspondance n’est pas immédiatement trouvée.

Je vais tenter le coup.

Un quantificateur gourmand correspond tout d’abord autant que possible. Donc, le .* Correspond à la chaîne entière. Ensuite, le matcher essaie de faire correspondre le suivant, mais il ne rest plus de caractères. Donc, il fait un “backtrack”, ce qui fait que le quantificateur gourmand correspond à une chose de moins (en laissant le “o” à la fin de la chaîne sans correspondance). Cela ne correspond toujours pas au f dans le regex, donc il “recule” un pas de plus, ce qui fait que le quantificateur gourmand correspond à une chose de moins (laissant le “oo” à la fin de la chaîne sans correspondance). Cela ne correspond toujours pas au f dans le regex, il fait donc un pas en arrière (laissant le “foo” à la fin de la chaîne sans correspondance). Maintenant, le matcher correspond enfin au f dans le regex, et le o et le prochain o sont également mis en correspondance. Succès!

Un quantificateur réticent ou “non gourmand” correspond le moins possible. Donc, le .* Ne correspond à rien au début, laissant la chaîne entière inégalée. Ensuite, le matcher essaie de faire correspondre le suivi de f , mais la partie sans correspondance de la chaîne commence par “x”, ce qui ne fonctionne pas. Ainsi, le matcher fait un retour en arrière, ce qui fait que le quantificateur non gourmand correspond à une autre chose (maintenant il correspond au “x”, laissant “fooxxxxxxfoo” sans correspondance). Ensuite, il essaie de faire correspondre le f , qui réussit, et le o et le prochain o dans la correspondance regex. Succès!

Dans votre exemple, il lance ensuite le processus avec la partie restante de la chaîne sans correspondance, en suivant le même processus.

Un quantificateur possessif est comme le quantificateur gourmand, mais il ne fait pas marche arrière. Donc, cela commence par .* Correspondant à la chaîne entière, ne laissant rien sans correspondance. Il ne rest alors plus rien à faire correspondre au f dans l’expression régulière. Puisque le quantificateur possessif ne fait pas marche arrière, la correspondance échoue.

Ce n’est que ma pratique pour visualiser la scène.

Image visuelle

Je n’ai pas entendu les termes exacts «régurgiter» ou «reculer» avant; l’expression qui les remplacerait serait “revenir en arrière”, mais “régurgiter” semble être une phrase aussi bonne que “le contenu qui avait été accepté avant que le retour en arrière ne le rejette”.

La chose importante à réaliser à propos de la plupart des moteurs de regex est qu’ils font un retour en arrière : ils accepteront provisoirement une correspondance partielle potentielle, tout en essayant de faire correspondre tout le contenu de la regex. Si le regex ne peut pas être complètement associé à la première tentative, le moteur de regex va revenir en arrière sur l’une de ses correspondances. Il va essayer de faire correspondre * , + ? , alternance ou répétition différemment, et réessayez. (Et oui, ce processus peut prendre beaucoup de temps.)

Le premier exemple utilise le quantificateur gourmand. * Pour trouver “n’importe quoi”, zéro ou plusieurs fois, suivi des lettres “f” “o” “o”. Comme le quantificateur est gourmand, la partie. * De l’expression mange d’abord toute la chaîne d’entrée. À ce stade, l’expression globale ne peut pas réussir, car les trois dernières lettres (“f” “o” “o”) ont déjà été consommées ( par qui? ).

Les trois dernières lettres, f , o et o étaient déjà consommées par la partie initiale .* la règle. Cependant, l’élément suivant de l’expression rationnelle, f , n’a plus rien dans la chaîne d’entrée. Le moteur sera obligé de revenir en arrière sur sa correspondance initiale .* Et d’essayer de faire correspondre tout-sauf-le-dernier caractère. (Cela peut être intelligent et revenir en arrière à tout sauf les trois derniers, car il a trois termes littéraux, mais je ne connais pas les détails d’implémentation à ce niveau.)

Ainsi, le matcher recule lentement ( de droite à gauche? ) Une lettre à la fois jusqu’à ce que la situation la plus à droite de “foo” ait été régurgitée ( qu’est-ce que cela signifie? ), À laquelle

Cela signifie que le foo avait provisoirement été inclus lors de la correspondance .* . Étant donné que cette tentative a échoué, le moteur de regex tente d’accepter un caractère de moins en .* . S’il y avait eu une correspondance réussie avant le .* Dans cet exemple, le moteur essaierait probablement de raccourcir la correspondance .* (De droite à gauche, comme vous l’avez souligné, car c’est un qualificatif gourmand), et si a été incapable de faire correspondre les entrées entières, alors il pourrait être forcé de réévaluer ce qu’il avait comparé avant le .* dans mon exemple hypothétique.

pointe la correspondance réussit et la recherche se termine.

Le deuxième exemple, cependant, est réticent, donc il commence par consumr ( par qui? ) D’abord “rien”. Parce que “foo”

Le rien initial est consommé par .?* , Qui consumra le plus petit nombre possible de tout ce qui permet au rest de l’expression régulière de correspondre.

n’apparaît pas au début de la chaîne, il est obligé d’avaler ( qui avale?) le

Là encore, le .?* (Dans ce cas, le moteur regex étend la correspondance pour .*? De gauche à droite, car .*? Est réticent.)

première lettre (un “x”), qui déclenche la première correspondance à 0 et 4. Notre faisceau de test continue le processus jusqu’à ce que la chaîne d’entrée soit épuisée. Il trouve une autre correspondance à 4 et 13.

Le troisième exemple ne parvient pas à trouver une correspondance car le quantificateur est possessif. Dans ce cas, toute la chaîne d’entrée est consommée par. * +, ( Comment? )

A. .*+ Consumra autant que possible, et ne fera pas marche arrière pour trouver de nouvelles correspondances lorsque le regex dans son ensemble ne parvient pas à trouver une correspondance. Étant donné que la forme possessive n’effectue pas de retour en arrière, vous ne verrez probablement pas beaucoup d’utilisations avec .*+ , Mais plutôt avec des classes de caractères ou des ressortingctions similaires: account: [[:digit:]]*+ phone: [[:digit:]]*+ .

Cela peut considérablement accélérer la mise en correspondance des regex, car vous dites au moteur regex qu’il ne doit jamais revenir en arrière sur les correspondances potentielles si une entrée ne correspond pas. (Si vous deviez écrire tout le code correspondant à la main, cela équivaudrait à ne jamais utiliser putc(3) pour repousser un caractère d’entrée. Il serait très similaire au code naïf que l’on pourrait écrire au premier essai. Sauf que les moteurs de regex sont bien meilleurs qu’un seul caractère de push-back, ils peuvent revenir en arrière à zéro et réessayer. 🙂

Mais plus que des accélérations potentielles, cela peut également vous permettre d’écrire des regex qui correspondent exactement à ce dont vous avez besoin. J’ai de la difficulté à trouver un exemple simple 🙂 mais écrire une regex en utilisant des quantificateurs possessifs vs gourmands peut vous donner différentes correspondances, et l’une ou l’autre peut être plus appropriée.

ne rien laisser pour satisfaire le “foo” à la fin de l’expression. Utilisez un quantificateur possessif pour les situations où vous voulez saisir tout sans rien reculer ( qu’est-ce que cela signifie? ); il surperformera

“Retrait” signifie dans ce contexte “retour en arrière” – rejetant une tentative de correspondance partielle pour tenter une autre correspondance partielle, qui peut ou peut échouer.

le quantificateur gourmand équivalent dans les cas où la correspondance n’est pas immédiatement trouvée.

http://swtch.com/~rsc/regexp/regexp1.html

Je ne suis pas sûr que ce soit la meilleure explication sur Internet, mais elle est raisonnablement bien écrite et correctement détaillée, et j’y reviens sans cesse. Vous pourriez vouloir le vérifier.

Si vous voulez un niveau supérieur (explication moins détaillée), pour des expressions régulières simples telles que celle que vous regardez, un moteur d’expression régulière fonctionne par backtracking. Essentiellement, il choisit (“mange”) une section de la chaîne et essaie de faire correspondre l’expression régulière à cette section. Si ça correspond, génial. Si ce n’est pas le cas, le moteur modifie son choix de la section de la chaîne et essaie de faire correspondre l’expression rationnelle à cette section, et ainsi de suite, jusqu’à ce qu’il tente tous les choix possibles.

Ce processus est utilisé de manière récursive: dans sa tentative de faire correspondre une chaîne avec une expression régulière donnée, le moteur divisera l’expression régulière en plusieurs parties et appliquera l’algorithme à chaque élément individuellement.

La différence entre les quantificateurs gourmands, réticents et possessifs intervient lorsque le moteur fait ses choix sur la partie de la chaîne à laquelle il convient de faire correspondre, et sur la façon de modifier ce choix s’il ne fonctionne pas la première fois. Les règles sont les suivantes:

  • Un quantificateur gourmand indique au moteur de démarrer avec la chaîne entière (ou du moins, tout ce qui n’a pas encore été trouvé dans les parties précédentes de l’expression régulière) et vérifie s’il correspond à l’expression rationnelle. Si oui, super; le moteur peut continuer avec le rest de l’expression rationnelle. Sinon, il essaie à nouveau, mais en supprimant un caractère (le dernier) de la section de la chaîne à vérifier. Si cela ne fonctionne pas, il coupe un autre personnage, etc. Ainsi, un quantificateur gourmand vérifie les correspondances possibles dans l’ordre croissant.

  • Un quantificateur réticent demande au moteur de démarrer avec le morceau le plus court possible de la chaîne. Si cela correspond, le moteur peut continuer; sinon, il ajoute un caractère à la section de la chaîne en cours de vérification et essaie de le faire, et ainsi de suite jusqu’à ce qu’il trouve une correspondance ou que la chaîne entière soit épuisée. Ainsi, un quantificateur réticent vérifie les correspondances possibles dans l’ordre du plus court au plus long.

  • Un quantificateur possessif est comme un quantificateur gourmand lors de la première tentative: il indique au moteur de commencer en vérifiant toute la chaîne. La différence est que si cela ne fonctionne pas, le quantificateur possessif signale que la correspondance a échoué tout de suite. Le moteur ne modifie pas la section de la chaîne considérée et ne fait plus de tentatives.

C’est pourquoi la correspondance du quantificateur possessif échoue dans votre exemple: le .*+ Est vérifié par rapport à la chaîne entière, ce qui correspond, mais le moteur continue de chercher des caractères supplémentaires après cela – mais bien sûr il ne trouve pas eux, parce que vous êtes déjà à la fin de la chaîne. Si c’était un quantificateur gourmand, il ferait un retour en arrière et essaierait de ne faire correspondre que le caractère précédent à l’avant-dernier, puis au troisième jusqu’au dernier caractère, puis jusqu’au quasortingème au dernier caractère, car seul alors y a-t-il un foo après le .* a “mangé” la première partie de la chaîne.

Voici ma prise en utilisant les positions Cell et Index (voir le diagramme ici pour distinguer une cellule d’un index).

Gourmand – Associez autant que possible au quantificateur gourmand et à l’ensemble de l’expression rationnelle. S’il n’y a pas de correspondance, revenir en arrière sur le quantificateur gourmand.

Chaîne d’entrée: xfooxxxxxxfoo
Regex:. * Foo

Le Regex ci-dessus a deux parties:
(moi et
ii) “foo”

Chacune des étapes ci-dessous parsingra les deux parties. Des commentaires supplémentaires pour une correspondance avec ‘Pass’ ou ‘Fail’ sont expliqués entre accolades.

Étape 1:
(i). * = xfooxxxxxxfoo – PASS (‘. *’ est un quantificateur gourmand et utilisera toute la chaîne d’entrée)
(ii) foo = Aucun caractère à conserver après l’index 13 – FAIL
Match échoué.

Étape 2:
(i). * = xfooxxxxxxfo – PASS (Retour sur le quantificateur gourmand ‘. *’)
(ii) foo = o – FAIL
Match échoué.

Étape 3:
(i). * = xfooxxxxxxf – PASS (Retour sur le quantificateur gourmand ‘. *’)
(ii) foo = oo – FAIL
Match échoué.

Étape 4:
(i). * = xfooxxxxxx – PASS (Retour sur le quantificateur gourmand ‘. *’)
(ii) foo = foo – PASS
Rapport MATCH

Résultat: 1 match (s)
J’ai trouvé le texte “xfooxxxxxxfoo” commençant à l’index 0 et se terminant à l’index 13.

Réticent – Associez le moins possible au quantificateur réticent et faites correspondre l’intégralité de l’expression rationnelle. S’il n’y a pas de correspondance, ajoutez des caractères au quantificateur réticent.

Chaîne d’entrée: xfooxxxxxxfoo
Regex:. *? Foo

La regex ci-dessus comporte deux parties:
(je) ‘.*?’ et
ii) “foo”

Étape 1:
. *? = ” (vide) – PASS (Correspond le moins possible au quantificateur réticent ‘. *?’. L’index 0 ayant ” est une correspondance.)
foo = xfo – FAIL (cellule 0,1,2 – c.-à-d. index entre 0 et 3)
Match échoué.

Étape 2:
. *? = x – PASS (Ajoute des caractères au quantificateur réticent ‘. *?’. La cellule 0 ayant ‘x’ est une correspondance.)
foo = foo – PASS
Rapport MATCH

Étape 3:
. *? = ” (vide) – PASS (Correspond le moins possible au quantificateur réticent ‘. *?’. Index 4 ayant ” est une correspondance.)
foo = xxx – FAIL (Cell 4,5,6 – c’est-à-dire entre 4 et 7)
Match échoué.

Étape 4:
. *? = x – PASS (Ajoute des caractères au quantificateur réticent ‘. *?’. Cellule 4.)
foo = xxx – FAIL (Cell 5,6,7 – c’est-à-dire entre 5 et 8)
Match échoué.

Étape 5:
. *? = xx – PASS (Ajoute des caractères au quantificateur réticent ‘. *?’. Cellule 4 à 5.)
foo = xxx – FAIL (Cell 6,7,8 – c’est-à-dire entre 6 et 9)
Match échoué.

Étape 6:
. *? = xxx – PASS (Ajoute des caractères au quantificateur réticent ‘. *?’. Cellule 4 à 6.)
foo = xxx – FAIL (Cell 7,8,9 – c’est-à-dire index entre 7 et 10)
Match échoué.

Étape 7:
. *? = xxxx – PASS (Ajoute des caractères au quantificateur réticent ‘. *?’. Cellule 4 à 7.)
foo = xxf – FAIL (Cell 8,9,10 – c.-à-d. index entre 8 et 11)
Match échoué.

Étape 8:
. *? = xxxxx – PASS (Ajoute des caractères au quantificateur réticent ‘. *?’. Cellule 4 à 8.)
foo = xfo – FAIL (Cell 9,10,11 – c’est-à-dire entre 9 et 12)
Match échoué.

Étape 9:
. *? = xxxxxx – PASS (Ajoute des caractères au quantificateur réticent ‘. *?’. Cellule 4 à 9.)
foo = foo – PASS (Cell 10,11,12 – c’est-à-dire entre 10 et 13)
Rapport MATCH

Étape 10:
. *? = ” (vide) – PASS (Associe le moins possible au quantificateur réticent ‘. *?’. L’index 13 est vide.)
foo = Aucun caractère restant à faire correspondre – FAIL (Il n’y a rien après l’index 13 pour correspondre)
Match échoué.

Résultat: 2 match (s)
J’ai trouvé le texte “xfoo” commençant à l’index 0 et se terminant à l’index 4.
J’ai trouvé le texte “xxxxxxfoo” commençant à l’index 4 et se terminant à l’index 13.

Possessive – Associez autant que possible au quantifère possessif et faites correspondre l’ensemble de l’expression rationnelle. Ne pas revenir en arrière.

Chaîne d’entrée: xfooxxxxxxfoo
Regex:. * + Foo

La regex ci-dessus comporte deux parties: ‘. * +’ Et ‘foo’.

Étape 1:
. * + = xfooxxxxxxfoo – PASS (Associe autant que possible au quantificateur possessif ‘. *’)
foo = Aucun personnage restant à faire correspondre – FAIL (Rien à faire après l’index 13)
Match échoué.

Remarque: le retour en arrière n’est pas autorisé.

Résultat: 0 match (s)

Gourmand: “correspond à la séquence de caractères la plus longue possible”

Réticent: “correspond à la séquence de caractères la plus courte possible”

Possessive: Ceci est un peu étrange car il ne tente PAS (contrairement à la cupidité et à la réticence) de trouver une correspondance pour l’ensemble de l’expression rationnelle.

Au fait: aucune implémentation de modèle de regex n’utilisera jamais le backtracking. Tous les modèles réels sont extrêmement rapides – presque indépendants de la complexité de l’expression régulière!

La quantification gourmande implique une correspondance de motif utilisant tous les caractères non validés restants d’une chaîne au cours d’une itération. Les caractères non validés commencent dans la séquence active . Chaque fois qu’une correspondance ne se produit pas, le caractère à la fin est mis en quarantaine et le contrôle est effectué à nouveau.

Lorsque la séquence active satisfait uniquement aux conditions principales du modèle d’expression régulière, une tentative de validation des conditions restantes par rapport à la quarantaine est effectuée. Si cette validation réussit, les caractères correspondants en quarantaine sont validés et les caractères non appariés résiduels restnt non validés et seront utilisés lorsque le processus recommencera à la prochaine itération.

Le stream de caractères va de la séquence active à la quarantaine. Le comportement résultant est que autant de la séquence originale est incluse dans une correspondance que possible.

La quantification réticente est essentiellement la même que la qualification gourmande, sauf que le stream de caractères est le contraire – c’est-à-dire qu’ils commencent dans la quarantaine et entrent dans la séquence active . Le comportement qui en résulte est que la séquence d’origine est la plus petite possible dans une correspondance.

La quantification possessive n’a pas de quarantaine et comprend tout dans une séquence active fixe.