python - 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 的Mastering Regular Expressions，第 3 版，第 4 章 - 表 4-1，第 145 页。

Google 图书有一个预览版。