Hacker News Reader

For me the same. Funny, as Friedl does barely discuss the ERE and awk (DFA) implementations at length. It is a shame, as the `more interesting` NFA implementations have performance issues under some circumstances. I had hoped the dilemma and engineering decision between features of NFA and guaranteed performance of DFA would get a more realistic discussion.

View on HN

For a discussion of the "DFA" engines, I'd recommend Russ Cox's article series.

The NFA implementations you speak of have problems because they use backtracking and take worst case exponential time. Most implementations are in fact not NFAs, since for example, an NFA is not a powerful enough tool to resolve backreferences (which are NP-complete).

Both NFAs and DFAs in fact have equivalent computational power, and either can be used to perform regular expression matching in linear time. There are of course lots of performance differences in practice.

Friedl's book is great for what it is: a guide to optimizing regexes that search via backtracking.

Reply on news.ycombinator.com