3 ms·

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

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
  Perl's algorithm has more power than an NFA, therefore, it is not an NFA. It's as simple as that. That certain inputs happen to correspond to a configuration solvable by an NFA does not make it an NFA. The worst part about calling it an NFA is that it misleads everyone about the theory and suggests that the engine is less powerful than it really is. I completely understand why it looks like an NFA. > What the heck do you call it? Anything but an NFA? My personal preference is unbounded backtracking (still not quite right), or just "Perl regexes." > (As well, that is how it was described in a number of popular and widely read books. For example pick up _Mastering Regular Expressions_.) I read that book when I was a young pup and remained hopelessly uninformed about the entire situation until my first complexity theory class during my undergraduate study almost ten years ago. That book is fantastic if you care about optimizing Perl regexes. It otherwise does a great disservice to theory and has likely been the cause of uncountable confusion. When pointed out the inaccuracy, Friedl essentially had the same response as you. It's tragic, frankly. PCRE's documentation even cites Friedl's book when describing their implementation by calling it the "NFA algorithm." PCRE also has a supposed "DFA," but its description makes it sound more like the actual NFA algorithm (since it maintains multiple states simultaneously).
  - btilly 11y ago
    It is not that certain inputs happen to correspond to a configuration solvable by an NFA. It is that if you give it certain inputs it internally generates a data structure that actually IS a description of an NFA. And the same is true of most RE engines. As for _Mastering Regular Expressions_, you've demonstrated both what it says and that it is popular. And further that it affected the terminology of a widely used project which has been embedded in many other projects. (Like PHP.) And yes, I agree that it did a lot of people a disservice. But the damage is now long-done. See for example https://msdn.microsoft.com/en-us/library/e347654k%28v=vs.110%29.aspx https://msdn.microsoft.com/en-us/library/e347654k%28v=vs.110... for yet another non-NFA that is described as one somewhere that programmers are likely to believe it.
    - burntsushi 11y ago

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
Perl's algorithm has more power than an NFA, therefore, it is not an NFA. It's as simple as that. That certain inputs happen to correspond to a configuration solvable by an NFA does not make it an NFA. The worst part about calling it an NFA is that it misleads everyone about the theory and suggests that the engine is less powerful than it really is. I completely understand why it looks like an NFA. > What the heck do you call it? Anything but an NFA? My personal preference is unbounded backtracking (still not quite right), or just "Perl regexes." > (As well, that is how it was described in a number of popular and widely read books. For example pick up _Mastering Regular Expressions_.) I read that book when I was a young pup and remained hopelessly uninformed about the entire situation until my first complexity theory class during my undergraduate study almost ten years ago. That book is fantastic if you care about optimizing Perl regexes. It otherwise does a great disservice to theory and has likely been the cause of uncountable confusion. When pointed out the inaccuracy, Friedl essentially had the same response as you. It's tragic, frankly. PCRE's documentation even cites Friedl's book when describing their implementation by calling it the "NFA algorithm." PCRE also has a supposed "DFA," but its description makes it sound more like the actual NFA algorithm (since it maintains multiple states simultaneously).
- btilly 11y ago
  It is not that certain inputs happen to correspond to a configuration solvable by an NFA. It is that if you give it certain inputs it internally generates a data structure that actually IS a description of an NFA. And the same is true of most RE engines. As for _Mastering Regular Expressions_, you've demonstrated both what it says and that it is popular. And further that it affected the terminology of a widely used project which has been embedded in many other projects. (Like PHP.) And yes, I agree that it did a lot of people a disservice. But the damage is now long-done. See for example https://msdn.microsoft.com/en-us/library/e347654k%28v=vs.110%29.aspx https://msdn.microsoft.com/en-us/library/e347654k%28v=vs.110... for yet another non-NFA that is described as one somewhere that programmers are likely to believe it.
  - burntsushi 11y ago