3 ms·

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

> 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 ago
You 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 ago
  I 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.
  - btilly 11y ago
    My response was triggered by wolfge saying, "...implementors of RE engines..." and attributing using backtracking to laziness. However the most widely used RE engines in the wild use backtracking because that is the easiest way to handle the full feature set that is asked of them. That's not to say that they couldn't be implemented in a way that was able to handle strict regular expressions without backtracking, while backtracking only when they need to. (Perl makes a modest attempt in that direction, but doesn't do it completely.) And then when programmers ask how the engine works, they start with the simple version for simple features. The naive explanation is of an actual NFA. And then someone goes off and implements one for a project, and they just follow that. Now you have an engine which is an honest NFA, and uses backtracking. It doesn't need to because it doesn't support extra features, but it is simple, it works, and if you ever needed to extend it, it is obvious how you'd go about it. So there are two reasons other than laziness to implement an RE engine with backtracking. The first is that your RE engine supports (or might in the future) features that require it. The second is that it is easier to find and follow explanations of backtracking. 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. Not true! If you hand Perl's RE engine a regular expression that is actually regular, then Perl will construct a set of states that are a recognizable NFA, and then will attempt to match the NFA to the string using the obvious backtracking algorithm. Admittedly the states are decorated with fields which COULD specify non-NFA stuff. The code it passes through will have checks for whether to trigger features that an NFA can't do. But what it actually will do is construct a recognizable NFA, and attempt to match it to the string. Now throw a non-regular "regular expression" at the same thing and you'll construct a data structure that clearly isn't a proper NFA. What the heck do you call it? It is some type of extended state machine, but it is easiest to think of it as "NFA with some extra stuff". And that is exactly how the people who do work on that code think of it. With no alternate terminology and thinking of it as an NFA, is there any wonder that they describe it as an NFA? (As well, that is how it was described in a number of popular and widely read books. For example pick up _Mastering Regular Expressions_.)
    - burntsushi 11y ago

btilly 11y ago

You 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 ago
I 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.
- btilly 11y ago
  My response was triggered by wolfge saying, "...implementors of RE engines..." and attributing using backtracking to laziness. However the most widely used RE engines in the wild use backtracking because that is the easiest way to handle the full feature set that is asked of them. That's not to say that they couldn't be implemented in a way that was able to handle strict regular expressions without backtracking, while backtracking only when they need to. (Perl makes a modest attempt in that direction, but doesn't do it completely.) And then when programmers ask how the engine works, they start with the simple version for simple features. The naive explanation is of an actual NFA. And then someone goes off and implements one for a project, and they just follow that. Now you have an engine which is an honest NFA, and uses backtracking. It doesn't need to because it doesn't support extra features, but it is simple, it works, and if you ever needed to extend it, it is obvious how you'd go about it. So there are two reasons other than laziness to implement an RE engine with backtracking. The first is that your RE engine supports (or might in the future) features that require it. The second is that it is easier to find and follow explanations of backtracking. 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. Not true! If you hand Perl's RE engine a regular expression that is actually regular, then Perl will construct a set of states that are a recognizable NFA, and then will attempt to match the NFA to the string using the obvious backtracking algorithm. Admittedly the states are decorated with fields which COULD specify non-NFA stuff. The code it passes through will have checks for whether to trigger features that an NFA can't do. But what it actually will do is construct a recognizable NFA, and attempt to match it to the string. Now throw a non-regular "regular expression" at the same thing and you'll construct a data structure that clearly isn't a proper NFA. What the heck do you call it? It is some type of extended state machine, but it is easiest to think of it as "NFA with some extra stuff". And that is exactly how the people who do work on that code think of it. With no alternate terminology and thinking of it as an NFA, is there any wonder that they describe it as an NFA? (As well, that is how it was described in a number of popular and widely read books. For example pick up _Mastering Regular Expressions_.)
  - burntsushi 11y ago