Est-ce que quelqu'un sait si Python (toute version) a utilisé les NFA (Automates Finis Non-Déterministes) pour évaluer les expressions régulières ou utilise-t-il un autre mécanisme? S'il vous plaît fournir des liens/référence si disponible.Est-ce que Python utilise les NFA pour l'évaluation d'expression régulière dans le module re?
Cela devrait prendre moins d'une ms sur un DFA:
$ time python3 -c 'import re; re.match("a?"*25+"a"*25, "a"*25)'
real 0m7.273s
Change 25 avec 100 et il ne mettra pas fin à une vie.
Voici à quoi il ressemble sur 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
Il y a une grande discussion sur le sujet http://swtch.com/~rsc/regexp/regexp1.html
Comme la plupart des moteurs de RE permettent de nos jours pour des langues non régulières à correspondre Je doute que tout moteur RE moderne utilise encore les NFA ou les DFA. – Joey
Eh bien, comme un moteur RE peut identifier un sous-ensemble de RE qui sont régulières, et ceux-ci sont d'usage courant, il est logique d'optimiser pour ces scénarios. Il est donc tout à fait possible qu'ils utilisent parfois les NFA ou les DFA. – MSalters