¿Por qué las expresiones regulares tienen un tiempo de ejecución exponencial?

Es posible escribir un Regex que necesita en algunos casos tiempo de ejecución exponencial. Tal ejemplo es (aa|aa)* . Si hay una entrada de un número impar de s, necesita un tiempo de ejecución exponencial.

Es fácil probar esto. Si la entrada contiene solo a s y tiene una longitud de 51, la Regex necesita algunos segundos para computar (en mi máquina). En cambio, si la longitud de entrada es 52, su tiempo de computación no es perceptible (lo probé con el Regex-parser incorporado de JavaRE).

He escrito un Regex-parser para encontrar el motivo de este comportamiento, pero no lo encontré. Mi analizador puede construir un AST o un NFA basado en un Regex. Después de eso, puede traducir el NFA a un DFA . Para hacer esto usa el algoritmo de construcción powerset .

Cuando analizo el Rgex mencionado anteriormente, el analizador crea un NFA con 7 estados: después de la conversión, solo quedan 3 estados en el DFA. El DFA representa el Regex (aa)* más sensible, que se puede analizar muy rápido.

Por lo tanto, no entiendo por qué hay analizadores que pueden ser tan lentos. ¿Cuál es la razón para esto? ¿No traducen el NFA a un DFA? Si es así, ¿por qué no? ¿Y cuáles son las razones técnicas por las que calculan tan lento?

Russ Cox tiene un artículo muy detallado sobre por qué esto es así y la historia de las expresiones regulares ( parte 2 , parte 3 ).

La coincidencia de expresiones regulares puede ser simple y rápida, usando técnicas finitas basadas en autómatas que se conocen desde hace décadas. En contraste, Perl, PCRE, Python, Ruby, Java y muchos otros lenguajes tienen implementaciones de expresiones regulares basadas en retrocesos recursivos que son simples pero pueden ser terriblemente lentos. Con la excepción de las referencias posteriores, las características proporcionadas por las implementaciones de retroceso lento pueden ser proporcionadas por las implementaciones basadas en autómatas a velocidades dramáticamente más rápidas y consistentes.

En gran medida, se reduce a la proliferación de funciones no regulares en expresiones “regulares” como referencias posteriores, y la ignorancia (continua) de la mayoría de los progtwigdores de que hay mejores alternativas para las expresiones regulares que no contienen tales características (que son muchas de ellas) .

Mientras escribía el editor de texto sam a principios de la década de 1980, Rob Pike escribió una nueva implementación de expresiones regulares, que Dave Presotto extrajo en una biblioteca que apareció en la Octava Edición. La implementación de Pike incorporó el seguimiento de subcompetencias en una eficiente simulación de NFA, pero, como el rest de la fuente de la Octava Edición, no se distribuyó ampliamente. El mismo Pike no se dio cuenta de que su técnica era algo nuevo. Henry Spencer reimplementó la interfaz de la biblioteca Eighth Edition partiendo de cero, pero utilizando el back-track y lanzó su implementación al dominio público. Llegó a ser muy utilizado, y finalmente sirvió de base para las implementaciones de expresiones regulares lentas mencionadas anteriormente: Perl, PCRE, Python, etc. (En su defensa, Spencer sabía que las rutinas podían ser lentas, y no sabía que existía un algoritmo más eficiente. Incluso advirtió en la documentación: “Muchos usuarios han encontrado la velocidad perfectamente adecuada, aunque reemplazando el interior de egrep con este código sería un error. “) La implementación de expresiones regulares de Pike, extendida para soportar Unicode, se hizo disponible de forma gratuita con sam a fines de 1992, pero el algoritmo de búsqueda de expresiones regulares particularmente eficiente pasó desapercibido.

Las expresiones regulares que se ajustan a esta definición formal son computables en tiempo lineal, porque tienen autómatas finitos correspondientes. Se construyen solo a partir de paréntesis, alternativa | (a veces llamado sum), Kleene star * y concatenación.

La extensión de expresiones regulares añadiendo, por ejemplo, referencias hacia atrás puede conducir incluso a expresiones regulares NP-completas. Aquí puede encontrar un ejemplo de expresión regular que reconoce números no primos.

Supongo que una implementación tan extendida puede tener un tiempo de coincidencia no lineal incluso en casos simples.

Hice un experimento rápido en Perl y tu expresión regular se computa igual de rápido para números impares y pares de ‘a’s.