polyregex

>> lazy quantifiers for inclusion into the next release of POSIX > That is surprising! I mean, POSIX BREs (only!) also include (single-digit) backreferences. Surprisingly, (with such a restriction) this is actually polynomial[1,2] if impractical (h/t 'burntsushi for the reference[3]). But I still wouldn’t take POSIX as the arbiter of sanity in this case. Thus far I’m not even convinced their text actually amounts to a well-defined ordering on parse trees. I don’t know if nongreedy quantifiers are all that interesting without match groups, though, so this isn’t a particularly burning question in my view. [1] https://branchfree.org/2019/04/04/question-is-matching-fixed... [2] https://github.com/travisdowns/polyregex [3] https://news.ycombinator.com/item?id=40431198

> Sat solvers have been implemented on backtracking regex engines. Again, if the (not-really-)regular expression grows as the SAT problem does, that doesn’t mean game over yet. Your favourite ahead-of-time regex compiler (the good interactive ones are usually incremental, but lex/flex or re2c certainly fit) is also exponential in the size of the regex, because determinization can have exponential-size output. After the (exponentially large) compiled form is produced, though, matching is linear in the size of the haystack no matter what it is. Burntsushi’s sibling reply links to blog post and thence to a proof-of-concept regular+backreferences expression matcher[1] that works in (quite miserable but still) polynomial time wrt the haystack, with the degree of the polynomial depending on the number of groups that have backreferences to them.

Here's a regex implementation that is polynomial in time and space: https://github.com/travisdowns/polyregex If you want to use extender regex that includes backreferences, it is still polynomial as long as the number of backreferences is fixed: since many regex syntaxes only support \1 through \9, the count is fixed by construction.