Python是否在re模塊中使用NFAs進行正則表達式評估？

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的）：

$ 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