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

如果把25改成100，它就会一直运行下去，永远不会结束。

这是在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的《掌握正则表达式》第三版，第4章 - 表4-1，145页。

谷歌图书上有预览可以查看。