3 ms·

Sure, but it must be relatively simple to identify, pre-compilation, if the regex is regular or not; there's only certain constructions that break regularity. W

• ben509 7y ago
  Theoretically, a regular expression can be expressed in constant space, and that's profoundly limiting, so anything that requires so much as a stack is not a regex. That includes basic things like capture groups. That doesn't mean you can't use automata in a regex-plus implementation, though. I can't find the paper, but I think there is a hybrid engine that tries to get the best of both worlds; constant space where possible and using additional space to provide more features.
  • chaosite 7y ago
    You can implement capture groups with no problem using automata (see re2). You might have meant to say that you can't use backreferences.
• rurban 7y ago
  It can, and it's one of my explicit goals to do so. But the biggest problem is perl's horrible code in regcomp and regexec. (based on Henry Spencer's old code). It mostly does state transitions via goto or setjmp/longjmp. The initial regex scanner did 2 passes, so it would have been trivial to detect NFA illegal backtracking with zero cost. With a cleanly written codebase it would be much easier. my re::engine::PCRE2 replacement is much faster, can do everything and even has less bugs than perl5 regex updates. But it's still not production ready, and full replacement would still be huge work. Now it's just via hooks. Which are slow, because most of the work is done twice.