4 ms·
This is where I got the VM analogy from: https://swtch.com/~rsc/regexp/regexp2.html https://swtch.com/~rsc/regexp/regexp2.html My whole comment was about tenuo
by man-and-laptop 8y ago
This is where I got the VM analogy from: https://swtch.com/~rsc/regexp/regexp2.html https://swtch.com/~rsc/regexp/regexp2.html
My whole comment was about tenuous but interesting analogies, and whether they can lead to somewhere interesting.
- glangdale 8y agoFair enough. I think that implementation is a dreadful straight NFA implementation - and, IIRC, is not used in RE2 for pure NFA code. It's not a dreadful way of implementing regex as it can do things a straightforward bitset NFA implementation can't. To be fair, I think your original post does stand, but I guess I am a bit pedantic about the terminology after spending a little bit of time on regex implementation. In fact, a number of strategies in regex implementation turned out to generalize to broader areas. The bitwise automata are helpful elsewhere, as are many of the strategies one might use to make them fast. The 4 Russians technique ( https://en.wikipedia.org/wiki/Method_of_Four_Russians https://en.wikipedia.org/wiki/Method_of_Four_Russians ) has also cropped up all over the place.