Russ Cox

I personally had the most trouble with regexes because I didn't have a good mental model of how they worked. The hard part wasn't finding the correct symbol/character class I was trying to match, but coming to grips with repetition, greedy/nongreedy, etc.

I took a compilers class in college where one of the projects was to implement a simple regex matcher using NFAs. Bashing my head against this for a week really helped with being able to "read" a regex. Not sure if this was due to finally understanding the algorithm, or the fact that I was just constantly staring at broken regex matches all day.

IMO it was a fairly small time investment for something that is so widely used.

I'll recommend this post that's been on HN many times: https://swtch.com/~rsc/regexp/regexp1.html

Regexps is another area where GoLang used to lag behind Python (for certain types of expressions?). Not sure if things have changed, but this issue is still open 4 years later: https://github.com/golang/go/issues/11646

Not sure I fully understand the NFA vs DFA/re2 choices -- seem like the issue above conflicts with the comment below. Can someone clarify?

From [1]: "Go has chosen to follow the re2 path (not surprising, since Russ Cox is a major author of both Go and re2). re2 has much better performance characteristics than some other regexp engines, in that it never has an exponential slowdown, but that comes at a cost for other regexps (https://swtch.com/~rsc/regexp/)."

[1] https://www.reddit.com/r/golang/comments/84o986/why_is_gos_regex_so_slow/

It's worth pointing out that the resource

https://swtch.com/~rsc/regexp/regexp1.html

linked above is also by the same author, Russ Cox,

as the reference I included at the end of the blog post:

https://swtch.com/~rsc/regexp/regexp2.html

All of the insights that I presented through this visualization tool are based upon the knowledge found in Russ Cox's articles. Also, the link above on RE2:

https://github.com/google/re2

is a project that was was also (started by|heavily contributed to by) Russ Cox. His writings on the topic of regular expressions are absolutely world-class and I have never found any better resource for understanding the deep low-level theory on how they work in practice.

Russ Cox's articles on regex engine remain the gold standard: https://swtch.com/~rsc/regexp/

I remember having built my own regex engine (for educational purposes only) following his articles almost a decade ago. Great fun.

Another fun thing you can do (and I have done) is that given a regex, construct strings that fully match the regex. It's not hard at all, but it's quite subtle if you want good results. For example given the regex "a+b+" the code can simply create strings like "ab", "aab", "aaab"... (with one "b" always), but it is slightly more challenging to have it output "aab", "abb", "aabb", etc, which involves forming the Cartesian product of infinite streams in a smart way.

> Having worked in an industry where the linear vs. exponential performance implications of regular expressions and PCREs was crucial (intrusion protection systems)

same boat. that's why we use re2 in a way inspired by Go (which means losing a few features but the tradeoff is worth it):

> The regexp implementation provided by this package is guaranteed to run in time linear in the size of the input. (This is a property not guaranteed by most open source implementations of regular expressions.) For more information about this property, see

> https://swtch.com/~rsc/regexp/regexp1.html

> or any book about automata theory.

https://pkg.go.dev/regexp

Admittedly I haven't stepped through all the code, but it's 958 lines and doesn't look horrible. It somewhat resembles the example C programs here:

https://swtch.com/~rsc/regexp/

In particular there don't seem to be crazy optimizations and non-portable stuff like you see in other production regex implementations and in interpreters. It's pure ANSI C.

The functions are all short -- no 1000 line monsters like I've seen in a lot of old C code lately.

The rsc example code is actually a great example of using pointers in C. People rightly avoid lots of raw pointers for application code, but for this use case, they yield compact and elegant code.