3 ms·
Yeah, it’s vexing. This backtracking / NFA / DFA confusion originally came from Jeffrey Friedl’s book “mastering regular expressions” (O’Reilly, 1997) — at leas
by fanf2 2y ago
Yeah, it’s vexing. This backtracking / NFA / DFA confusion originally came from Jeffrey Friedl’s book “mastering regular expressions” (O’Reilly, 1997) — at least, that’s the first place I saw the mistake in print. Philip Hazel relied a lot on Friedl’s book when writing PCRE, which is why the PCRE docs get it wrong. (I spoke to Philip about this many years ago when we worked together.)
- burntsushi 2y agoYeah I didn't mention Friedl because I've dumped on him in the past, and didn't want to belabor it. But Friedl definitely didn't start this. According to him, he was just using what was common vernacular even back then: http://regex.info/blog/2006-09-15/248 http://regex.info/blog/2006-09-15/248 (Note that blog is from 2006, but he's actually quoting himself from ~10 years prior to that in 1997.) But... he is the one who ultimately installed this ambiguity into a classic book that is still read to this day. So I think he can at least be blamed for popularizing the confusion. And especially since the entire book is framed around "NFA" and "DFA" regex engines. It's not like it was just some one-off mention. The mix-up is baked into the conceptual fabric of the book. The landscape also looked different back then. It predated RE2 for example, and RE2 is, I think, principally responsible for bringing "backtracking semantics" to finite automata oriented engines. So Friedl's book is forever stuck in a false dichotomy that only happened to exist back when he wrote it.
- mikeqq2024 2y agoThanks for the detailed explanation to grok the whole landscape.