4 ms·

> most regexp libraries are stuck in the 80s/90s, not keeping up with recent developments in research. Can you show me the research that states how to add thin

> most regexp libraries are stuck in the 80s/90s, not keeping up with recent developments in research. Can you show me the research that states how to add things like complement and intersection to general purpose regex libraries? Most regex engines are backtracking based, and in that context, adding complement/intersection seems pretty intractable to me. For the small subset of regex engines that are based on finite state machines, it's pretty much intractable there too outside of niche regex engines. In fact, the research[1] suggests that adding things like complement/intersection is quite difficult: > In particular, we show that when constructing a regular expression defining the complement of a given regular expression, a double exponential size increase cannot be avoided. Similarly, when constructing a regular expression defining the intersection of a fixed and an arbitrary number of regular expressions, an exponential and double exponential size increase, respectively, cannot be avoided. And indeed, as another commenter pointed out, "minimal DFA" is effectively irrelevant for any general purpose regex engine. Not only do you not have the the budget to build a DFA, but you certainly don't have the budget to minimize that DFA. With respect to reversal, RE2 and Rust's regex crate both do that. But mostly as an internal strategy for finding the start-of-match when using a lazy DFA. It's otherwise a somewhat niche feature more generally. With respect to JITs, plenty of regex engines out there do that. PCRE comes to mind. So does V8. As a general purpose regex engine author, we aren't "stuck" in the 80s/90s. There are just some fundamental trade offs at play here that make your ideas difficult to support. It's not like we haven't thought about it. Moreover, for things like complement and intersection specifically, actually reasoning about them in regex syntax is pretty tricky! I'm not sure if you've tried it or not. (There are some niche regex engines that implement it, like redgrep.) [1]: https://dl.acm.org/doi/10.1145/2071368.2071372 https://dl.acm.org/doi/10.1145/2071368.2071372

nsajko 4y ago
> Can you show me the research that states how to add things like complement and intersection to general purpose regex libraries? Sorry, don't have time for that right now, but look into regular expression derivatives and similar stuff. > Most regex engines are backtracking based, and in that context, adding complement/intersection seems pretty intractable to me. Yeah, I wasn't really considering irregular "regexp", they don't make much sense in theory, so of course that extending them wouldn't make much sense either. Thing is, extending true regular expressions with operators like complement and concepts like weights seems like it could make the "theoretically pure" regexps more powerful *in practice* than irregular regexps (with backreferences, etc. Certainly more understandable. > For the small subset of regex engines that are based on finite state machines, it's pretty much intractable there too outside of niche regex engines. Don't think so. There are many examples, but mostly implemented in "functional" programming languages. > In fact, the research[1] suggests that adding things like complement/intersection is quite difficult: > > ... You misunderstood the abstract. It's not saying that its difficult to translate extended RE (RE with these additional operators) to finite automata, it's just saying that translating extended RE to traditional RE can cause a huge blowup (something I already hinted at in the comment above). So this is a pro, not a con. > And indeed, as another commenter pointed out, "minimal DFA" is effectively irrelevant for any general purpose regex engine. Not only do you not have the the budget to build a DFA, but you certainly don't have the budget to minimize that DFA. It's possible to produce NFA directly from extended RE, see "Antimirov derivatives" for a start. The original Antimirov derivatives don't support complementation and similar, but there are extensions that do. Search for something like "partial derivatives regular expression complement", or "derived term automata complement". > niche regex engines that implement it, like redgrep Thanks for the pointer.
- burntsushi 4y ago
  > Sorry, don't have time for that right now, but look into regular expression derivatives and similar stuff. Obviously, I have. There's a reason why there isn't a single general purpose regex engine that uses regex derivatives. They build full DFAs and full DFAs take worst case exponential time and space. > Don't think so. There are many examples, but mostly implemented in "functional" programming languages. Oh I think so. Feel free to link to some examples of general purpose regex engines that implement these things. > You misunderstood the abstract. It's not saying that its difficult to translate extended RE (RE with these additional operators) to finite automata, it's just saying that translating extended RE to traditional RE can cause a huge blowup (something I already hinted at in the comment above). So this is a pro, not a con. No, I'm not misunderstanding anything. The bottom line is that if you have an NFA with N states and you take its complement (how do you do that without first converting it to a DFA?), then you could wind up with an NFA containing a number of states exponential in N. What's happening here is that you aren't quite appreciating what it means to engineer a general purpose regex engine. All of these things you're talking about are all doable and implementable in niche regex engine libraries that serve a particular purpose. And it's all been done before. What I'm talking about here are general purpose regex engines, where you can't afford quadratic time during regex compilation (which is why Thompson's construction is so popular), nevermind exponential time. And all of this is rooted in me taking objection to your characterization of regex engines being "stuck" in the 80s/90s. I'm trying to explain to you why that's not the case. In theory, practice and theory are the same. In practice, they're totally different. > It's possible to produce NFA directly from extended RE, see "Antimirov derivatives" for a start. I know. I'm not talking about what's "possible." I'm talking about what's feasible from engineering perspective. As far as I know, building such an NFA takes O(n^2) time, which is a hard sell in a general purpose regex engine.
  - nsajko 4y ago
    There are tradeoffs, for sure; but say one creates an API with separate procedures for compilation and execution, I think one could call such an engine a "general purpose one" even with the compilation taking quadratic (or even exponential) time. > The bottom line is that if you have an NFA with N states and you take its complement (how do you do that without first converting it to a DFA?), then you could wind up with an NFA containing a number of states exponential in N. Are you sure that a less naive approach doesn't exist? Genuinely asking, I'm not an expert. I don't quite remember the contents, but I know there are some papers with extensions to Antimirov derivatives (see updated upthread comment) that support taking the complement of an expression.
