Escribir una mejor expresión de expresiones regulares para no usar perezoso repetición cuantificador

Question

tengo una expresión regular:

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

Dado que se usa cuantificador de repetición perezoso, para las cadenas más largas (con opciones más de 500) que da marcha atrás a más de 100.000 veces y falla Ayúdeme a encontrar una mejor expresión regular que no utilice el cuantificador de repetición perezoso

Answer 1

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

... o en forma legible por humanos:

<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 

Este es un ejemplo de la técnica de "ciclo desenrollado" que Friedl desarrolla en su libro, Mastering Regular Expressions. Hice una prueba rápida en RegexBuddy usando un modelo basado en los cuantificadores reacios:

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

... y tardó unos 6.000 pasos para encontrar una coincidencia. El patrón desenrollado-bucle tomó solo 500 pasos. Y cuando eliminé el soporte de cierre de la etiqueta de cierre (</select), imposibilitando una coincidencia, solo requirió 800 pasos para informar la falla.

Si su sabor expresión regular compatible con cuantificadores posesivos, seguir adelante y utilizarlos, también:

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

Se tarda aproximadamente el mismo número de pasos para lograr una coincidencia, pero se puede utilizar mucho menos memoria en el proceso. Y si no es posible una coincidencia, falla aún más rápidamente; en mis pruebas tomó alrededor de 500 pasos, el mismo número que tardó en encontrar una coincidencia.

Answer 2

Lamentablemente, esto no funcionará, consulte la respuesta de Alan Moore para obtener un ejemplo correcto.

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

Desde la página de manual de Perl expresiones regulares:

Por defecto, cuando un sub-patrón cuantificado no permite que el resto del patrón general a la altura, Perl dar marcha atrás. Sin embargo, este comportamiento es a veces indeseable. Por lo tanto, Perl también proporciona el cuantificador "posesivo" .

 *+  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 

Por ejemplo,

 'aaaa' =~ /a++a/ 

nunca coinciden, como el "A ++" será engullir toda la "a" 's en la cadena y ganó no deje ninguno para la parte restante del patrón. Esta característica puede ser extremadamente útil para dar pistas sobre dónde no debe retroceder. Por ejemplo, el típico "coinciden con un cadena entre comillas dobles" problema puede llevar a cabo de manera más eficiente cuando se escribe como:

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