I wonder which regular expression algorithm does Python's re module use~
-
4Possible duplicate of Which Regular Expression flavour is used in Python?. It seems that Python uses its own flavor of regex, which is fairly similar to Perl.– Tim BiegeleisenDec 28, 2017 at 2:46
-
@TimBiegeleisen stackoverflow.com/questions/12022443/… is about compatible of python's regex syntax with other language,like perl's’;While my question is about python's regex's algorithm, it's recursive backtracking algorithm– leafonswordDec 29, 2017 at 6:49
1 Answer
(I would comment but I can't at the moment)
If you read the article you linked thoroughly, it says that Python uses a backtracking algorithm.
In contrast, Perl, PCRE, Python, Ruby, Java, and many other languages have regular expression implementations based on recursive backtracking that are simple but can be excruciatingly slow.
Of course, every language would implement regex differently, though the time complexity should be similar. If you want to investigate how exactly it's done, you can simply just read the algorithms.