3 ms·
AFAIK, RE2 does not implement a tagged DFA. It implements a DFA that runs when captures are not required and/or to find a match within the text and then it runs
by nitely 6y ago
AFAIK, RE2 does not implement a tagged DFA. It implements a DFA that runs when captures are not required and/or to find a match within the text and then it runs the NFA to record the captures.
I'm aware of Laurikari's algorithm, I'm not aware of it being correct[0]. Also, their algorithm has POSIX semantics, RE2 (and most PLs regex engines) has PCRE semantics.
[0] http://lambda-the-ultimate.org/node/2064#comment-25469 http://lambda-the-ultimate.org/node/2064#comment-25469
- fizbin 6y agoAs an aside, it's possible to modify Laurikari's algorithm slightly and obtain PCRE semantics w.r.t. capturing groups, and those correctly. (POSIX capturing semantics are designed for standards specs. I've never met an actual practicing programmer who wanted those semantics instead of the PCRE ones)
- nitely 6y agoThat's good to know. Is there an implementation of it? I know of TRE, regex-tdfa, ocaml-regex-tfa, and re2c, they all implement Laurikari's algorithm (or a variation of it), but have POSIX semantics.