[yatac42]

> re2 uses a DFA-based system instead that just doesn't support the kinds of regexes that catastrophically backtrack

There are certain fearures that are harder or impossible to implement with RE2's approach, but it's not true that it doesn't support the kind of regex that would catastrophically backtrack using a backtracking engine.

`(.*a)*b` would be a (silly) example of a regex that can catastrophically backtrack using backtracking engines and re2 supports it just fine without backtracking.

[krackers]

If it's actually a _regular_ expression, by definition re2 will support it. Of course if by "regular expression" you mean pcre (with things like subpatterns) then this can actually match a many context-free languages as well, and if you're doing that then you probably want a proper parser anyway instead of trying to roll one yourself.

[burntsushi]

> If it's actually a _regular_ expression, by definition re2 will support it.

Hmmm, kinda sorta. Regular languages are closed under complement and intersection, but RE2 doesn't support them. They are difficult to implement efficiently, particularly with respect to building the regex. There are some issues on the RE2 issue tracker about this.

Of course, you could say that you could always rewrite a regex using complement or intersection to an equivalent regex that doesn't use those operations. While true, such a feat is usually quite tricky. So treat this comment as adding more clarity as opposed to me trying to correct you perhaps. :-)

Complement and intersection are not implemented in any "general purpose" regex engine that I know of. You tend to find them in more specialty projects like redgrep[1] or in libraries specifically devoted to the construction and manipulation of DFAs. (RE2 doesn't have such a thing, only a lazy DFA, because full DFAs are too expensive to build in the "general purpose" context.)

[1]: https://github.com/google/redgrep

[yatac42]

And perhaps more relevantly, the regex from the article also works fine in RE2.