Re:Debugging Catastrophic Backtracking for Regular Expressio...
by krackers on Saturday September 09, 2023 @03:15PM
(#37449253)
Thanks, this is a good point. As you mentioned, I'd still argue that because complementing an NFA can result in an exponential blowup in number of states it makes sense to not support it as a "first-class" operation, to avoid giving one an accidental footgun. (And if for some reason you really need to, you can compute it yourself then write the [likely very long] regex for 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