Python在re模块中使用NFA进行正则表达式评估吗？

Question

有人知道Python（任何版本）是使用NFAs（非确定性有限自动机）来计算正则表达式还是使用其他机制？请提供链接/参考（如有）。在

Answer 1

NFA。在

参见Friedl的《掌握正则表达式》，第3版，第4章-表4-1，第145页。在

谷歌图书拥有a preview。在

Answer 2

在DFA上，这应该不到一毫秒：

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

把25改成100，它一辈子都不会终止。在

以下是DFA（grep）的外观：

^{pr2}$

在http://swtch.com/~rsc/regexp/regexp1.html上有一个关于这个主题的大讨论