5 ms·

The article by Russ Cox [0] (from which the initial Perl vs. Thompson NFA graph is taken) is a much more informative read. Also, I'm not sure why this always ge

The article by Russ Cox [0] (from which the initial Perl vs. Thompson NFA graph is taken) is a much more informative read. Also, I'm not sure why this always gets brought up as being a big deal: CS is all about making the right tradeoffs and I agree that sometimes there are cool tricks that let you _almost_ have your cake an eat it. But here, there is no such trick: backtracking has always been exponential and finite state automata have always been linear. No surprises. [0] https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html

wohlergehen 10y ago
Respectively exponential or linear in the input size. The NFA in exchange is exponential in the states (or rather, it's deterministic counterpart is).
btilly 10y ago
There are some more gotchas. The finite state automata can potentially be exponential in the size of the regular expression you feed it. (Its states are set of states in the NFA.) Subexpression matching is more complex to implement and can make that exponential superexponential. (You have to go from sets of states to ordered sets of states.) And these catastrophic expressions get much easier when you add in lookaheads, look behinds, and so on.
lobster_johnson 10y ago
The lack of lookahead is a pain in Go's regexp engine, and this cascades to the various apps that use it, such as Prometheus and Kubernetes. Mainly, it means it's super awkward — arguably so awkward it's completely impractical, because the result ends up being unreadable and probably slow — to do negative matching, i.e. exclusion.
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 ago
  Interesting. 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 ago
  See, now _this_ is something interesting. When I get some time, I'll take a look at hyperscan. Looks pretty neat.
  - burntsushi 10y ago
    As 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.)

wohlergehen 10y ago

Respectively exponential or linear in the input size. The NFA in exchange is exponential in the states (or rather, it's deterministic counterpart is).

btilly 10y ago

There are some more gotchas. The finite state automata can potentially be exponential in the size of the regular expression you feed it. (Its states are set of states in the NFA.) Subexpression matching is more complex to implement and can make that exponential superexponential. (You have to go from sets of states to ordered sets of states.) And these catastrophic expressions get much easier when you add in lookaheads, look behinds, and so on.

lobster_johnson 10y ago

The lack of lookahead is a pain in Go's regexp engine, and this cascades to the various apps that use it, such as Prometheus and Kubernetes. Mainly, it means it's super awkward — arguably so awkward it's completely impractical, because the result ends up being unreadable and probably slow — to do negative matching, i.e. exclusion.

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 ago
Interesting. 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 ago
See, now _this_ is something interesting. When I get some time, I'll take a look at hyperscan. Looks pretty neat.
- burntsushi 10y ago
  As 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.)