Rob Pike's simple C regex matcher in Go
I like the article that this post refers to about efficient implementation
(https://swtch.com/~rsc/regexp/regexp1.html). It mentions a debate between
J. Friedl and comp. sci. purists about whether NFAs and regular expressions should really be called what they are in the face of backreferences and other notation. Friedl suggests another name should be used, because de facto "NFAs"
are no longer equivalent to DFAs.Since Xerox Research Europe's invention of xfst, the term "extended regular
expression" is already taken for a specific superclass of expressions that
describe regular relations.So I propose two alternatives, semi-regular expressions and super-regular expressions, for strings that look like regular expressions but that use non-regular extensions like backreferences that push the complexity beyond what can be done with NDAs/DFAs.