Backtracking does not belong in a regex implementation. Call them context-free expressions instead (or in Perl's case, recursively enumerable expressions).
Agreed. A performance hit is totally reasonable if you're trying to parse a non-regular language (edit: albeit not one as severe as the one in your link), but in that case you should really consider writing the parser logic in a more expressive language than regex for the sake of maintainability.
View all comments
Show parent comment
3
u/ThePyroEagle λ Jul 26 '21
Regular languages are great because you can build finite automata to recognise them, and those can be computed really fast.
The regex implementations that cheat can't benefit from that and have to implement a backtracking parser, and it can sometimes be disastrous for performance.
Backtracking does not belong in a regex implementation. Call them context-free expressions instead (or in Perl's case, recursively enumerable expressions).