Actualmente estoy investigando el problema de las expresiones regulares que pueden acabar ejecutándose en tiempo exponencial cuando se comparan con una entrada determinada, por ejemplo, (a*)* y muestran potencialmente 'catastrophic backtracking' cuando coinciden con la cadena aaaaab - por cada ' 'en la secuencia combinada, el tiempo necesario para intentar hacer coincidir la secuencia se duplica. Este es solo el caso si el motor utiliza un enfoque de retroceso/NFA de intentar probar todas las ramas posibles en el árbol antes de fallar, como el utilizado en PCRE.Regex (a?) * No exponencial?
Mi pregunta es, ¿por qué no es (a?)* vulnerable? De acuerdo con mi conocimiento de retroceder, lo que debería pasar en la cadena "aaaab" es esencialmente lo que ocurre con (a|a)*. Si construimos el NFA usando la construcción estándar de Thomspson NFA, seguramente para cada transición épsilon que ocurra, el motor tendrá que seguir tomándolos y retrocediendo de la misma forma que lo haría en el caso de dos a's. Por ejemplo (omitiendo algunos pasos y donde reemplaza @ épsilon):
partidos "aaaa", pero no puede coincidir con 'b', FAIL (retroceso)
"aaaa @" de los partidos, 'b' fallar (retroceso)
"aaa @ a" partidos, 'b' fallar (retroceso)
"aaa @ un @" coincide, 'b' fallar (retroceso)
...
"@ un @ un @ un @ un @ "partidos, 'b' falla (retrocede)
tratando todas las posibles combinaciones de épsilon y a, lo que seguramente conduce a una explosión exponencial de las rutas?
Tendría sentido eliminar las transiciones épsilon de la NFA, pero creo que esto tiene el efecto de eliminar todo no determinismo del patrón (a*)*. Sin embargo, esto definitivamente es vulnerable, ¡así que no estoy completamente seguro de lo que está pasando!
¡Muchas gracias de antemano!
Editar: Se ha señalado que Qtax Epsilons no pueden todavía estar presente cuando el NFA es atravesado con la marcha atrás tradicional, de lo contrario (@)* se intentará hacer coincidir siempre. Entonces, ¿qué implementación de NFA podría llevar a que (a*)* y (a|a)* sean exponenciales, y (a?)* no sea así? Este es el quid de la cuestión realmente.
Los motores PCRE y Perl regex están optimizados de muchas maneras. Todos sus ejemplos fallarán rápidamente sin retrocesos catastróficos, incluso en grandes cadenas. – Qtax
Soy consciente de esto, tal vez un mejor ejemplo sería el motor de expresiones regulares de Java, que no falla rápidamente. Las primeras versiones de PCRE y Perl también sufrieron los mismos problemas, ¡y mi pregunta puede aplicarse a ellos! Sin embargo, en esos motores que parecen ser vulnerables a patrones tales como '(a *) *' (es decirmotores no optimizados), '(a?) *' parece estar bien, ¿por qué? – Jarmex
Optimizaciones. La expresión de ancho cero cuantificado (sin efectos secundarios) es inútil, y si se usara como usted describe (intente hacer coincidir 'a' luego cadena vacía para cada repetición) entonces la expresión regular nunca fallará, ya que puede repetir'() * ' indefinidamente. – Qtax