4 ms·
Read your link carefully. Real-world regular expression engines support backreferences, and efficiently determining whether an RE with backreferences matches a
by btilly 11y ago
Read your link carefully. Real-world regular expression engines support backreferences, and efficiently determining whether an RE with backreferences matches a given string is an NP-complete problem.
If you're going to implement this important feature in a sane way then at SOME point you're going to need to backtrack.
- burntsushi 11y agoThe parent comments are using the term "NFA engine," not "real world engines." NFA engines indeed cannot support backreferences for exactly the reason you specified. They simply aren't powerful enough. (The top comment in this thread mischaracterized regex engines, which is a common confusion.) And there are plenty of "real world" regex engines in wide use that don't support backreferences.
- btilly 11y agoThe commenter also talked about "RE engines". Most RE engines that are described as being an NFA (examples include Perl's, PCRE and Java's) are implemented with backtracking exactly because you can easily add in a little state and suddenly you support backreferences. Of course the language isn't really now a proper regular expression, but everyone knows what you mean when you talk about them. And yes, I'm well aware of how many real-world regex engines there are without backreferences. However the ones with the most widespread use, do.
- burntsushi 11y ago> Most RE engines that are described as being an NFA Yes, and it's a huge disservice to continue doing so. It doesn't make any sense to describe Perl's (or Java's, or Python's or PCRE) regex implementation as an NFA. > but everyone knows what you mean when you talk about them I disagree. The confusion in this space is extremely high.
- btilly 11y agoYou are at least 20 years too late to change terminology here. There are more people who are used to the wrong terminology than will ever hear or care about the official terminology. Complaining about it is like telling the media the difference between crackers and hackers, or like telling most programmers that what they mean by big-O really is big-Omega. The problem starts with "regular expression". Regular expressions in Java, JavaScript, Python, Perl, Ruby, or many other languages or environments, aren't regular. They support backreferences. In many of those languages, it would be a backwards incompatible change to change either the name of the engine, or its feature set. There are more users of these languages who "know" how to use regular expressions than know the actual definition. Good luck convincing Java, JavaScript and Python to make backwards incompatible changes so we can restore language terminology! Moving on, every description of regular expressions starts with the DFA and NFA terminology. All of these regular expression engines that I named, when presented with an actual regular expression, solve it like an NFA. Admittedly with a backtracking algorithm. Even though their internal states go beyond NFA, it isn't actually wrong to say that "This RE engine uses an NFA algorithm on regular expressions." Given that, it is hopeless either to get people to use "regular expression" in its original meaning, or to get people to stop calling their so-called (but not really) RE engines, NFA implementations.
- burntsushi 11y agoI get that terms can change in meaning over time. I totally concede the point that complaining about the term "regular expression" being misused is a lost cause at this point. The term has graduated from a purely technical term to something that is colloquially used quite frequently. I find it unfortunate, but I'm not going to nitpick someone to death over that. With that said, I absolutely take issue with using the term NFA to describe anything that is NP-complete. It's just plain nonsense. The term "NFA" isn't nearly as widely used as "regular expression," and it is a very technical term with very specific technical implications. > it isn't actually wrong to say that "This RE engine uses an NFA algorithm on regular expressions." This is exactly the problem. It is wrong to say that Perl uses an NFA algorithm. It literally cannot be true because Perl implements features that are NP-complete. This is exactly what happens when people get sloppy with their teminology. They start bending the meaning of words to say something that doesn't make any sense. As a result, those of us who aren't as informed end up getting extremely confused. > or to get people to stop calling their so-called (but not really) RE engines, NFA implementations. In a discussion like the one in this thread, where the distinction ACTUALLY MATTERS, it is absolutely worth pointing out. > Good luck convincing Java, JavaScript and Python to make backwards incompatible changes so we can restore language terminology! This is such a bad argument and such a huge straw man. Do you think I'm on some crusade to fix terminology? No. That's stupid and a waste of time. The only reason I brought this up is because your initial comment in this thread suggested (to me) that you were confused about the terminology being used! Why? Because wolfgke used the term NFA correctly: "An NFA does not use backtracking." But you chimed in with stuff about backreferences and "real" regex engines. What gives? I don't know, but it seemed like a clarification was in order to me.