Quantificateurs avides vs réticents vs possessifs

J'ai trouvé cet excellent tutoriel sur les expressions régulières et bien que je comprenne intuitivement ce que font les quantificateurs "avides", "réticents" et "possessifs", il semble y avoir un sérieux trou dans ma compréhension.

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

Enter your regex: .*foo  // greedy quantifier
Enter input string 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 string 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 string to search: xfooxxxxxxfoo
No match found.

L'explication mentionne avoir mangé la chaîne d'entrée entière, des 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) comment fonctionnent les moteurs d'expressions régulières?

Alternativement, si quelqu'un peut expliquer dans une formulation quelque peu différente le paragraphe suivant, ce 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". Parce que le quantificateur est gourmand, la partie. * De l'expression mange d'abord la chaîne d'entrée entière. À 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" soit régurgitée ( qu'est-ce que cela signifie? ), À quel point la correspondance réussit et la recherche se termine.

Le deuxième exemple, cependant, est réticent, il commence donc par consommer d'abord ( par qui? ) "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"), ce 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, la chaîne d'entrée entière 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 quelque chose sans jamais reculer ( qu'est-ce que signifie reculer? ); il surpassera le quantificateur gourmand équivalent dans les cas où la correspondance n'est pas immédiatement trouvée.

Je vais essayer.

Un quantificateur gourmand correspond d'abord autant que possible. Ainsi, le .*correspond à la chaîne entière. Ensuite, le matcher essaie de faire correspondre les éléments fsuivants, mais il ne reste aucun caractère. Ainsi, il "revient en arrière", ce qui fait que le quantificateur gourmand correspond à un caractère de moins (en laissant le "o" à la fin de la chaîne sans correspondance). Cela ne correspond toujours pas fà l'expression rationnelle, donc il revient en arrière d'une étape supplémentaire, ce qui fait que le quantificateur gourmand correspond à nouveau à un caractère de moins (en laissant le "oo" à la fin de la chaîne sans correspondance). Cela ne correspond toujours pas au fdans l'expression régulière, donc il revient en arrière d'une étape de plus (en laissant le "foo" à la fin de la chaîne sans correspondance). Maintenant, le match correspond enfin fà l'expression rationnelle,oosont assortis aussi. Succès!

Un quantificateur réticent ou "non gourmand" correspond d'abord 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 les éléments fsuivants, mais la partie sans correspondance de la chaîne commence par "x", ce qui ne fonctionne pas. Ainsi, le matcher revient en arrière, ce qui fait que le quantificateur non gourmand correspond à un caractère de plus (maintenant il correspond au "x", laissant "fooxxxxxxfoo" inégalé). Ensuite, il essaie de faire correspondre le f, qui réussit, et le oet le suivant odans la correspondance d'expression régulière aussi. Succès!

Dans votre exemple, il recommence alors le processus avec la partie non correspondante restante de la chaîne, "xxxxxxfoo", en suivant le même processus.

Un quantificateur possessif est comme le quantificateur gourmand, mais il ne revient pas en arrière. Il commence donc par faire .*correspondre la chaîne entière, ne laissant rien d'inégalé. Ensuite, il ne reste plus rien à faire avec le fdans l'expression régulière. Puisque le quantificateur possessif ne revient pas en arrière, la correspondance échoue là-bas.

C'est juste ma sortie d'entraînement pour visualiser la scène-

Je n'ai jamais entendu les termes exacts «régurgiter» ou «reculer» auparavant; l'expression qui remplacerait ces derniers est "retour en arrière", mais "régurgiter" semble être une expression aussi bonne que n'importe laquelle pour "le contenu qui avait été provisoirement accepté avant que le retour en arrière ne le rejette".

La chose importante à réaliser sur la plupart des moteurs d'expression régulière est qu'ils font marche arrière : ils accepteront provisoirement une correspondance partielle potentielle, tout en essayant de faire correspondre le contenu entier de l'expression régulière. Si l'expression régulière ne peut pas être complètement adapté à la première tentative, le moteur de regex revenir en arrière sur l' un de ses matchs. Il essayera matching *, +, ?, alternance ou {n,m}répétition différemment, et essayez à nouveau. (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". Parce que le quantificateur est gourmand, la partie. * De l'expression mange d'abord la chaîne d'entrée entière. À 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, oet oont déjà été consommés par la première .*partie de la règle. Cependant, l'élément suivant dans l'expression régulière 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 le dernier caractère. (Il pourrait être intelligent et revenir à tous les trois, sauf les trois derniers, car il contient trois termes littéraux, mais je ne connais pas les détails de mise en œuvre à ce niveau.)

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? ), À laquelle

