Cupides vs réticents vs quantificateurs possessifs

Question

J'ai trouvé cet excellent tutoriel sur les expressions régulières et alors que je intuitivement comprendre ce qu'est "gourmand", "réticents" et "possessif" quantificateurs faire, 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 des mentions de manger l'ensemble de la chaîne d'entrée, des lettres d'été consommé, comparateur de sauvegarde, de droite occurrence de "foo" a été régurgité, etc.

Malheureusement, en dépit de la belle 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 expressions régulières fonctionnent les moteurs?

Sinon, si quelqu'un peut expliquer un peu différent du phrasé, de l'alinéa suivant, qui serait bien apprécié:

Le premier exemple utilise le gourmand quantificateur .* afin de trouver "quelque chose", zéro ou plusieurs fois, suivi par les lettres "f" "o" "o". Parce que le quantificateur est gourmand, le .* partie de la d'abord l'expression mange l'ensemble de l'entrée chaîne de caractères. À 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à été consommée (par qui?). Ainsi, le matcher lentement s'éloigne (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?), à qui point du match réussit et le la recherche se termine.

Le deuxième exemple, cependant, est réticent, il commence d'abord par consommer (par qui?) "rien". Parce que "foo" n'apparaît pas au début de la chaîne, il est forcé d'avaler (qui avale?) l' 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 d'entrée est épuisé. Il trouve un autre match à 4 et 13.

Le troisième exemple, ne parvient pas à trouver un match parce que le quantificateur est possessif. Dans ce cas, l'ensemble de la chaîne d'entrée est consommé .*+, (comment?) ne laissant rien pour satisfaire le "toto" à la fin de la de l'expression. Utiliser un possessif quantificateur pour les situations où vous voulez vous emparer de tous quelque chose sans jamais la sauvegarde (ce qui n'back off veux dire?); il sera mieux l'équivalent gourmand quantificateur dans les cas où le match n'est pas immédiatement trouvé.

Answer 1

Je vais donner un coup de feu.

Une gourmande quantificateur premiers matchs autant que possible. Si l' .* correspond à l'ensemble de la chaîne. Puis le comparateur essaie de faire correspondre l' f suivants, mais il n'y a pas de caractères à gauche. Donc, il "revient", faire le gourmand quantificateur correspondre à une chose de moins (en laissant le "o" à la fin de la chaîne inégalée). N'est toujours pas correspondre à l' f dans l'expression régulière, de sorte qu'il "revient" un pas de plus, en faisant le gourmand quantificateur correspondre à une chose de moins à nouveau (en laissant le "oo" à la fin de la chaîne inégalée). Qui encore ne correspond pas à l' f dans l'expression régulière, de sorte qu'il revient d'un pas de plus (en laissant le "toto" à la fin de la chaîne inégalée). Maintenant, le matcher correspond finalement l' f dans la regex, et l' o et du prochain o sont jumelés. Succès!

Un réticents ou "non-greedy" quantificateur premiers matchs aussi peu que possible. Si l' .* correspond à rien à la première, laissant l'ensemble de la chaîne inégalée. Puis le comparateur essaie de faire correspondre l' f suivants, mais l'incomparable partie de la chaîne de caractères commence par un "x" si cela ne fonctionne pas. Ainsi, le comparateur de revient, faisant de la non-greedy quantificateur match encore une chose (maintenant, il correspond à "x", laissant "fooxxxxxxfoo" inégalée). Puis il essaie de faire correspondre l' f, ce qui réussit, et l' o et du prochain o dans la regex match de trop. Succès!

Dans votre exemple, il commence alors le processus avec le reste inégalée partie de la chaîne, en suivant le même processus.

Un possessif quantificateur est comme le gourmand quantificateur, mais il ne veut pas revenir en arrière. Donc ça commence avec .* correspondant à la totalité de la chaîne, ne laissant rien inégalée. Ensuite, il ne reste rien pour elle pour la faire correspondre avec l' f dans la regex. Depuis le possessif quantificateur ne pas revenir en arrière, le match ne parvient pas là.

Answer 2

Je n'ai pas entendu les termes exacts de "régurgiter" ou "reculer" avant; l'expression à remplacer ces "retours en arrière", mais "régurgiter" semble aussi bon qu'une phrase comme tout pour "le contenu qui avait été provisoirement acceptée avant de mandature a jeté de nouveau".

