Note that when you use grep, awk, sed, libc regexec(), RE2 [1], or rust/regex, this isn't how your regexes are executed.
They use automata-based engines whereas this is a backtracking engine, which can blow up on small inputs. (Although I will say the C code here is cool, because it gives you a fork() bomb, so it might exhaust your operating system and not just your CPU!)
Canonical reference: Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)
https://swtch.com/~rsc/regexp/regexp1.html
Archive since it's down at the moment due to some App Engine stuff (!): https://web.archive.org/web/20200624195819/https://swtch.com...
My blog post and sample code that verifies that GNU grep, awk, sed, and libc don't backtrack:
Comments on Eggex and Regular Languages http://www.oilshell.org/blog/2020/07/eggex-theory.html
https://github.com/oilshell/blog-code/tree/master/regular-la...
[1] https://github.com/google/re2
----
Also, the production quality way of compiling regular expressions to C code looks like this [2], which is completely different than what's shown in the article:
https://www.oilshell.org/release/0.8.pre8/source-code.wwz/_d...
The regex is converted to an NFA, then a DFA, then a bunch of switch/goto statements in C that implement the DFA.
This example is huge, but the switch/goto and lack of any notion of "threading" is the important point.
Essentially, the instruction pointer is used as the DFA state. It's a very natural use of "goto" (where you don't write or debug them yourself)
[2] via http://re2c.org/ (not related to RE2)
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:
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.