Comment by burntsushi | Hacker News Reader

Comment by burntsushi | Hacker News Reader

Parent Full thread

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

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.

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

One of the papers that I was referring to above is "Derived-term automata for extended weighted rational expressions" by Akim Demaille, from 2016. I haven't managed to study the topic more closely yet, but the idea seems to be to compute the DFA lazily, only creating the states and transitions when they are required. No idea how well this can perform in practice, but this seems like a valid way to avoid the exponential blowup, and it's already implemented in the Vcsn (formerly "Vaucanson", I think) software.

Vcsn link: https://www.lrde.epita.fr/wiki/Vcsn

Yes, that's what RE2, the regex crate and a few other regex engines already do. (Specifically, build the DFA lazily.) Everything I've said I've said with that full context.

I don't know, maybe just don't make grand pronouncements about regex engines if you aren't actually familiar with how they're implemented and the engineering tradeoffs in play?

So what's the problem with extending regexp then?

It seems pretty clear from reading the above thread that burntsushi is saying that they have not been able to find a way to implement the extensions you suggested without making the compile time unfeasible for general use. Given how prolific their work in writing regex and other text-search related libraries is, it seems reasonable to take them that their word that they have in fact spent time trying to solve this problem. On the other hand, it doesn't sound like there's any any practical implementations that anyone can point to that can in fact add these extensions in a way that doesn't cause the compile time to be infeasible. Given that, you seem to be making the stronger claim, so it's a little strange to put the burden of proof on the other side of the argument.

I already told you. I'm done wasting my time speaking with you in this thread. In particular, you seem unwilling to acknowledge any specific trade offs that I've pointed out.

Wait, if one wants to match a complement of a regex, surely it is equivalent to seeing if matching the original regex would fail? Or do I miss something obvious?

I mean, yes? But it's kind of missing the forest for the trees. Regex searching isn't limited to "did it match or not," but also to finding where the regex matched in the first place. For example, let's say you want to match all words except for 'foo'. You might write, '\b(!foo)\b', where the '(!re)' syntax means "complement of 're'." That would then match 'bar', 'baz' but not 'foo' in 'bar foo baz'.

It's like how character class set notation has a 'negation' feature. e.g., '[a-z]' matches a-z, but '[^a-z]' matches anything except for 'a-z'. So you might say, "why bother with adding negation when you can just check if the original char class would fail?" The answer is that without negation embedded in the regex itself, you miss out on composition.

This is another reason why features like complement and intersection aren't particularly popular. They are weird to reason about. Another reason is that many of their use cases can be achieved through other means. For example, my example above could conceivably be done by iterating over all words (using word segmentation, for example) and just checking whether each matches 'foo' or not. It could also likely be accomplished through the use of negative look-around, commonly found in backtracking regex engines and not finite automata based regex engines.

Your proposed implementation makes sense for the case of merely taking the complement of a simple regular expression. But the point of having the complement operator available is to be able to take complements of arbitrary sub-expressions within the RE, and even having nested complements in the RE. In that case your proposed implementation would be relatively inefficient.

Reply on news.ycombinator.com