Weiß jemand, ob Python (irgendeine Version) NFAs (nicht-deterministische finite Automaten) verwendet hat, um reguläre Ausdrücke auszuwerten, oder benutzt es einen anderen Mechanismus? Bitte geben Sie Links/Referenzen an, falls verfügbar.Verwendet Python NFAs für die Evaluierung regulärer Ausdrücke im re-Modul?
Dies sollte weniger eingenommen hat, als eine ms auf einem DFA:
$ time python3 -c 'import re; re.match("a?"*25+"a"*25, "a"*25)'
real 0m7.273s
Ändern 25 mit 100, und es wird ein Leben lang nicht beenden.
Hier ist, wie es auf einem DFA (grep) aussieht:
$ 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
Es gibt eine große Diskussion des Themas bei http://swtch.com/~rsc/regexp/regexp1.html
Da die meisten RE-Motoren heute für nicht-reguläre Sprachen ermöglichen angepasst werden Ich bezweifle, dass eine moderne RE-Maschine tatsächlich immer noch NFAs oder DFAs verwendet. – Joey
Nun, da eine RE-Engine eine Teilmenge von REs identifizieren kann, die regulär sind und die allgemein verwendet werden, ist es sinnvoll, für diese Szenarien zu optimieren. Es ist also durchaus möglich, dass sie manchmal NFAs oder DFAs verwenden. – MSalters