3 ms·
> If I'm remembering correctly, I think the problem with derivatives is that they jump straight to a DFA. You can't do that in a production regex engine because
by eru 6y ago
> If I'm remembering correctly, I think the problem with derivatives is that they jump straight to a DFA. You can't do that in a production regex engine because a DFA's worst case size is exponential in the size of the regex.
Oh, that's interesting! Because I actually worked on some approaches that don't jump directly to the DFA.
The problem is the notion of (extended) NFA you need is quite a bit more complicated when you support intersection and complement.
- burntsushi 6y agoIndeed. And in the regex crate and RE2, for example, captures are only implemented in the "NFA" engines (specifically, the PikeVM and the bounded backtracker). So if you support captures, then those engines have to be able to support everything.
- tsegratis 6y agoCan I ask; what about a zdd? The seem similar to closed languages with a disjunct and conjunct Though I don't think I will, I was considering adding zdd or bdd to a PEG, to provide that conjunct ofc, sat solver can represent a regex with conjuncts, but is this a good way of going about it, particularly with unbounded strings?? Would love to hear your thoughts on that