Cela signifie qu'ils fooavaient provisoirement été inclus lors de l'appariement .*. Parce que cette tentative a échoué, le moteur d'expression régulière essaie d'accepter un caractère de moins dans .*. 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 il s'agit d'un qualificatif gourmand), et s'il ne pouvait pas correspondre toutes les entrées, alors il pourrait être forcé de réévaluer ce qu'il avait correspondu avant le .*dans mon exemple hypothétique.

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

Le deuxième exemple, cependant, est réticent, il commence donc par consommer d'abord ( par qui? ) "Rien". Parce que "foo"

Le rien initial est consommé par .?*, ce qui consommera la quantité la plus courte possible de tout ce qui permet au reste 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

Encore une fois, le .?*consomme le premier caractère, après avoir fait marche arrière sur l'échec initial à faire correspondre l'intégralité de l'expression rationnelle avec la correspondance la plus courte possible. (Dans ce cas, le moteur d'expression régulière étend la correspondance .*?de gauche à droite, car il .*?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 un autre match à 4 et 13.

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

A .*+consommera autant que possible et ne reviendra pas en arrière pour trouver de nouvelles correspondances lorsque l'expression régulière dans son ensemble ne parvient pas à trouver une correspondance. Parce que la forme possessive ne fonctionne pas retours en arrière, vous ne verrez probablement pas beaucoup d' utilisations avec .*+, mais avec des classes de caractères ou des restrictions similaires: account: [[:digit:]]*+ phone: [[:digit:]]*+.

Cela peut accélérer considérablement la correspondance des expressions rationnelles, car vous dites au moteur d'expression régulière qu'il ne devrait 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 reviendrait à ne jamais utiliser putc(3)pour «repousser» un caractère d'entrée. Ce serait très similaire au code naïf que l'on pourrait écrire lors d'un premier essai. Sauf que les moteurs d'expression régulière sont bien mieux qu'un seul caractère de push-back, ils peuvent revenir en arrière à zéro et réessayer. :)

Mais plus que les accélérations potentielles, cela peut également vous permettre d'écrire des expressions rationnelles qui correspondent exactement à ce dont vous avez besoin. J'ai du mal à trouver un exemple simple :) mais écrire une expression rationnelle en utilisant des quantificateurs possessifs vs gourmands peut vous donner des correspondances différentes, et l'un ou l'autre peut être plus approprié.

ne laissant rien pour satisfaire le "foo" à la fin de l'expression. Utilisez un quantificateur possessif pour les situations où vous voulez saisir tout quelque chose sans jamais reculer ( qu'est-ce que signifie reculer? ); il surclassera

Dans ce contexte, «reculer» signifie «revenir en arrière» - jeter une tentative de correspondance partielle pour essayer une autre correspondance partielle, qui peut ou non réussir.

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 suffisamment détaillée, et je continue d'y revenir. Vous voudrez peut-être le vérifier.

Si vous voulez un niveau plus élevé (explication moins détaillée), pour les expressions régulières simples comme celle que vous regardez, un moteur d'expression régulière fonctionne par retour arrière. Essentiellement, il choisit ("mange") une section de la chaîne et essaie de faire correspondre l'expression régulière à cette section. Si cela correspond, tant mieux. Sinon, le moteur modifie son choix de la section de la chaîne et essaie de faire correspondre l'expression rationnelle avec cette section, et ainsi de suite, jusqu'à ce qu'il ait essayé tous les choix possibles.

