3 ms·

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 so

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
  > 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. All this means is that Perl sometimes evaluates inputs using an NFA algorithm. To describe its matching engine generally as an NFA is extremely misleading. > See for example https://msdn.microsoft.com/en-us/library/e347654k%28v=vs.110.. 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. Yes. It's sad. I frankly can't tell you how much I see this confusion. It happens so much. I point it out when I see it in the hopes that others learn. I don't really buy the argument that we should stop educating others just because the "damage is done." There's certainly a fine line between being an annoying pedant about this and genuinely trying to clarify it for someone who is confused. I thought I was doing the latter in this case initially. Of course, I am hyper sensitive to this topic because I maintain a regex engine! Can you guess which kind? :P

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
> 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. All this means is that Perl sometimes evaluates inputs using an NFA algorithm. To describe its matching engine generally as an NFA is extremely misleading. > See for example https://msdn.microsoft.com/en-us/library/e347654k%28v=vs.110.. 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. Yes. It's sad. I frankly can't tell you how much I see this confusion. It happens so much. I point it out when I see it in the hopes that others learn. I don't really buy the argument that we should stop educating others just because the "damage is done." There's certainly a fine line between being an annoying pedant about this and genuinely trying to clarify it for someone who is confused. I thought I was doing the latter in this case initially. Of course, I am hyper sensitive to this topic because I maintain a regex engine! Can you guess which kind? :P