Python是否在re模块中使用NFA进行正则表达式求值？

Question

有人知道Python(任何版本)是否使用NFA(非确定性有限自动机)来评估正则表达式还是使用其他机制？如果可以,请提供链接/参考.

Answer 1

这应该在DFA上花费不到一毫秒:

$ time python3 -c 'import re; re.match("a?"*25+"a"*25, "a"*25)'
real    0m7.273s

用100改变25,它不会终止一生.

以下是它在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

http://swtch.com/~rsc/regexp/regexp1.html对该主题进行了很好的讨论.

Answer 2

NFA.

参见Friedl的Mastering Regular Expressions,第3版,第4章 - 表4-1,第145页.

Google图书有预览功能.