5 ms·
Same question here. I didn't realize that they didn't. regular expression NFA and DFA algorithms are in every compiler book out there. I find it hard to believe
by newt0311 18y ago
Same question here. I didn't realize that they didn't. regular expression NFA and DFA algorithms are in every compiler book out there. I find it hard to believe that guido et al. didn't know about these algorithms.
- michaelneale 18y agoI am guessing the comment by jimrandomh explains why. to be perl compatible you need a lot more.
- nostrademons 18y agoYeah, jimrandomh's comment basically explains it. Perl regexp's have features that can't be implemented by a DFA, like backreferences and arbitrary code evaluation. (I believe you can implement capturing subgroups, you'd just need to annotate the states with a marker for the current position in the string.) Those features are used often enough that you can't just leave them out. I see no reason why popular languages couldn't implement both algorithms, though, and then select the backtracking one only if the regexp contains backreferences or expressions. It's easy enough to tell if a regexp uses these features, just checking for their existence when the regexp is compiled. Then you could use the fast algorithm when possible and the featureful one when not.
- newt0311 18y agoNope. Backref and friends can be implemented on top of DFAs. Grep offers an example of such an implementation.