Ce processus est utilisé récursivement: 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 morceaux et appliquera l'algorithme à chaque morceau individuellement.

La différence entre les quantificateurs gourmands, réticents et possessifs entre lorsque le moteur fait son choix de la partie de la chaîne à essayer de comparer, et comment 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 au moins, tout ce qui n'a pas déjà été mis en correspondance par les parties précédentes de l'expression régulière) et de vérifier s'il correspond à l'expression rationnelle. Si oui, tant mieux; le moteur peut continuer avec le reste 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 supprime un autre caractère, etc. Un quantificateur gourmand vérifie donc les correspondances possibles dans l'ordre, du plus long au plus court.

• Un quantificateur réticent indique au moteur de démarrer avec le morceau de chaîne le plus court possible. S'il correspond, le moteur peut continuer; sinon, il ajoute un caractère à la section de la chaîne vérifiée et essaie cela, et ainsi de suite jusqu'à ce qu'il trouve une correspondance ou que la chaîne entière ait été utilisé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 à la première tentative: il dit au moteur de démarrer en vérifiant la chaîne entière. 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 examiné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 qu'il correspond, mais le moteur continue ensuite à rechercher des caractères supplémentaires foo- mais bien sûr, il ne les trouve pas, car vous êtes déjà à la fin de la chaîne. S'il s'agissait d'un quantificateur gourmand, il reviendrait en arrière et essaierait de faire la .*seule correspondance jusqu'à l'avant-dernier caractère, puis jusqu'au troisième au dernier caractère, puis jusqu'au quatrième au dernier caractère, qui réussit parce que seulement alors il y a une foogauche après .*avoir "mangé" la première partie de la chaîne.

Voici mon point de vue en utilisant les positions de cellule et d'index (voir le diagramme ici pour distinguer une cellule d'un index).

Gourmand - Correspondre autant que possible au quantificateur gourmand et à toute l'expression régulière. S'il n'y a pas de correspondance, revenez sur le quantificateur gourmand.

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

Le Regex ci-dessus comprend deux parties:
(i) '. *' Et
(ii) 'foo'

Chacune des étapes ci-dessous analysera les deux parties. Les commentaires supplémentaires pour une correspondance avec «réussite» ou «échec» sont expliqués entre accolades.

Étape 1:
(i). * = Xfooxxxxxxfoo - PASS ('. *' Est un quantificateur gourmand et utilisera l'intégralité de la chaîne d'entrée)
(ii) foo = Aucun caractère ne reste après l'index 13 - ÉCHEC La
correspondance a échoué.

Étape 2:
(i). * = Xfooxxxxxxfo - PASS (Retour sur le quantificateur gourmand '. *')
(Ii) foo = o - FAIL
Match a échoué.

Étape 3:
(i). * = Xfooxxxxxxf - PASS (Retour sur le quantificateur gourmand '. *')
(Ii) foo = oo - FAIL
Match a échoué.

Étape 4:
(i). * = Xfooxxxxxx - PASS (Retour sur le quantificateur gourmand '. *')
(Ii) foo = foo - PASS
Report MATCH

Résultat: 1 correspondance (s)
J'ai trouvé le texte "xfooxxxxxxfoo" commençant à l'index 0 et se terminant à l'index 13.

Réticent - Correspond le moins possible au quantificateur réticent et correspond à l'ensemble 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

L'expression rationnelle ci-dessus comprend deux parties:
(i) '. *?' et
(ii) «foo»

