Ken Thompson's NFA regex patent (1971)

https://patents.google.com/patent/US3568156A/en

by jonstewart • 4 years ago

120 20 4 years ago

patents.google.com

jonstewart• 4 years ago

ken also wrote a paper about his algorithm, published in CACM in 1968: https://dl.acm.org/doi/pdf/10.1145/363347.363387 (PDF)

HellsMaddy• 4 years ago

https://en.wikipedia.org/wiki/Thompson's_construction

ape4• 4 years ago

Do current regex implementations use this algorithm?

bla3• 4 years ago

Most don't, but re2 and a few others do. The ones that do use it don't have exponential runtime on malicious inputs and lack a few features (back references, mostly). https://swtch.com/~rsc/regexp/ is a great resource on this.

iron2disulfide• 4 years ago

Most don't

Is this true? I'm pretty sure that most of the regex engines I've used (grep, ripgrep, re2, hyperscan) use Thompson's construction or at least some NFA-based algorithm (not necessarily Thomopson's; Glushkov automata in particular are used by hyperscan).

klodolph• 4 years ago

As a side note, when converting the NFA to a DFA, you get an exponential number of states, since each DFA state corresponds to a set of NFA states.

yarg• 4 years ago

Most modern 'regex' implementations don't actually implement regular grammars.

I think they're generally closer in power to PDA.

https://en.wikipedia.org/wiki/Pushdown_automaton

Kranar• 4 years ago

Yep absolutely, almost all of them are more powerful than PDAs and in fact Perl's are Turing complete.

joedrago• 4 years ago

I read an article a million years ago which I thought described this mechanism in a super friendly way:

https://perl.plover.com/Regex/article.html

It uses the idea of "putting a penny down" on the graph and moving it around, and I found the conversational tone of the description to be very easy to grok. Assuming this is the exact same mechanism (which the author cites), it might resonate for some of you too.

jedimastert• 4 years ago

Holy smoke, what an amazing article. This has nagged the back of my brain for a very long time.

photochemsyn• 4 years ago

Nice article. On this bit: " It's about how you would write a regex package from scratch, in a language like C that doesn't already have regexes."

There's a 30-line C regex matching program that Rob Pike wrote and Brian Kernighan wrote about here. It only implements . ^ $ * (where c is any literal):

"A Regular Expression Matcher" (2007)

https://www.cs.princeton.edu/courses/archive/spr09/cos333/be...

"Rob's implementation itself is a superb example of beautiful code: compact, elegant, efficient, and useful. It's one of the best examples of recursion that I have ever seen, and it shows the power of C pointers. Although at the time we were most interested in conveying the important role of a good notation in making a program easier to use and perhaps easier to write as well, the regular expression code has also been an excellent way to illustrate algorithms, data structures, testing, performance enhancement, and other important topics." - Brian Kernighan

tgv• 4 years ago

As I said before: that's a simple backtracker with exponential complexity, and it adding more operators will trigger that behavior faster. I think Thompson's NFA matcher is O(n m), but I didn't check the patent. If it isn't, it's fairly easy to make it that.

Cupertino950142• 4 years ago

Does anyone know if this patent was ever asserted by AT&T? (Of course, it's long expired.)

bodhiandphysics• 4 years ago

He did it before he was at bell labs

Cupertino950142• 4 years ago

The patent's assigned to AT&T, though. If that was in effect before it expired, A&T could have asserted it.

Ken Thompson's NFA regex patent (1971)

Related Stories