python - Pythonはreモジュールの正規表現評価にNFAを使用しますか？

Question

Python（任意のバージョン）が正規表現を評価するためにNFA（非決定性有限オートマトン）を使用したかどうか、または他のメカニズムを使用したかどうかを誰かが知っていますか？可能な場合は、リンク/参照を提供してください。

Answer 1

これは、DFAでは1ミリ秒未満かかるはずです。

$ 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のMasteringRegularExpressions、第3版、第4章-表4-1、145ページを参照してください。

Googleブックスにはプレビューがあります。