5 ms·
You're the author of Haraka, a tool I'm prepared to try in production. This makes me _really_ worried that I'm making the right choice. (To explain: obviously
by simi_ 12y ago
You're the author of Haraka, a tool I'm prepared to try in production. This makes me _really_ worried that I'm making the right choice.
(To explain: obviously C++ churns out machine code, the parent was talking about compiled vs uncompiled regexes – if I'm not terribly wrong, the compilation step is turning the regex into a finite automaton.)
- baudehlo 12y agoV8 literally compiles regexps to X86 machine code the first time they are executed. They are not compiled into an FSA that gets walked in the traditional sense. Hopefully that lowers your concern level.
- simi_ 12y agoInteresting, thanks for the info!
- TheLoneWolfling 12y agoDoesn't that mean that you have exponential worst-case complexity?
- jbnicolai 12y agoAbsolutely! Even worse, you may get different results than the expected method (FSA compilation) would yield. Observe: Javascript, executed in the console of a recent Chrome: > 'ab'.match(/a|ab/) ["a"] BSD Grep: > egrep 'a|ab' <<< ab ab
- TheLoneWolfling 12y agoYow... I was under the impression that all major regex engines used NFAs converted to DFAs lazily, with fallbacks to a slower engine for features that cannot (or cannot practically) be implemented using an NFA (unbounded backtracking, that sort of thing.) What is the advantage to doing this?