I saw this and I was immediately sure that I could make this blow up exponentially. But then I got too lazy to think about exactly how, and instead waited for kind strangers on the Internet to provide a ready solution. Thank you :)

BTW, the concept is still cool.

My point was to illustrate the technique. I found no minimalistic python implementations and decided to write one with a short and gentle intro.

I wanted to add the test for 'syntactic' equivalence to reduce the number of terms. But the code became less readable and I rolled it back.

> DFA construction has a risk of exponential growth in the number of states.

Right, I may have phrased that badly. I meant that the length of the derivative can grow multiplicatively for each consumed character, without bound, so even with memoization you won’t end up with a DFA. For example, in your simple implementation each A fed into (A*)* gives you a new (longer) RE, forever, even though a DFA for it only has to have a starting state and a failure one (actual implementations may end up with more).

Brzozowski proves that a RE has only a finite number of derivatives, thus making memoized differentiation equivalent to lazy DFA construction, but only if you respect associativity, commutativity and idempotence of choice ( | in modern syntax, + in his). I’m not actually sure you need all of those, in all circumstances, or if it’s enough to restrict the equivalences to e.g. the vicinity of a repetition operator, and he doesn’t discuss this, but I’ve made a couple of simpler attempts and could still make them blow up after some tinkering.

r + r ~ r

r + s ~ s + r

(r + s) + t ~ r + (s + t)

In [1] authors state this and refer to the proof in the original paper. They even extend it to a set of extended rules to reduce the number of terms (states) even more.

Actually, the code for (lazy) DFA construction code is not even committed yet. The repo contains just sequential per-character application of the derivative to a regex. Which is obviously finite (though not efficient). Again, just to demonstrate the concept.

[1] https://www.ccs.neu.edu/home/turon/re-deriv.pdf

One neat thing is that the "compaction" rules to avoid exponential blowup are symmetrical (they form like, a ring or semi-ring or whatever, sorry I'm not a mathematician.) https://joypy.osdn.io/notebooks/Derivatives_of_Regular_Expre...

For the 'compaction' you mention, yes it is useful. But the code will be more complicated and optimization wasn't the point of the sketch.

As there’s only a finite number of derivatives, their length is obviously bounded by a constant for a fixed starting RE (though that constant is still exponential in the length of that RE). This implies your non-DFA-based matcher can only take a bounded time computing the next derivative, so takes a time proportional to the length of a string to process that string (even if the constant of proportionality is exponential in the RE length).

(I’m not good at fitting all of my reasoning into a single comment today, am I?)