Использует ли Python NFA для оценки регулярных выражений в модуле re?

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.

См. Фридла Освоение регулярных выражений , 3-е издание, глава 4 - таблица 4-1, стр. 145.

В книгах Google имеется предварительный просмотр .