How Regexes Work

Probably taken from yesterday's discussion: Ken Thompson's NFA regex patent

https://news.ycombinator.com/item?id=33566557

Always a worthy, related mention: https://swtch.com/~rsc/regexp/regexp1.html

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.

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.

Curious if this exponentially slow regex is the reason Notepad++ crashes on loading modestly sized (10 MB) JSON?