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

美国国家期货协会。

请参阅 Friedl 的掌握正则表达式，第 3 版，第 4 章 - 表 4-1，第 145 页。Google

图书有 预览 。