3 ms·
Full disclosure - I work on the Hyperscan project at Intel github.com/01org/hyperscan Regular expression implementation is fun and many interesting things have
by glangdale 10y ago
Full disclosure - I work on the Hyperscan project at Intel github.com/01org/hyperscan
Regular expression implementation is fun and many interesting things have been done in this area. We are partial to the work of Gonzalo Navarro (in terms of summary papers) and the Glushkov construction, which predates the Thompson NFA construction and IMO is better in a number of ways for fast implementation.
I quite enjoyed the Russ Cox posts, but they are a very partial and idiosyncratic picture of regular expression implementation. RE2 is one point in the automata-style regex implementation space; Hyperscan is another, and there a bunch of other distinct and interesting approaches (e.g. the work from the Parabix guys, various hardware and GPGPU implementations, etc).
- tannhaeuser 10y agoInteresting. The Glushkov construction is also used to decide ambiguousness of content models in SGML and XML. Moreover, it naturally extends to partial derivative-based automata as was used by Antimirov (might be interesting to the algebraically-minded FP folks on HN).
- harpocrates 10y agoSee, now _this_ is something interesting. When I get some time, I'll take a look at hyperscan. Looks pretty neat.
- burntsushi 10y agoAs the author of Rust's regex crate, Hyperscan is a work of art, both in terms of the algorithms it employs and its performance. (I don't think Hyperscan has been part of any publicized benchmark yet, so I'm only speaking with some limited experience I've had poking at it.)