La chose importante à réaliser sur la plupart des regex moteurs est qu'ils sont de retours en arrière: ils seront provisoirement accepter un potentiel, correspondance partielle, tout en essayant de correspondre à la totalité du contenu de la regex. Si la regex ne peut pas être complètement correspondait à la première tentative, puis le moteur d'expressions régulières permettra de revenir en arrière sur l'un de ses matches. Il va essayer de correspondance *, +, ?, alternance, ou {n,m} répétition différemment, et essayez à nouveau. (Et oui, ce processus peut prendre un certain temps.)

Le premier exemple utilise le gourmand quantificateur .* afin de trouver "quelque chose", zéro ou plusieurs fois, suivi par les lettres "f" "o" "o". Parce que le quantificateur est gourmand, le .* partie de la d'abord l'expression mange l'ensemble de l'entrée chaîne de caractères. À 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à été consommée (par qui?).

Les trois dernières lettres, f, o, et o ont déjà consommé par le premier .* partie de la règle. Cependant, l'élément suivant dans la regex, f, n'a rien laissé dans la chaîne d'entrée. Le moteur sera forcé de revenir sur ses premières .* match, et essayer de faire correspondre tous-mais-le-dernier caractère. (Il pourrait être intelligent 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.)

Ainsi, le matcher lentement s'éloigne (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?), à qui

Cela signifie que l' foo avait provisoirement été, y compris lors de l'appariement .*. Parce que l'échec de cette tentative, le moteur d'expressions régulières essaie d'accepter moins de caractère en .*. S'il y avait eu un match de succès avant l' .* dans cet exemple, le moteur serait probablement essayer de raccourcir le .* match (de droite à gauche, comme vous l'avez souligné, parce que c'est un gourmand qualifier), et si elle était incapable de répondre à l'ensemble des entrées, alors il pourrait être forcé de réévaluer ce qu'il avait été à la hauteur avant de l' .* dans mon exemple hypothétique.

point du match réussit et le la recherche se termine.

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

La première, rien n'est consommé par .?*, ce 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 chaîne, il est forcé d'avaler (qui avale?) l'

De nouveau l' .?* consomme le premier caractère, après de revenir sur l'échec initial pour correspondre à l'ensemble de la regex avec la plus courte possible. (Dans ce cas, le moteur d'expressions régulières est d'étendre le match pour .*? à partir de la gauche-à-droite, parce qu' .*? est réticent à le faire.)

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 d'entrée est épuisé. Il trouve un autre match à 4 et 13.

Le troisième exemple, ne parvient pas à trouver un match parce que le quantificateur est possessif. Dans ce cas, l'ensemble de la chaîne d'entrée est consommé .*+, (comment?)

Un .*+ consomment autant que possible, et ne sera pas revenir en arrière pour trouver de nouveaux matches lors de la regex ne parvient pas à trouver une correspondance. Parce que la forme possessive de ne pas effectuer de retour en arrière, vous n'aurez probablement pas voir de nombreuses utilisations avec .*+, mais plutôt avec des classes de personnages ou des restrictions semblables: account: [[:digit:]]*+ phone: [[:digit:]]*+.

Cela peut considérablement accélérer les regex correspondance, parce que vous dites que le moteur d'expressions régulières qu'il ne faut jamais revenir en arrière sur les correspondances possibles si une entrée ne correspond pas. (Si vous aviez à écrire tout le code correspondant à la main, ce serait semblable à jamais l'aide d' putc(3) 'repousser' une entrée de caractères. Il serait très semblable à de la naïveté de code on peut écrire sur un premier essai. Sauf regex moteurs sont bien meilleur que d'un seul caractère de push-back, ils peuvent rewind toutes les remises à zéro et essayer de nouveau. :)

Mais plus que le potentiel de vitesse de l'onduleur, cela peut aussi vous permettent d'écrire des regexs qui correspondent exactement ce dont vous avez besoin pour correspondre. Je vais avoir du mal à trouver un exemple facile :) mais l'écriture d'une expression régulière en utilisant possessif vs gourmand quantificateurs peuvent vous donner des matches différents, et l'un ou l'autre peut être plus approprié.

