mieux écrire l'expression regex pour ne pas utiliser la répétition paresseuse quantificateurs

Question

J'ai une expression régulière:

(<select([^>]*>))(.*?)(</select\s*>) 

Comme il utilise quantificateurs de répétition paresseuse, pour les chaînes plus longues (ayant des options plus de 500), il revient en arrière pour plus de 100.000 fois et échoue. S'il vous plaît aidez-moi à trouver une meilleure expression régulière qui n'utilise pas quantificateur de répétition paresseux

Answer 1

<select[^>]*>[^<]*(?:<(?!/select>)[^<]*)*</select> 

... ou sous forme lisible par l'homme:

<select[^>]*> # start tag 
[^<]*   # anything except opening bracket 
(?:    # if you find an open bracket 
    <(?!/select>) # match it if it's not part of end tag 
    [^<]*   # consume any more non-brackets 
)*    # repeat as needed 
</select>  # end tag 

Ceci est un exemple de la technique de "boucle déroulée" que Friedl développe dans son livre, Mastering Regular Expressions. Je l'ai fait un test rapide à RegexBuddy en utilisant un modèle basé sur les quantificateurs réticents:

(?s)<select[^>]*>.*?</select> 

... et il a fallu environ 6 000 mesures pour trouver une correspondance. Le motif à boucle déroulée n'a pris que 500 pas. Et quand j'ai enlevé le support de fermeture de l'étiquette de fin (</select), rendant une correspondance impossible, il a fallu seulement 800 étapes pour signaler une défaillance.

Si votre goût regex soutient quantificateurs possessifs, allez-y et de les utiliser aussi:

<select[^>]*+>[^<]*+(?:<(?!/select>)[^<]*+)*+</select> 

Il faut environ le même nombre d'étapes pour atteindre un match, mais il peut utiliser beaucoup moins de mémoire dans la processus. Et si aucune correspondance n'est possible, elle échoue encore plus rapidement; dans mes tests, il a fallu environ 500 pas, le même nombre que pour trouver un match.

Answer 2

Malheureusement cela ne fonctionne pas, voir la réponse par Alan Moore pour un exemple correct!

(<select([^>]*>))(.*+)(</select\s*>) 

De perl regexp manpage:

Par défaut, lorsqu'un sous-motif quantifié ne permet pas le reste du modèle global pour correspondre, Perl machine arrière. Cependant, ce comportement est parfois indésirable. Ainsi, Perl fournit également la forme de quantificateur "possessive" .

 *+  Match 0 or more times and give nothing back 
     ++  Match 1 or more times and give nothing back 
     ?+  Match 0 or 1 time and give nothing back 
     {n}+ Match exactly n times and give nothing back (redundant) 
     {n,}+ Match at least n times and give nothing back 
     {n,m}+ Match at least n but not more than m times and give nothing back 

Par exemple,

 'aaaa' =~ /a++a/ 

ne correspondra jamais, comme "a ++" gobe tout le d ' "une" dans la chaîne et won n'en laissez aucun pour la partie restante du motif. Cette fonctionnalité peut être extrêmement utile pour donner des indications perl sur l'endroit où ne devrait pas revenir en arrière. Par exemple, le typique « correspondent à une chaîne entre guillemets » problème peut être plus efficacement effectuée lorsque écrit:

 /"(?:[^"\\]++|\\.)*+"/