syrrim 4y ago
>Can you show me the research that states how to add things like complement and intersection to general purpose regex libraries? >Most regex engines are backtracking based, and in that context, adding complement/intersection seems pretty intractable to me. Most regex engines, using backtracking, already have it in the form of lookarounds. The performance penalty of such a strategy is often quite significant. Lookarounds are hard to automatically convert into intersection and complement, but if such primitives were exposed to the programmer, they could often reimplement their regexes in terms of them. It might occasionally lead to an unacceptable performance cost, but there would be many cases where it would be a desirable tradeoff.

nsajko 4y ago

> Can you show me the research that states how to add things like complement and intersection to general purpose regex libraries? Sorry, don't have time for that right now, but look into regular expression derivatives and similar stuff. > Most regex engines are backtracking based, and in that context, adding complement/intersection seems pretty intractable to me. Yeah, I wasn't really considering irregular "regexp", they don't make much sense in theory, so of course that extending them wouldn't make much sense either. Thing is, extending true regular expressions with operators like complement and concepts like weights seems like it could make the "theoretically pure" regexps more powerful *in practice* than irregular regexps (with backreferences, etc. Certainly more understandable. > For the small subset of regex engines that are based on finite state machines, it's pretty much intractable there too outside of niche regex engines. Don't think so. There are many examples, but mostly implemented in "functional" programming languages. > In fact, the research[1] suggests that adding things like complement/intersection is quite difficult: > > ... You misunderstood the abstract. It's not saying that its difficult to translate extended RE (RE with these additional operators) to finite automata, it's just saying that translating extended RE to traditional RE can cause a huge blowup (something I already hinted at in the comment above). So this is a pro, not a con. > And indeed, as another commenter pointed out, "minimal DFA" is effectively irrelevant for any general purpose regex engine. Not only do you not have the the budget to build a DFA, but you certainly don't have the budget to minimize that DFA. It's possible to produce NFA directly from extended RE, see "Antimirov derivatives" for a start. The original Antimirov derivatives don't support complementation and similar, but there are extensions that do. Search for something like "partial derivatives regular expression complement", or "derived term automata complement". > niche regex engines that implement it, like redgrep Thanks for the pointer.

burntsushi 4y ago
> Sorry, don't have time for that right now, but look into regular expression derivatives and similar stuff. Obviously, I have. There's a reason why there isn't a single general purpose regex engine that uses regex derivatives. They build full DFAs and full DFAs take worst case exponential time and space. > Don't think so. There are many examples, but mostly implemented in "functional" programming languages. Oh I think so. Feel free to link to some examples of general purpose regex engines that implement these things. > You misunderstood the abstract. It's not saying that its difficult to translate extended RE (RE with these additional operators) to finite automata, it's just saying that translating extended RE to traditional RE can cause a huge blowup (something I already hinted at in the comment above). So this is a pro, not a con. No, I'm not misunderstanding anything. The bottom line is that if you have an NFA with N states and you take its complement (how do you do that without first converting it to a DFA?), then you could wind up with an NFA containing a number of states exponential in N. What's happening here is that you aren't quite appreciating what it means to engineer a general purpose regex engine. All of these things you're talking about are all doable and implementable in niche regex engine libraries that serve a particular purpose. And it's all been done before. What I'm talking about here are general purpose regex engines, where you can't afford quadratic time during regex compilation (which is why Thompson's construction is so popular), nevermind exponential time. And all of this is rooted in me taking objection to your characterization of regex engines being "stuck" in the 80s/90s. I'm trying to explain to you why that's not the case. In theory, practice and theory are the same. In practice, they're totally different. > It's possible to produce NFA directly from extended RE, see "Antimirov derivatives" for a start. I know. I'm not talking about what's "possible." I'm talking about what's feasible from engineering perspective. As far as I know, building such an NFA takes O(n^2) time, which is a hard sell in a general purpose regex engine.
- nsajko 4y ago
  There are tradeoffs, for sure; but say one creates an API with separate procedures for compilation and execution, I think one could call such an engine a "general purpose one" even with the compilation taking quadratic (or even exponential) time. > The bottom line is that if you have an NFA with N states and you take its complement (how do you do that without first converting it to a DFA?), then you could wind up with an NFA containing a number of states exponential in N. Are you sure that a less naive approach doesn't exist? Genuinely asking, I'm not an expert. I don't quite remember the contents, but I know there are some papers with extensions to Antimirov derivatives (see updated upthread comment) that support taking the complement of an expression.

syrrim 4y ago

>Can you show me the research that states how to add things like complement and intersection to general purpose regex libraries? >Most regex engines are backtracking based, and in that context, adding complement/intersection seems pretty intractable to me. Most regex engines, using backtracking, already have it in the form of lookarounds. The performance penalty of such a strategy is often quite significant. Lookarounds are hard to automatically convert into intersection and complement, but if such primitives were exposed to the programmer, they could often reimplement their regexes in terms of them. It might occasionally lead to an unacceptable performance cost, but there would be many cases where it would be a desirable tradeoff.