5 ms·

> 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 th

by 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.
  - burntsushi 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. I don't think so. There's a reason why exactly zero popular regex engines build full DFAs. (Sometimes small DFAs are built in cases where you know they'll be very small or enforce a tight bound, but even then, the DFA is typically used as a prefilter rather than a regex engine unto itself.) There are plenty of regex engines that do build full DFAs, but they're either relegated to the work of research or niche areas. re2c, for example, is an excellent regex engine that translates regex syntax into DFA source code. It thus has procedures for compilation and execution, but it is not what I would call a "general purpose" regex engine. As another example, if I were to make Rust's regex crate use quadratic (or far worse, exponential) compilation, I'm pretty sure I'd have many upset users. (Now, I could use quadratic or even exponential compilation in cases where I'm sure that the absolute wall clock time won't be disagreeable, but I think it's safe to exclude such things for the purposes of this discussion.) Even for DFAs that don't take exponential time, Unicode means that DFAs get obscenely big. \pL, for example, is 279 states and uses 143K of memory. And it takes around 8ms to compile on my machine. 1ms is already pushing it. > Are you sure that a less naive approach doesn't exist? Pretty sure. I'm not an expert in the theory either. I'm just aware of most of it. And I'm totally unaware of anyone who has overcome the practical engineering challenges of things like complement and intersection.
nsajko 4y ago
I'm curious about why someone would downvote the comment I'm replying to.
- surrealize 4y ago
  I downvoted it because you were talking to burntsushi, who has implemented an excellent general-purpose regex engine and is very thorough, thoughtful, and knowledgeable about it. When he said "Can you show me the research", that was him being exceedingly generous to your point of view. And when you said "Sorry, don't have time for that right now, but look into regular expression derivatives and similar stuff", that was you being the opposite of generous.
  - nsajko 4y ago
    Thanks for voicing your opinion. That said, I don't see constructive criticism here. From what I gather I was basically at fault for daring to somewhat disagree with burntsushi. > who has implemented an excellent ... This is an appeal to authority. > being exceedingly generous to your point of view Now you're just insulting me!? > you being the opposite of generous Consider that I couldn't have known upfront that burntsushi is acquainted to any degree with RE derivatives and similar concepts. His regexp engine is not based on them AFAIK. So I pointed to those for a start. Later in the discussion, including in the same comment, I pointed to other sources, too. So I think it's not fair to call me ungenerous. The whole "general-purpose regex engine" thing was moving the goalposts in the first place and not very relevant to this whole discussion anyway. EDIT: I'm not saying that these distinctions don't matter at all, rather what I want to say is that it doesn't make sense to implicitly call upon a subjective and arbitrary standard.
    - earleybird 4y ago
      > This is an appeal to authority. I understand how you might think this. However, please consider that the statement you were responding to is establishing a bonafide - a reason why burntsushi's words might be worth consideration. Sometimes an appeal to authority is not wrong. In my experience, the more I study a topic, the smarter other folks appear.

by nsajko 4y ago

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.
- burntsushi 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. I don't think so. There's a reason why exactly zero popular regex engines build full DFAs. (Sometimes small DFAs are built in cases where you know they'll be very small or enforce a tight bound, but even then, the DFA is typically used as a prefilter rather than a regex engine unto itself.) There are plenty of regex engines that do build full DFAs, but they're either relegated to the work of research or niche areas. re2c, for example, is an excellent regex engine that translates regex syntax into DFA source code. It thus has procedures for compilation and execution, but it is not what I would call a "general purpose" regex engine. As another example, if I were to make Rust's regex crate use quadratic (or far worse, exponential) compilation, I'm pretty sure I'd have many upset users. (Now, I could use quadratic or even exponential compilation in cases where I'm sure that the absolute wall clock time won't be disagreeable, but I think it's safe to exclude such things for the purposes of this discussion.) Even for DFAs that don't take exponential time, Unicode means that DFAs get obscenely big. \pL, for example, is 279 states and uses 143K of memory. And it takes around 8ms to compile on my machine. 1ms is already pushing it. > Are you sure that a less naive approach doesn't exist? Pretty sure. I'm not an expert in the theory either. I'm just aware of most of it. And I'm totally unaware of anyone who has overcome the practical engineering challenges of things like complement and intersection.

nsajko 4y ago

I'm curious about why someone would downvote the comment I'm replying to.

surrealize 4y ago
I downvoted it because you were talking to burntsushi, who has implemented an excellent general-purpose regex engine and is very thorough, thoughtful, and knowledgeable about it. When he said "Can you show me the research", that was him being exceedingly generous to your point of view. And when you said "Sorry, don't have time for that right now, but look into regular expression derivatives and similar stuff", that was you being the opposite of generous.
- nsajko 4y ago
  Thanks for voicing your opinion. That said, I don't see constructive criticism here. From what I gather I was basically at fault for daring to somewhat disagree with burntsushi. > who has implemented an excellent ... This is an appeal to authority. > being exceedingly generous to your point of view Now you're just insulting me!? > you being the opposite of generous Consider that I couldn't have known upfront that burntsushi is acquainted to any degree with RE derivatives and similar concepts. His regexp engine is not based on them AFAIK. So I pointed to those for a start. Later in the discussion, including in the same comment, I pointed to other sources, too. So I think it's not fair to call me ungenerous. The whole "general-purpose regex engine" thing was moving the goalposts in the first place and not very relevant to this whole discussion anyway. EDIT: I'm not saying that these distinctions don't matter at all, rather what I want to say is that it doesn't make sense to implicitly call upon a subjective and arbitrary standard.
  - earleybird 4y ago
    > This is an appeal to authority. I understand how you might think this. However, please consider that the statement you were responding to is establishing a bonafide - a reason why burntsushi's words might be worth consideration. Sometimes an appeal to authority is not wrong. In my experience, the more I study a topic, the smarter other folks appear.