Implementing Regular Expressions in Hare
harelang.org
harelang.org
Also, I don't see how this "threading" solves the issue pointed out in the article:
> This backtracking-based approach works, but it comes with a problem. The number of branches we need to test can exponentially increase with the size of the regex in certain situations, which means that testing all the branches would potentially take forever.
> [...]
> This approach means we only need to do an amount of tests that’s directly proportional to the size of the string we’re testing against. There’s no possibility for exponential growth, and so our algorithm is said to guarantee to match in linear time.
If the number of branches grows exponentially, then the number of "threads" will also grow exponentially. And so the number of states you step through "simultaneously" will grow exponentially. This "simultaneously" seems to be a bit of a sleight of hand in this article. (Also note that the actual code doesn't use multithreading, although that also wouldn't solve the issue --- you'd just have a big number of actual threads to start and coordinate which would probably also be slower, not faster.)
Subset construction is O(2^m), where m is the number of nodes of NFA. It looks scary, but it's important to note that it doesn't depend on the size of string which we're matching against at all. Matching against the string will be linear. And once you have the DFA you may reuse it for many different strings.
All the while, this "threading" still seems exponential wrt branches, but you can't reuse it for different strings.
A good explanation of why and how it works can be found in a collection of posts by Russ Cox, at https://swtch.com/~rsc/regexp/.
> This backtracking-based approach works, but it comes with a problem. The number of branches we need to test can exponentially increase with the size of the regex in certain situations, which means that testing all the branches would potentially take forever.
I think that's where it went wrong. And my comment is also subtly wrong in that it implicitly assumed this is right and proceeded from there.
The important part though is that simulating an NFA grows with the regex, while with DFA it doesn't, and you can also find it in Russ's article ("Caching the NFA to build a DFA").
The article's claim that this is what grep and AWK use is also contradicted by Russ. Claim:
> Incidentally, this is the approach used in grep and awk.
Russ:
> Awk, Tcl, GNU grep, and GNU awk build DFAs, either precomputing them or using the on-the-fly construction described in the next section.
[1]: Most sources claim that it's actually O(nm^2), where m is the number of states of NFA (which is linear to length of regex, so you can treat m as length of regex as well).