4 ms·
V8 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.
by baudehlo 12y ago
V8 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?