Quelle est la différence entre .*? et. * expressions régulières?

142

J'essaye de diviser une chaîne en deux parties en utilisant regex. La chaîne est formatée comme suit:

text to extract<number>

J'utilise (.*?)<et <(.*?)>qui fonctionnent bien, mais après avoir lu un peu ?les expressions régulières , j'ai juste commencé à me demander pourquoi j'ai besoin des expressions. Je ne l'ai fait que comme ça après les avoir trouvés sur ce site, donc je ne sais pas exactement quelle est la différence.

Doug
la source

Réponses:

172

C'est la différence entre les quantificateurs gourmands et non gourmands.

Considérez l'entrée 101000000000100.

Utiliser 1.*1, *c'est gourmand - il correspondra jusqu'à la fin, puis reviendra en arrière jusqu'à ce qu'il puisse correspondre 1, vous laissant avec 1010000000001.
.*?n'est pas gourmand. *ne correspondra à rien, mais essaiera ensuite de faire correspondre des caractères supplémentaires jusqu'à ce qu'il corresponde 1, éventuellement 101.

Tous les quantificateurs ont un mode non gourmand: .*?, .+?, .{2,6}?, et même .??.

Dans votre cas, un modèle similaire pourrait être <([^>]*)>- correspondant à tout sauf à un signe supérieur à (à proprement parler, il correspond à zéro ou plus de caractères autres >qu'entre <et >).

Voir la feuille de triche quantificateur .

Kobi
la source
Ah super j'aime ce dernier de tout sauf le signe>!
Doug
1
Pouvez-vous expliquer ou montrer un exemple de la ?différence entre le cupide et le non-gourmand ???
AdrianHHH
4
Sûr. Pour la chaîne "abc", l'expression régulière /\w\w?\w/correspondrait à la chaîne complète "abc"- car elle ?est gourmande. /\w\w??\w/est paresseux - il ne correspondra que "ab". Il ne reviendra et ne correspondra que "abc"s'il échoue plus tard.
Kobi
184

Sur gourmand vs non gourmand

La répétition dans les regex par défaut est gourmande : ils essaient de faire correspondre autant de répétitions que possible, et quand cela ne fonctionne pas et qu'ils doivent revenir en arrière, ils essaient de faire correspondre une répétition de moins à la fois, jusqu'à ce qu'une correspondance du modèle entier soit a trouvé. En conséquence, lorsqu'un match se produit finalement, une répétition gourmande correspondrait à autant de répétitions que possible.

Le ?quantificateur en tant que répétition change ce comportement en non gourmand , aussi appelé réticent ( par exemple en Java ) (et parfois «paresseux»). En revanche, cette répétition essaiera d'abord de faire correspondre le moins de répétitions possible, et lorsque cela ne fonctionne pas et qu'ils doivent revenir en arrière, ils commencent à faire correspondre un répétition de plus à la fois. En conséquence, lorsqu'un match se produit finalement, une répétition réticente correspondrait au moins de répétitions possible.

Références


Exemple 1: de A à Z

Comparons ces deux modèles: A.*Zet A.*?Z.

Compte tenu de l'entrée suivante:

eeeAiiZuuuuAoooZeeee

Les modèles donnent les correspondances suivantes:

Concentrons-nous d'abord sur ce que A.*Zfait. Quand il correspond au premier A, le .*, étant gourmand, essaie d'abord d'en faire correspondre autant .que possible.

eeeAiiZuuuuAoooZeeee
   \_______________/
    A.* matched, Z can't match

Puisque le Zne correspond pas, le moteur revient en arrière et .*doit ensuite correspondre à un de moins .:

eeeAiiZuuuuAoooZeeee
   \______________/
    A.* matched, Z still can't match

Cela se produit encore quelques fois, jusqu'à ce que nous en arrivions finalement à ceci:

eeeAiiZuuuuAoooZeeee
   \__________/
    A.* matched, Z can now match

Maintenant Zpeut correspondre, donc le modèle global correspond:

eeeAiiZuuuuAoooZeeee
   \___________/
    A.*Z matched

En revanche, la répétition réticente dans les A.*?Zpremiers matchs le moins .possible, puis en prenant plus .si nécessaire. Cela explique pourquoi il trouve deux correspondances dans l'entrée.

Voici une représentation visuelle de ce que les deux modèles correspondent:

eeeAiiZuuuuAoooZeeee
   \__/r   \___/r      r = reluctant
    \____g____/        g = greedy

Exemple: une alternative

Dans de nombreuses applications, les deux correspondances dans l'entrée ci-dessus sont ce qui est souhaité, ainsi un réticent .*?est utilisé au lieu du gourmand .*pour éviter un sur-appariement. Pour ce modèle particulier, cependant, il existe une meilleure alternative, en utilisant une classe de caractères inversée.

Le modèle A[^Z]*Ztrouve également les deux mêmes correspondances que le A.*?Zmodèle pour l'entrée ci-dessus ( comme vu sur ideone.com ). [^Z]est ce qu'on appelle une classe de caractères annulée : elle correspond à tout sauf à Z.

La principale différence entre les deux modèles réside dans les performances: étant plus stricte, la classe de caractères annulée ne peut correspondre qu'à une seule manière pour une entrée donnée. Peu importe si vous utilisez un modificateur gourmand ou réticent pour ce modèle. En fait, dans certaines saveurs, vous pouvez faire encore mieux et utiliser ce qu'on appelle le quantificateur possessif, qui ne revient pas du tout.

Références


Exemple 2: De A à ZZ

Cet exemple doit être illustratif: il montre comment les modèles de classe de caractères gourmands, réticents et annulés correspondent différemment avec la même entrée.

eeAiiZooAuuZZeeeZZfff

Voici les correspondances pour l'entrée ci-dessus:

Voici une représentation visuelle de ce à quoi ils correspondent:

         ___n
        /   \              n = negated character class
eeAiiZooAuuZZeeeZZfff      r = reluctant
  \_________/r   /         g = greedy
   \____________/g

Rubriques connexes

Ce sont des liens vers des questions et réponses sur stackoverflow qui couvrent certains sujets susceptibles de vous intéresser.

Une répétition gourmande peut en surpasser une autre

lubrifiants polygènes
la source
1
Je voulais dire rubular.com, pas ideone.com. Aux autres: ne révisez pas ce post pour moi, je le ferai moi-même lors de la prochaine révision, avec d'autres exemples. N'hésitez pas à faire part de vos commentaires, suggestions, etc. dans les commentaires afin que je puisse les intégrer également.
polygenelubricants
2
Voir aussi: stackoverflow.com/questions/3145023/…
polygenelubricants
4
Cette réponse a été ajoutée à la FAQ sur les expressions régulières Stack Overflow , sous "Quantificateurs> En savoir plus sur les différences ..."
aliteralmind
Cette réponse mérite vraiment d'être la réponse choisie !. Merci beaucoup pour votre explication détaillée.
masky007
J'ai ajouté le tag non gourmand . Pourquoi, parce que la question en avait besoin, mais aussi parce qu'elle redirigera davantage d'utilisateurs vers cette excellente réponse. En d'autres termes, si vous donnez une bonne réponse et que la réponse utilise une balise qui ne figure pas dans la question, ajoutez la balise car l'OP ne savait pas que la balise était révélatrice.
Guy Coder
21

Disons que vous avez:

<a></a>

<(.*)>correspondrait a></a<(.*?)>correspondrait a. Ce dernier s'arrête après le premier match de >. Il recherche une ou 0 correspondance de .*suivi de l'expression suivante.

La première expression <(.*)>ne s'arrête pas lors de la correspondance avec la première >. Il continuera jusqu'au dernier match de >.

Simon
la source
c'est plus facile à comprendre que l'explication ci-dessus.
Prometheus