[derefr]

> determinized DFA

Yep, that's the thing I was thinking of. Thanks!

Question, since you seem like you might know: is there an alternative regex library—or a plain Yacc parsing grammar that you could stick as a validator in front of PCRE's parser—that would allow through only the regexes which parse out to constant-time (determinized) DFAs?

[skybrian]

Not an expert in this, but I'm thinking this is usually handled by switching to a non-backtracking regexp engine. Otherwise, any such validator would depend on details of the regexp engine's implementation.