3 ms·
As I mentioned elsewhere, linear performance is a hard requirement for some domains such as intrusion prevention. Unbounded recursion isn't the primary problem
by colanderman 5y ago
As I mentioned elsewhere, linear performance is a hard requirement for some domains such as intrusion prevention. Unbounded recursion isn't the primary problem; exponential runtime is.
If state-space explosion is a concern, you can implement a non-backtracking regular expression matcher using term rewriting. For true regular expressions, the size of the rewritten terms are a function of the size of the pattern (and thus performance is linear). For non-regular expressions, this does not hold.
- jonstewart 5y agoYou can also just implement an NFA but apply determinization to much of it, with tight memory allocation bounds, to get most of the benefit.
- rurban 5y agoyeah, with practical backtracking regexes they limit their recursion depth to about 10. with DFA expansion this was pretty hard to implement, with simple NFA's it was trivial. Pratt and esp. PEG solve the determinism problem, even better than yacc.