ne laissant rien pour satisfaire le "toto" à la fin de la de l'expression. Utiliser un possessif quantificateur pour les situations où vous voulez vous emparer de tous quelque chose sans jamais la sauvegarde (ce qui n'back off veux dire?); il sera mieux

"La sauvegarde" dans ce contexte signifie "retour en arrière" -- jeter une tentative de correspondance partielle d'essayer une autre correspondance partielle, qui peut ou peut ne pas réussir.

l'équivalent gourmand quantificateur dans les cas où le match n'est pas immédiatement trouvé.

Answer 3

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

Je ne suis pas sûr que la meilleure explication sur l'internet, mais c'est assez bien écrit et suffisamment détaillé, et je reviens toujours à elle. Vous pourriez vouloir vérifier.

Si vous voulez un plus haut niveau (moins l'explication détaillée), pour les expressions régulières simples comme celui que vous êtes en train de regarder, un moteur d'expression régulière œuvres par les retours en arrière. Essentiellement, il choisit ("mange"), une section de la corde et tente de faire correspondre l'expression régulière à l'encontre de cette section. Si elle correspond, grand. Si pas, le moteur modifie son choix de la section de la corde et tente de faire correspondre les regexp à l'encontre de cette section, et ainsi de suite, jusqu'à ce qu'il est essayé de chaque choix possible.

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 pour chaque pièce individuellement.

La différence entre le gourmand, réticents, et les quantificateurs possessifs entre quand le moteur est son choix de quelle partie de la chaîne à essayer de faire correspondre, et comment modifier ce choix si cela ne fonctionne pas la première fois. Les règles sont comme suit:

• Une gourmande quantificateur indique au moteur de démarrer avec l' ensemble de la chaîne (ou au moins, tout ce qui n'a pas déjà été appariés par les parties précédentes de l'expression régulière) et vérifier qu'il correspond à l'expression rationnelle. Si oui, les grands, le moteur peut continuer avec le reste de la regexp. Si pas, il essaie à nouveau, mais le parage d'un caractère (la dernière) au large de la section de la chaîne à être vérifié. Si cela ne fonctionne pas, il retire un autre personnage, etc. Ainsi, un gourmand quantificateur vérifie les correspondances possibles dans l'ordre de la plus longue à la plus courte.

• Un peu réticents quantificateur indique au moteur de démarrer avec la plus courte possible morceau de la chaîne. Si elle correspond, le moteur peut continuer; sinon, il ajoute un caractère à la section de la chaîne en cours de vérification et qui tente, et ainsi de suite jusqu'à ce qu'il trouve une correspondance ou la totalité de la chaîne a été utilisé. Donc un peu réticents quantificateur vérifie les correspondances possibles dans l'ordre, de la plus courte à la plus longue.

• Un possessif quantificateur est comme une gourmande quantificateur à la première tentative: il indique au moteur à commencer par la vérification de l'ensemble de la chaîne. La différence est que si ça ne fonctionne pas, le possessif quantificateur rapports que le match n'a pas à droite, puis et là. Le moteur ne change pas la section de la chaîne d'être regardé, et il ne faut pas faire plus de tentatives.

C'est pourquoi le possessif quantificateur match échoue dans votre exemple: l' .*+ obtient vérifié par rapport à l'ensemble de la chaîne, à laquelle elle correspond, mais le moteur continue de chercher de nouveaux personnages foo - mais bien sûr, il ne les trouve pas, parce que vous êtes déjà à la fin de la chaîne. Si c'était un gourmand quantificateur, il serait revenir en arrière et essayer de faire le .* seulement correspondre à l'avant-dernier caractère, puis jusqu'à la troisième à la dernière lettre, puis jusqu'à la quatrième à la dernière lettre, qui réussit, car alors seulement est-il un foo à gauche après l' .* a "mangé" la partie antérieure de la chaîne.

Answer 4

Gourmand : « correspond à la plus longue séquence possible de caractères »

Réticents : « correspond à la plus courte séquence possible de caractères »

Possessif : C’est un peu étrange comme il le fait pas (contrairement aux gourmands et réticents) essayer de trouver une correspondance pour l’expression régulière ensemble.

Soit dit en passant : aucune implémentation de matcher du modèle regex n’utilisera jamais revenir en arrière. Tous les matcher de modèle de la vie réelle sont extrêmement rapide - pratiquement indépendante de la complexité de l’expression régulière !