> About large character classes: how are those harder than in approaches? If you build any FSM you have to deal with those, don't you? I mean specifically in t

> About large character classes: how are those harder than in approaches? If you build any FSM you have to deal with those, don't you? I mean specifically in the context of derivatives. IIRC, the formulation used in Turon's paper wasn't amenable to large classes. Yes, interval sets work great: https://github.com/rust-lang/regex/blob/master/regex-syntax/src/hir/interval.rs https://github.com/rust-lang/regex/blob/master/regex-syntax/... This is why I asked if a production grade regex engine based on derivatives exists. Because I want to see how the engineering is actually done. > What do you want your capture groups to do? Do you eg just want to return pointers to where you captured them (if any)? Look at any production grade regex engine. It will implement captures. It should do what they do. > I have an inkling that something inspired by https://en.wikipedia.org/wiki/Viterbi_algorithm https://en.wikipedia.org/wiki/Viterbi_algorithm might work. Nothing about Viterbi is fast, in my experience implementing it in the past. :-) > https://github.com/google/redgrep/blob/main/parser.yy https://github.com/google/redgrep/blob/main/parser.yy mentions something about capture, but not sure if that has anything to do with capture groups. It looks like it does, and in particular see: https://github.com/google/redgrep/blob/6b9d5b02753c4ece17e2f1c8e9b619b25e498189/regexp.h#L290-L294 https://github.com/google/redgrep/blob/6b9d5b02753c4ece17e2f... But that's only for parsing the regex itself. I don't see any match APIs that utilize them. I wouldn't expect to either, because you can't implement capturing inside a DFA. (You need a tagged DFA, which is a strictly more powerful thing. But in that case, the DFA size explodes. See the re2c project and their associated papers.) If I'm remembering correctly, I think the problem with derivatives is that they jump straight to a DFA. You can't do that in a production regex engine because a DFA's worst case size is exponential in the size of the regex.