5 ms·
Yeah, nim-regex is based on NFA. I'm not aware of a pure DFA that is correct and also supports those. I built an hybrid a while ago[0], but it's slower than nim
by nitely 6y ago
Yeah, nim-regex is based on NFA. I'm not aware of a pure DFA that is correct and also supports those. I built an hybrid a while ago[0], but it's slower than nim-regex when it needs to capture/assert, I should profile it and find out why some day.
[0] https://github.com/nitely/nregex https://github.com/nitely/nregex
- ridiculous_fish 6y agore2 implements captures as "tagged DFAs" (Laurikari algorithm) while zero-width assertions are implemented as running the algorithm "one byte ahead". Neither of these techniques is very well known.
- nitely 6y agoAFAIK, 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.