Speed of Rust vs. C

Re:Speed of Rust vs. C by eru on Sunday March 14, 2021 @11:57PM (#26462489)

> 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.

[ Parent | on HN ]

Re:Speed of Rust vs. C by burntsushi on Monday March 15, 2021 @05:25PM (#26469287)

Indeed. 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.

[ Parent | on HN ]

Re:Speed of Rust vs. C by tsegratis on Tuesday March 16, 2021 @06:00AM (#26474790)

Can 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

[ Parent | on HN ]