[burntsushi]

Thanks! You might be right. I'm probably at a point where I'd have to actually go out and try it to understand it better.

I do wonder if there is some room for derivatives in a meta regex engine (like RE2 or the regex crate). For example, if it let you build a DFA more quickly (in practice, not necessarily in theory), then you might be able to use it for a big subset of cases. It's tricky to make that case over the lazy DFA, however, a full DFA has more optimization opportunities. For example, identifying states with very few outgoing transitions and "accelerating" them by running memchr (or memchr2 or memchr3) on those outgoing transitions instead of continuing to walk the automaton. It's really hard to do that with a lazy DFA because you don't really compute entire states up front.

[def-lkb]

I think what you suggest is possible, derivation might even be well suited for this application, however I can't tell if it would be better than existing approaches. There are some chances that it might be interesting in practice, since it seems that this application of derivatives has not been much studied, but that's highly speculative.