3 ms·

I'm not the author of this implementation, so I don't have sufficient understanding of the algorithm to explain why your reasoning is wrong, but the threading a

I'm not the author of this implementation, so I don't have sufficient understanding of the algorithm to explain why your reasoning is wrong, but the threading approach is widely known (used in e.g. Go) and is not exponential. 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/ https://swtch.com/~rsc/regexp/.

yakubin 4y ago
Russ made a different claim though. He wrote that the backtracking approach is O(2^n), where n is the size of the string matched against, while simulating NFA is O(mn)[1] (not O(n) as the article claims), where m is the length of the regex. The article on the other hand claims that backtracking gives you O(2^m): > 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).
- vladharbuz 4y ago
  Hi, author here! I think you're right that some things in the article are a bit wrong, I seem to have used inaccurate wording about the actual complexity, and I think I also failed to differentiate between the NFA and DFA cases (which I wanted to do a bit for simplicity, but it seems I overdid it). I'll be looking over the details more carefully and updating the wording. Thank you for your comment! :)
  - yakubin 4y ago
    No problem. I like that you chose to go with POSIX Extended Regexes and FAs instead of going the Perl route.

yakubin 4y ago

Russ made a different claim though. He wrote that the backtracking approach is O(2^n), where n is the size of the string matched against, while simulating NFA is O(mn)[1] (not O(n) as the article claims), where m is the length of the regex. The article on the other hand claims that backtracking gives you O(2^m): > 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).

vladharbuz 4y ago
Hi, author here! I think you're right that some things in the article are a bit wrong, I seem to have used inaccurate wording about the actual complexity, and I think I also failed to differentiate between the NFA and DFA cases (which I wanted to do a bit for simplicity, but it seems I overdid it). I'll be looking over the details more carefully and updating the wording. Thank you for your comment! :)
- yakubin 4y ago
  No problem. I like that you chose to go with POSIX Extended Regexes and FAs instead of going the Perl route.