Étape 1:.
*? = '' (vide) - PASS (Correspondre aussi peu que possible au quantificateur réticent '. *?'. L'index 0 ayant '' est une correspondance.)
foo = xfo - FAIL (Cellule 0,1,2 - ie index entre 0 et 3) Le
match a échoué.

Étape 2:.
*? = x - PASS (Ajouter des caractères au quantificateur réticent '. *?'. La cellule 0 ayant 'x' est une correspondance.)
foo = foo - PASS
Report MATCH

Étape 3:.
*? = '' (vide) - PASS (Correspondre le moins possible au quantificateur réticent '. *?'. L'index 4 ayant '' est une correspondance.)
foo = xxx - FAIL (Cellule 4,5,6 - ie index entre 4 et 7) Le
match a échoué.

Étape 4:.
*? = x - PASS (Ajouter des caractères au quantificateur réticent '. *?'. Cellule 4.)
foo = xxx - FAIL (Cell 5,6,7 - ie index entre 5 et 8) La
correspondance a échoué.

Étape 5:.
*? = xx - PASS (Ajouter des caractères au quantificateur réticent '. *?'. Cellule 4 à 5.)
foo = xxx - FAIL (Cell 6,7,8 - ie index entre 6 et 9) La
correspondance a échoué.

Étape 6:.
*? = xxx - PASS (Ajouter des caractères au quantificateur réticent '. *?'. Cellule 4 à 6.)
foo = xxx - FAIL (Cellule 7,8,9 - c'est-à-dire index entre 7 et 10) La
correspondance a échoué.

Étape 7:.
*? = xxxx - PASS (Ajouter des caractères au quantificateur réticent '. *?'. Cellule 4 à 7.)
foo = xxf - FAIL (Cell 8,9,10 - c'est-à-dire index entre 8 et 11) La
correspondance a échoué.

Étape 8:.
*? = xxxxx - PASS (Ajouter des caractères au quantificateur réticent '. *?'. Cellule 4 à 8.)
foo = xfo - FAIL (Cell 9,10,11 - c'est-à-dire index entre 9 et 12) La
correspondance a échoué.

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

Étape 10:.
*? = '' (vide) - PASS (correspond le moins possible au quantificateur réticent '. *?'. L'index 13 est vide.)
foo = Aucun caractère ne reste à faire correspondre - FAIL (il n'y a rien après l'index 13 à faire correspondre)
Match échoué.

Résultat: 2 correspondance (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 - Faites correspondre autant que possible le quantifère possessif et faites correspondre le regex entier. Ne reculez PAS.

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

L'expression rationnelle ci-dessus comprend deux parties: '. * +' Et 'foo'.

Étape 1
:. * + = Xfooxxxxxxfoo - PASS (correspondre autant que possible au quantificateur possessif '. *')
Foo = aucun caractère ne reste à faire correspondre - FAIL (rien à faire correspondre après l'index 13) La
correspondance a échoué.

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

Résultat: 0 match (s)

Gourmand: "correspondre à la séquence de caractères la plus longue possible"

Réticent: "correspondre à la séquence de caractères la plus courte possible"

Possessif: C'est un peu étrange car il n'essaye PAS (contrairement aux gourmands et réticents) de trouver une correspondance pour toute l'expression régulière.

Soit dit en passant: aucune implémentation de matcher de motifs regex n'utilisera jamais de retour arrière. Tous les matcher de motifs 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 modèle en 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 la vérification est effectuée à nouveau.

Lorsque seules les conditions principales du modèle d'expression régulière sont satisfaites par la séquence active, une tentative est effectuée pour valider les conditions restantes par rapport à la quarantaine. Si cette validation réussit, les caractères correspondants dans la quarantaine sont validés et les caractères résiduels non correspondants restent non validés et seront utilisés lorsque le processus recommencera lors de l'itération suivante.

Le flux de caractères va de la séquence active à la quarantaine. Le comportement résultant est que la plus grande partie possible de la séquence d'origine est incluse dans une correspondance.

La quantification réticente est essentiellement la même que la qualification gourmande, sauf que le flux de caractères est le contraire - c'est-à-dire qu'ils commencent dans la quarantaine et se jettent dans la séquence active . Le comportement résultant est que le moins possible de la séquence d'origine est incluse dans une correspondance.

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