Second, this fucking course is really good: https://www.coursera.org/course/automata (I have taken it myself.) If you have a dozen hours to spare, it is highly recommended.
Third, you may want to take a look at this… fucking… analogy:
The number of paths from top to bottom is 2^N. If you want to try them all, that will indeed take exponential time, parallelism or not. But when you process an NFA, you don't care which path you have taken. So you can forget about which path you have "actually" taken.
The thing is, when you branch from K, both branches land at the same spot: K+1. So you merge those branches. Then you split again. So when you're going through this graph, the maximum number of actual threads you will ever run in parallel is 2.
That's nowhere near the expected 2^N.
Here lies the beauty of proper NFA processing. By merging the parallel threads at each opportunity, you keep their numbers down to the number of states in the NFA —at most. As a result, the worst running time of a good NFA algorithm is O(N*S), where N is the length of the input, and S the number of states in the NFA. And the worst running space is O(S).
Of course, if you're fail to merge the threads (like backtracking), then your worst case goes back to exponential. On the other hand, it can give you extra powers such as back references.
Regular expression usage in real programs is somewhat more complicated than what the regular expression implementations described above can handle...
I'm unable to see how the approach suggested in the paper could be made idempotent with Perl's regular expression engine while still maintaining linear performance. Though admittedly idempotence is a strong form of "Perl Compatible".
But as I'm not particularly bright, there's no need to try and explain.
(Sorry for the dismissive tone, but you apparently glossed over the algorithm I took pain to write for you. That pissed me off a little.)
PCRE is the wrong trade-off, not worth the backward compatibility. The world will be a better place when people stop to use them. I don't care what real programs do, real programs are wrong.
You need to understand that PCRE are not regular expressions. They're top down parsers.
Let that sink in for a moment. PCRE are actually top-down parsers.
By using the syntax of regular expression, PCRE are less readable than they could be, and their full power comes of as incredibly contrived. If they were called Perl Compatible Parsing Expression Grammars (PCPEG), and used an actual PEG syntax, I wouldn't object.
If you need to parse a regular grammar, use an actual regular expression engine. If you need something more powerful, then you may consider top down parsing. Just don't be shy about it.
I'm not a Perl RegEx expert, but what about Perl regexes isn't idempotent? Which features modify the external environment other than by returning matches? Even variable assignment would be idempotent unless the variable is both modified and affects the behavior of the regex.
> How idempotence has to do with anything? A regex match is supposed to return a result, not perform effects…
Correct, which is why I was asking why the GP wrote:
> I'm unable to see how the approach suggested in the paper could be made idempotent with Perl's regular expression engine while still maintaining linear performance.
First, I suggest you read the fucking link I summarised in the first place: https://swtch.com/~rsc/regexp/regexp1.html
Second, this fucking course is really good: https://www.coursera.org/course/automata (I have taken it myself.) If you have a dozen hours to spare, it is highly recommended.
Third, you may want to take a look at this… fucking… analogy:
The number of paths from top to bottom is 2^N. If you want to try them all, that will indeed take exponential time, parallelism or not. But when you process an NFA, you don't care which path you have taken. So you can forget about which path you have "actually" taken.The thing is, when you branch from K, both branches land at the same spot: K+1. So you merge those branches. Then you split again. So when you're going through this graph, the maximum number of actual threads you will ever run in parallel is 2.
That's nowhere near the expected 2^N.
Here lies the beauty of proper NFA processing. By merging the parallel threads at each opportunity, you keep their numbers down to the number of states in the NFA —at most. As a result, the worst running time of a good NFA algorithm is O(N*S), where N is the length of the input, and S the number of states in the NFA. And the worst running space is O(S).
Of course, if you're fail to merge the threads (like backtracking), then your worst case goes back to exponential. On the other hand, it can give you extra powers such as back references.