Quantificateurs cupides vs. réticents vs. possessifs
j'ai trouvé ce 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 trou sérieux 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 manger toute la chaîne de caractères, lettres été consommé , matcher backing off , l'occurrence la plus à droite de" foo "a été regurgité , 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 façon concise) comment les moteurs d'expressions régulières fonctionnent?
par ailleurs, si quelqu'un peut expliquer dans un libellé quelque peu différent le paragraphe suivant, cela soyez très apprécié:
Le premier exemple utilise le gourmand quantificateur. * pour trouver "quelque chose", zéro ou plusieurs fois, suivi par les lettres "f ""o"o". Parce que le quantificateur est gourmande, la .* la partie de la l'expression mange d'abord toute l'entrée chaîne. À ce stade, l'ensemble de la l'expression ne peut pas réussir, parce que le trois dernières lettres ("f" "o" "o") ont déjà consommé ( par qui? ). Donc le matcher lentement sauvegarde ( de droite à gauche? ) une lettre à la fois jusqu'à l'apparition de l'extrême droite "foo" a été régurgité ( qu'est-ce que cela signifie? ), à laquelle point le match réussit et le la recherche se termine.
Le deuxième exemple, cependant, est réticent, donc il commence par consommant ( par qui? ) "rien". Parce que "foo" n'apparaît pas au début de la chaîne, il est forcé de hirondelle ( qui hirondelles?) le première lettre (un "x"), qui déclenche le premier match à 0 et 4. Notre test harnais continue le processus jusqu'à ce que la chaîne de saisie est épuisée. Il trouve une autre correspondance à 4 et 13.
le troisième exemple ne trouve pas match parce que le quantificateur est possessif. Dans ce cas, l'ensemble de la chaîne d'entrée est consommée par .* + , ( comment? ) ne laissant rien pour satisfaire le "foo" à la fin de la expression. Utiliser un possessif quantificateur pour les situations où vous veulent saisir tout de quelque chose sans jamais reculer ( que signifie "reculer"? ); il sera plus performant l'équivalent gourmand quantificateur dans les cas où le match n'est pas immédiatement trouvé.
7 réponses
je vais essayer.
Un gourmand quantificateur premiers matchs autant que possible. Donc le .* correspond à la chaîne entière. Puis le matcher essaye de faire correspondre le f suivant, mais il n'y a plus de caractères. Ainsi, il "backtracks", ce qui rend le quantificateur gourmand match une chose de moins (laissant le" o " à la fin de la chaîne inégalée). Cela ne correspond toujours pas au f dans le regex, donc il "retrace" un plus de pas, faisant correspondre le quantificateur gourmand une chose de moins (laissant le" oo " à la fin de la chaîne inégalée). Que still ne correspond pas au f dans le regex, il recule donc d'un pas de plus (laissant le "foo" à la fin de la chaîne inégalée). Maintenant, le matcher correspond finalement au f dans le regex, et le o et le suivant o sont assortis aussi. Succès!
A réticent ou "non-greedy" quantificateur premiers matchs aussi peu que possible. Donc le .* ne correspond à rien au début, laissant la chaîne entière inégalée. Ensuite, l'apparieur essaie de faire correspondre le f suivant, mais la partie non appariée de la chaîne commence par "x" de sorte que cela ne fonctionne pas. Donc le matcher recule, faisant correspondre le quantificateur non-gourmand à une chose de plus (maintenant il correspond au "x", laissant "fooxxxxxxfoo" inégalé). Puis il essaie de faire correspondre le f , qui réussit, et le o et le suivant o dans le match regex aussi. Succès!
dans votre exemple, il démarre alors le processus avec la partie restante non appariée de la chaîne, en suivant le même processus.
A possessive quantifierest exactement comme le quantificateur cupide, mais il ne recule pas. Donc ça commence avec .* correspondant à toute la chaîne, ne laissant rien d'inégalé. Ensuite, il ya il ne reste plus rien pour qu'il corresponde au f dans le regex. Comme le quantificateur possessif ne recule pas, le match échoue.
Je n'ai jamais entendu les termes exacts "regurgitate" ou "backtracking" avant; la phrase qui remplacerait ceux-ci est "backtracking", mais "regurgitate"semble comme une bonne phrase comme n'importe quel pour" le contenu qui avait été accepté provisoirement avant de backtracking jeté loin à nouveau".
la chose importante à réaliser sur la plupart des moteurs regex est qu'ils sont retracing : ils seront provisoirement accepter un potentiel, correspondance partielle, tout en essayant de faire correspondre tout le contenu du regex. Si le regex ne peut pas être complètement apparié à la première tentative, alors le moteur regex sera backtrack sur l'un de ses matchs. Il va essayer de correspondance * , + , ? , l'alternance, ou {n,m} répétition différemment, et essayez à nouveau. (Et oui, ce processus de peut prendre du temps.)
le premier exemple utilise la gourmande quantificateur. * pour trouver "quelque chose", zéro ou plusieurs fois, suivi par les lettres "f ""o"o". Parce que le quantificateur est gourmande, la .* la partie de la l'expression mange d'abord toute l'entrée chaîne. À ce stade, l'ensemble de la l'expression ne peut pas réussir, parce que le trois dernières lettres ("f" "o" "o") ont déjà consommé ( par qui? ).
les trois dernières lettres, f , o , et o ont déjà été consommés par la partie initiale .* de la règle. Cependant, l'élément suivant dans le regex, f , n'a plus rien dans la chaîne de saisie. Le moteur sera forcé de backtrack sur son match initial .* , et essayer de faire correspondre tout-sauf-le-dernier caractère. (Il pourrait être smart et revenir en arrière pour tous-mais-le-dernier-trois, parce qu'il a trois sens littéral du terme, mais je suis pas au courant des détails de mise en œuvre à ce niveau.)
de Sorte que le matcher lentement sauvegarde ( de droite à gauche? ) une lettre à la fois jusqu'à l'apparition de l'extrême droite "foo" a été régurgité ( qu'est-ce que cela signifie? ), auquel
cela signifie que le foo avait provisoirement y compris lors de l'appariement .* . Parce que cette tentative a échoué, le regex le moteur essaie d'accepter un caractère de moins dans .* . S'il y avait eu une correspondance réussie avant le .* dans cet exemple, alors le moteur essaierait probablement de raccourcir la correspondance .* (de droite à gauche, comme vous l'avez souligné, parce que c'est un qualificatif gourmand), et s'il était incapable de correspondre à l'ensemble des entrées, alors il pourrait être forcé de réévaluer ce qu'il avait correspondu avant le .* dans mon hypothétique exemple.
point le match réussit et le la recherche se termine.
Le deuxième exemple, cependant, est réticent, donc il commence par consommant ( par qui? ) "rien". Parce que " foo "
La première, rien n'est consommé par .?* , qui va consommer le plus possible le montant de tout ce qui permet au reste de la regex de match.
n'apparaît pas au début de la string, il est forcé d'avaler ( qui avale?) le
encore une fois le .?* consomme le premier caractère, après un retour en arrière sur l'échec initial de faire correspondre l'ensemble de la regex avec la plus courte correspondance possible. (Dans ce cas, le moteur regex prolonge de gauche à droite le match pour .*? , car .*? est réticent.)
première lettre (un "x"), qui déclenche le premier match à 0 et 4. Notre test harnais continue le processus jusqu'à ce que la chaîne de saisie est épuisée. Il trouve une autre correspondance à 4 et 13.
le troisième exemple ne trouve pas match parce que le quantificateur est possessif. Dans ce cas, l'ensemble de la chaîne d'entrée est consommée par .*+, ( comment? )
Un .*+ sera consommez autant que possible, et ne reculera pas pour trouver de nouveaux matchs lorsque le regex dans son ensemble ne parvient pas à trouver une correspondance. Parce que la forme possessive n'effectue pas de retracking, vous ne verrez probablement pas beaucoup d'utilisations avec .*+ , mais plutôt avec des classes de caractères ou des restrictions similaires: account: [[:digit:]]*+ phone: [[:digit:]]*+ .
cela peut accélérer considérablement la correspondance regex, parce que vous dites au moteur regex qu'il ne devrait jamais revenir en arrière sur le potentiel les matchs si une entrée ne correspond pas. (Si vous deviez écrire tout le code correspondant à la main, ce serait similaire à ne jamais utiliser putc(3) pour 'repousser' un caractère d'entrée. Ce serait très similaire au Code naïf qu'on pourrait écrire à la première tentative. Sauf que les moteurs regex sont bien meilleurs qu'un simple caractère de push-back, ils peuvent rembobiner tout le retour à zéro et essayer à nouveau. :)
mais plus que des speed ups potentiels, cela peut aussi vous permettre d'écrire des regex qui correspondent exactement ce que vous devez faire correspondre. J'ai du mal à trouver un exemple simple :) mais écrire un regex en utilisant des quantificateurs possessifs vs gourmands peut vous donner des correspondances différentes, et l'un ou l'autre peut être plus approprié.
laissant rien pour satisfaire le "toto" à la fin de la expression. Utiliser un possessif quantificateur pour les situations où vous veulent saisir tout de quelque chose sans que signifie "reculer"? ); il sera plus performant
"Backup" dans ce contexte signifie "backtracking" -- jeter un match partiel de tentative pour essayer un autre match partiel, qui peut ou ne peut pas réussir.
l'équivalent gourmand quantificateur dans les cas où le match n'est pas immédiatement trouvé.
http://swtch.com/~rsc/regexp/regexp1.html
Je ne suis pas sûr que ce soit la meilleure explication sur internet, mais c'est raisonnablement bien écrit et suffisamment détaillé, et je n'arrête pas d'y revenir. Vous pourriez vouloir vérifier.
si vous voulez un niveau plus élevé (explication moins détaillée), pour des expressions régulières simples comme celle que vous regardez, un moteur d'expression régulière fonctionne en faisant marche arrière. Essentiellement, il choisit ("mange") une section de la chaîne et tente de faire correspondre l'expression régulière avec cette section. Si elle correspond, grand. Si ce n'est pas le cas, le moteur modifie son choix de la section de la corde et tente de faire correspondre la regexp à cette section, et ainsi de suite, jusqu'à ce qu'il ait essayé 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 va diviser l'expression régulière en morceaux et appliquer l'algorithme à chaque pièce individuellement.
la différence entre les quantificateurs gourmands, réticents et possessifs entre quand le moteur fait ses choix de quelle partie de la chaîne essayer de faire match contre, et comment modifier ce choix si elle ne fonctionne pas la première fois. Les règles sont les suivantes:
-
un quantificateur gourmand demande au moteur de démarrer avec la chaîne entière (ou à au moins, tout ce qui n'a pas déjà été comparé avec les parties précédentes de l'expression régulière) et vérifiez si cela correspond au regexp. Si oui, les grands, le moteur peut continuer avec le reste de la regexp. Si ce n'est pas le cas, il essaie de nouveau, mais en coupant un caractère (le dernier) de la section de la chaîne à cocher. Si cela ne fonctionne pas, cela enlève un autre caractère, etc. Donc un quantificateur gourmand vérifie les correspondances possibles dans l'ordre de la plus longue à la plus courte.
-
un quantificateur réticent dit au moteur de démarrer avec le plus court morceau possible de la corde. S'il correspond, le moteur peut continuer; si non, il ajoute un caractère à la section de la chaîne cochée et essaye cela, et ainsi de suite jusqu'à ce qu'il trouve une correspondance ou la chaîne entière a été utilisée. Donc un quantificateur réticent vérifie les correspondances possibles dans l'ordre de la plus courte à la plus longue.
-
Un possessif quantifierest comme un quantificateur gourmand à la première tentative: il indique au moteur de démarrer en vérifiant la chaîne entière. La différence est que si ça ne marche pas, le quantificateur possessif signale que le match a échoué à ce moment-là. Le moteur ne change pas la section de la corde à regarder, et il ne fait plus aucune tentative.
C'est pourquoi le match possessif quantificateur échoue dans votre exemple: le .*+ obtient vérifié par rapport à la chaîne entière, qui correspond, mais ensuite le moteur continue à chercher des caractères supplémentaires foo après cela - mais bien sûr, il ne les trouve pas, parce que vous êtes déjà à la fin de la chaîne. S'il s'agissait d'un quantificateur gourmand, il ferait marche arrière et essaierait de faire correspondre le .* au caractère suivant-à-la-dernière, puis au troisième au dernier caractère, puis au quatrième au dernier caractère, ce qui réussit parce qu'il n'y a qu'alors un foo à gauche après le .* a "mangé" la partie antérieure de la chaîne.
voici ma prise en utilisant les positions de la cellule et de L'Index (voir le diagramme ici pour distinguer une cellule d'un Index).
Gourmand - Match, autant que possible, à cause de la cupidité des quantificateurs et de l'ensemble de la regex. S'il n'y a pas de correspondance, retournez sur le quantificateur cupide.
chaîne de saisie: xfooxxxxxxfoo
Regex: .*foo
ci-dessus Regex a deux parties:
(je.')* "et
ii) "foo'
Chacune des étapes ci-dessous analysera les deux parties. Les commentaires supplémentaires pour une correspondance à 'réussite' ou' échec ' sont expliqués dans les accolades.
Étape 1:
(je. )* = xfooxxxxxxfoo-PASS ('.*' être une gourmande quantificateur, et d'utiliser la totalité de la Chaîne d'Entrée)
(ii) foo = Pas de caractère à la gauche du match après l'indice 13 - ÉCHEC
Match n'a pas.
Étape 2:
(je. )* = xfooxxxxxxfo - PASS (de revenir sur les gourmand quantificateur '.* ')
(ii) foo = o - ÉCHEC
Match n'a pas.
Étape 3:
(je. )* = xfooxxxxxxf - PASS (de revenir sur les gourmand quantificateur '.* ')
(ii) foo = oo - ÉCHEC
Match n'a pas.
Étape 4:
(je. )* = xfooxxxxxx - PASS (de revenir sur les gourmand quantificateur '.* ')
II) foo = foo-PASS
MATCH du rapport
résultat: 1 match(s)
J'ai trouvé le texte "xfooxxxxxxfoo" qui commence à l'index 0 et se termine au niveau de l'index 13.
match de résistance aussi peu que possible au quantificateur de résistance et match l'ensemble du regex. s'il n'y a pas de correspondance, ajouter des caractères au quantificateur réticent.
Chaîne d'Entrée: xfooxxxxxxfoo
Regex: .*?foo
le regex ci-dessus a deux parties:
(je.' )*?' et
ii) " foo
Étape 1:
.*? = " (vide) - PASS (Match aussi peu que possible pour les réticents quantificateur '.*?'. Indice 0 ayant " est un match.)
foo = xfo-FAIL (cellule 0,1,2-I. E indice entre 0 et 3)
Match n'a pas.
Étape 2:
.*? = X-PASS (ajouter des caractères à la valeur quantificateur.' *?'. Cellule 0 ayant " x " est une correspondance.)
foo = foo-PASS
MATCH du rapport
Étape 3:
.*? = " (vide) - PASS (Match aussi peu que possible pour les réticents quantificateur '.*?'. Index 4 Avoir " est une correspondance.)
foo = xxx-FAIL (cellule 4,5,6-I. E indice entre 4 et 7)
Match n'a pas.
Étape 4:
.*? = X-PASS (ajouter des caractères au quantificateur réticent '.*?'. Cellule 4.)
foo = xxx-FAIL (cellule 5,6,7-I. E indice entre 5 et 8)
Match n'a pas.
Étape 5:
.*? = xx-PASS (ajouter des caractères au quantificateur réticent '.*?'. Cellule 4 à 5.)
foo = xxx-FAIL (Cellule 6,7,8-I. E indice entre 6 et 9)
Match n'a pas.
Étape 6:
.*? = xxx-PASS (ajouter des caractères au quantificateur réticent '.*?'. Cellule 4 à 6.)
foo = xxx-FAIL (cellule 7,8,9-I. E indice entre 7 et 10)
Match n'a pas.
Étape 7:
.*? = xxxx-PASS (ajouter des caractères à les réticents quantificateur '.*?'. Cellule 4 à 7.)
foo = xxf-FAIL (cellule 8,9,10-I. E indice entre 8 et 11)
Match n'a pas.
Étape 8:
.*? = xxxxx-PASS (ajouter des caractères au quantificateur réticent '.*?'. Cellule 4 à 8.)
foo = xfo-FAIL (cellule 9,10,11-I. E indice entre 9 et 12)
Match n'a pas.
Étape 9:
.*? = xxxxxx-PASS (ajouter des caractères au quantificateur réticent '.*?'. Cellule 4 à 9.)
foo = foo-PASS(cellule 10,11,12-I. E indice entre 10 et 13)
MATCH du rapport
Étape 10:
.*? = " (vide) - PASS (Match aussi peu que possible pour les réticents quantificateur '.*?'. L'Index 13 est vide.)
foo = Pas de caractère à la gauche du match de l'ÉCHEC (Il n'y a rien après l'indice 13 pour match)
Match n'a pas.
résultat: 2 match(s)
J'ai trouvé le texte "xfoo" commençant à l'index 0 et se terminant à l'indice 4.
J'ai trouvé le texte "xxxxxxfoo" commençant à l'index 4 et se terminant à l'indice 13.
Possessif - Correspondre autant que possible à l' quantifer possessif et correspondre à tout le regex. Ne PAS faire marche arrière.
Chaîne d'Entrée: xfooxxxxxxfoo
Regex: .* + foo
le regex ci-dessus a deux parties:".*+' et 'foo'.
Étape 1:
.*+ = xfooxxxxxxfoo-PASS (correspond autant que possible au quantificateur possessif".* ')
foo = Pas de le caractère à la gauche de match - FAIL (Rien de match après l'indice 13)
Match n'a pas.
Note: le retraçage n'est pas autorisé.
résultat: 0 match(es)
Gourmand: "le match le plus longtemps possible de la séquence de caractères"
Réticents: "le match le plus rapidement possible de la séquence de caractères"
Possessive: c'est un peu étrange car elle ne cherche pas (contrairement à avide et réticente) à trouver une correspondance pour l'ensemble du regex.
soit dit en passant: aucune implémentation regex pattern matcher n'utilisera jamais de backtracking. Tous les modèles de la vie réelle matcher sont extrêmement rapide - presque indépendant de la complexité de l'expression régulière!
Greedy Quantification implique l'appariement des motifs en utilisant tous les caractères non validés restants d'une chaîne de caractères au cours d'une itération. Les caractères non validés débutent 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 seules les conditions principales du modèle regex sont remplies par les conditions actives séquence, une tentative est faite pour valider les conditions restantes contre la quarantaine. Si cette validation est réussie, les caractères appariés de la quarantaine sont validés et les caractères restants non appariés demeurent non validés et seront utilisés lorsque le processus commencera à nouveau dans la prochaine itération.
le flux de caractères est de la séquence active dans la quarantaine. Le comportement résultant est que la plus grande partie de la séquence originale est incluse dans une correspondance aussi possible.
"la Quantification hésitante est la plupart du temps la même que la qualification avide sauf que le flux de caractères est le contraire--c'est-à-dire qu'ils commencent dans la quarantaine et s'écoulent dans la séquence active . Le comportement résultant est qu'aussi peu de la séquence originale est incluse dans une correspondance que possible.
Quantification Possessive n'a pas de quarantaine et comprend tout dans une séquence active fixe .