2 ms·
I strongly doubt the AST would be needed. You could probably do this in a trivial loop state machine. It can't even be called laziness: that regex took time to
by zamalek 11y ago
I strongly doubt the AST would be needed. You could probably do this in a trivial loop state machine. It can't even be called laziness: that regex took time to work out - far longer than a switch-based state machine would have taken to write in the first place.
Aside: out of curiosity it would have been interesting to see how a Thompson NFA[1] would have dealt with this.
[1]: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
- hencq 11y ago> Aside: out of curiosity it would have been interesting to see how a Thompson NFA[1] would have dealt with this. It wouldn't have dealt with it right? NFAs and DFAs are equivalent and them being actually regular means they can't do things like count parentheses.
- zamalek 11y agoI miscommunicated the question: "how well would have a Thompson NFA have dealt with this?" I.e. How many magnitudes of order faster would it have been? If it was faster?
- joepvd 11y agoNFAs do not do backtracking. So the solution space would look different. More sane, and more performant, but it would not be a pure regex solution.