JIT sounds interesting. Do you have a good ref? I don't feel the constant factors are large on Thompson. It's essentially linear to construct IIRC, and matchin

JIT sounds interesting. Do you have a good ref? I don't feel the constant factors are large on Thompson. It's essentially linear to construct IIRC, and matching next char is then proportional to the number of current States which are valid. Which is bounded by the vertexes in the NFA which will mostly be less than DFA. I don't see how you can get more efficient than that, because you're just keeping track of all the matching states which would seem to be the minimum required. I'm really keen to learn an even better way. The proposal is a workable heuristic ( use the practically working algorithm rather than the one with a theoretical low bound which is costly in practice ), and people do well to heed it in many places, however I don't believe it applies here because Thompson is great in practice. You sound like you know a lot about this, what am I missing?