¿Alguien sabe si Python (cualquier versión) utilizó NFA (autómatas finitos no deterministas) para evaluar expresiones regulares o utiliza algún otro mecanismo? Proporcione enlaces/referencia si está disponible.¿Python usa NFA para la evaluación de expresiones regulares en el módulo re?
Esto debería tomar menos de un ms en un DFA:
$ time python3 -c 'import re; re.match("a?"*25+"a"*25, "a"*25)'
real 0m7.273s
Cambio 25 con 100 y no va a terminar para toda la vida.
Aquí es cómo se ve en un DFA (grep):
$ time echo "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" |grep "a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
real 0m0.063s
hay una gran discusión del tema en http://swtch.com/~rsc/regexp/regexp1.html
Como la mayoría de los motores RE hoy en día permiten lenguajes no regulares, que se ajustará Dudo que un motor de RE moderno realmente todavía use NFAs o DFAs. – Joey
Bueno, dado que un motor de RE puede identificar un subconjunto de RE que son regulares, y que son de uso común, tiene sentido optimizar para esos escenarios. Por lo tanto, es muy posible que a veces utilicen los de NFA o DFA. – MSalters