4 ms·

I'm with glangdale on this one. Some parts of this are strange, but it was overall a fun read. Thanks. :-) > DFAs have some big advantages over NFAs: Because D

I'm with glangdale on this one. Some parts of this are strange, but it was overall a fun read. Thanks. :-) > DFAs have some big advantages over NFAs: Because DFA regex engines don't need to backtrack they are in general much faster than NFAs. Also, because NFAs need to backtrack, it is possible to structure your pattern in such a way that the backtracking will cause nearly infinite loops on certain input sequences. DFAs also don't need the non-greedy operators STAR? and +? Two points to make here. NFAs certainly do not need to backtrack. You can write an NFA implementation that inspects each byte at most M times, where M ~ len(regex). You can implement this with a virtual machine: https://swtch.com/~rsc/regexp/regexp2.html https://swtch.com/~rsc/regexp/regexp2.html The other point is that "DFAs don't need non-greedy operators" doesn't really make any sense. Were you thinking of possessive quantifiers instead? Non-greedy operators don't impact whether a match occurs or not, but they can certainly impact the length of a match. Both NFAs and DFAs can implement those semantics.

glangdale 9y ago
You can write an NFA implementation that can inspect each byte once. Of course, you won't get capturing or greedy/non-greedy semantics as a result. Even Start of Match is a challenge. We did have a project for a while which did capturing (in a Glushkov NFA) in two passes - you had to inspect each byte twice (if you were content with a O(N) size requirement for side storage, where N is the size of the input), three times (with a O(sqrt(N) side storage requirement), ... k times (with a O(power(N, 1/(k-1)) side storage requirement). It was quite cool, but we never found a customer, and it polluted the Hyperscan source base in many weird ways.
wernsey 9y ago
Thank you for your feedback. I only discovered that article by rsc quite recently when I was putting the finishing touches on the article and going over the sources, but it has some very interesting points and ideas. You are probably correct on both accounts. I will consider how I will correct the article.

glangdale 9y ago

You can write an NFA implementation that can inspect each byte once. Of course, you won't get capturing or greedy/non-greedy semantics as a result. Even Start of Match is a challenge. We did have a project for a while which did capturing (in a Glushkov NFA) in two passes - you had to inspect each byte twice (if you were content with a O(N) size requirement for side storage, where N is the size of the input), three times (with a O(sqrt(N) side storage requirement), ... k times (with a O(power(N, 1/(k-1)) side storage requirement). It was quite cool, but we never found a customer, and it polluted the Hyperscan source base in many weird ways.

wernsey 9y ago

Thank you for your feedback. I only discovered that article by rsc quite recently when I was putting the finishing touches on the article and going over the sources, but it has some very interesting points and ideas. You are probably correct on both accounts. I will consider how I will correct the article.