4 ms·

Jeffrey Friedl's book on regexes unapologetically popularized the incorrect use of the terms "NFA" and "DFA" to characterize the different implementations of re

Jeffrey Friedl's book on regexes unapologetically popularized the incorrect use of the terms "NFA" and "DFA" to characterize the different implementations of regex engines. Translating to something more sensible, "NFA" means "unbounded backtracking," where as "DFA" means "Thompson NFA simulation." In this vernacular, as far as I can tell, there is no word to describe an actual DFA. PCRE's docs continue this confusion. For example, they expose a DFA API... But it's not actually a DFA! One might say this is similar to how "regex" doesn't necessarily imply "regular," which is true. That's definitely a battle that has been lost long ago. But NFA and DFA are even more specific jargon terms, and the way in which they have been redefined by the Friedls of the world has led to exactly your confusion over and over again.

ridiculous_fish 7y ago
Thank you, that clears everything up. NFA as used here means something completely different from NFAs in CS literature.
- burntsushi 7y ago
  Unfortunately, yes. Although there is a connection. If you squint, you can see parts of the NFA. Indeed, it is very easy to simulate an NFA with unbounded backtracking (taking exponential worst case time). All you need to do from there is add a few op codes for look around and backreferences. Where you end up still looks like you're simulating an NFA, but the actual implementation has a lot more power. To be fair, the same thing happens with the Thompson NFA simulation. It's not too hard to add a little extra power to it in the form of memory in order to track capturing group locations. It becomes more powerful than an NFA with this addition, but retains its linear time bound. This is why I've normally seen this addition called the Pike VM. (At least, Russ Cox and I both use than name.) For completeness, you can also use bounded backtracking to simulate an NFA. It keeps track of all states visited per input byte, so it uses a lot of extra memory, but maintains a linear time bound.

ridiculous_fish 7y ago

Thank you, that clears everything up. NFA as used here means something completely different from NFAs in CS literature.

burntsushi 7y ago
Unfortunately, yes. Although there is a connection. If you squint, you can see parts of the NFA. Indeed, it is very easy to simulate an NFA with unbounded backtracking (taking exponential worst case time). All you need to do from there is add a few op codes for look around and backreferences. Where you end up still looks like you're simulating an NFA, but the actual implementation has a lot more power. To be fair, the same thing happens with the Thompson NFA simulation. It's not too hard to add a little extra power to it in the form of memory in order to track capturing group locations. It becomes more powerful than an NFA with this addition, but retains its linear time bound. This is why I've normally seen this addition called the Pike VM. (At least, Russ Cox and I both use than name.) For completeness, you can also use bounded backtracking to simulate an NFA. It keeps track of all states visited per input byte, so it uses a lot of extra memory, but maintains a linear time bound.