"Regular Expression Matching Can Be Simple And Fast" (2007)

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

Regular languages are also closed under intersection and taking prefix etc (see https://en.wikipedia.org/wiki/Regular_language#Closure_prope...), and if you want to expose those operators in your regular expressions, Russ Cox's technique doesn't really work.

I also suspect that this might result in a combinatorial explosion of fused terms, but that's irrelevant as we're only worried about whether intersection can be implemented in Russ Cox's method, not whether a regular expression might require several earths or so worth of RAM to hold :)

Nothing in the wiki article mentions taking a prefix, but that just sounds like `(prefix|)`?

As you point out Russ Cox's method can not deal with complement and intersection. You can hack it up by putting a compiler in front, but then you might as well compile to finite automata directly. Or you use derivatives: https://en.wikipedia.org/wiki/Brzozowski_derivative or https://www.ccs.neu.edu/home/turon/re-deriv.pdf (or https://well-typed.com/blog/2020/06/fix-ing-regular-expressi... for a Haskell flavour).

> Nothing in the wiki article mentions taking a prefix, but that just sounds like `(prefix|)`?

They implicitly mention prefixes, when they talk about 'the trio operations: string homomorphism, inverse string homomorphism, and intersection with regular languages.' If I remember right, the prefix operation is:

Take a language L, restrict it to the strings that have the right prefix: `L' := L & (prefix.*)` then chop off that prefix from every member of L'.

See https://en.wikipedia.org/wiki/Quotient_of_a_formal_language which this is a special case of. The Brzozowski derivative article also explains it in more detail.

Which is why the "RE" in the article is excrutiatingly slow, given that it needs to perform insane amounts of backtracking. In contrast, "real" regular expression checkers run in linear time.

Also, nitpicking, but they take unbounded time. It's still finite.

The inflationary use of "infinite" especially in tech crowds that should know better deserves pushback.

There are models of computation that actually model infinite computation. A well-studied one is Büchi automata, basically a generalization of finite state automata to infinite sequences.

> And I’m not sure about unbounded; surely it is bounded by a suitable exponential function?

Nope. You can nest them and for any function that you give you can produce a RE that takes longer than that function to evaluate. (That's literally what "unbounded" means. There is no bound. Doesn't mean it's "infinite". All those computations terminate, which is literally what "finite" means in this context.)

Nope.

> Perl regexes have become a de facto standard, having a rich and powerful set of atomic expressions.