3 ms·

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.