Probably taken from yesterday's discussion: Ken Thompson's NFA regex patent<p><a href="https://news.ycombinator.com/item?id=33566557" rel="nofollow">https://news.ycombinator.com/item?id=33566557</a>
Always a worthy, related mention: <a href="https://swtch.com/~rsc/regexp/regexp1.html" rel="nofollow">https://swtch.com/~rsc/regexp/regexp1.html</a><p>Another fun idea is the opposite of the regex: the regex constructs a state machine of the needle and is then quickly able to run many haystacks through it. Sometimes you need the other optimisation: compile the entire haystack down to a state machine, and you can run many needles through it! It becomes a very primitive search index.
I worked briefly with Mark-Jason Dominus in 2000. He added instrumentation to the Perl regex engine so that we could develop a regex debugger for the forthcoming Komodo editor. Each time the engine advanced to process the next step, we would get a callback that included vital information such as the location in the regex string and the target string.<p>Today, there are numerous excellent tools like this on the web. Back in 2000, it was dark magic and so much fun to work on.