Hacker News Reader

Comment by ridiculous_fish | Hacker News Reader

How does nim-regex implement capture groups and zero-width assertions (like \b)? Both of those are tricky with DFAs.

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

re2 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.

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

As 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)

That'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.

Reply on news.ycombinator.com