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.
What really irks me that there are several useful operations that can be supported by proper regular expressions in linear time, but those franken-expressions never feature them.
Burntsushi (of regex crate / ripgrep fame) is on record saying[1] he thinks those are intractable in a standard DFA implementation on a large alphabet (Unicode), and if he can’t do it, I don’t think there’s much hope for the rest of us :) They are relatively straightforward in derivative-based implementations[2,3], but those are kind of meh performance-wise AFAIU, and just eagerly building the DFA using derivatives[4] yields huge automata.
(To be fair, the regex crate can’t match canonically equivalent Unicode strings, which I also think is pretty meh, but I’ve played with Unicode normalization recently and I’m convinced it would be impossible to support canonical equivalence with the same order of magnitude in performance without going through horrible contortions.)
> To be fair, the regex crate can’t match canonically equivalent Unicode strings, which I also think is pretty meh
Yeah not "meh" at all. :-) I don't think any regex engine can do it? Does icu's regex engine even do it? Certainly no fsm regex engine does.
UTS#18 doesn't even ask regex engines to do it. If you need it, it just suggests canonicalizing both the regex and the haystack first.
And yes, derivatives build full DFAs. Those are a no-go in a general purpose regex engine.
There's also the issue of complement and intersection being somewhat difficult to reason about.
I'll also note that I have never given any serious effort to actually trying to implement complement or intersection. I just don't see any viable implememtation path to it in the first place. I don't know where I would start. Everything I cam think of involves extreme compile-time costs that would just be totally unacceptable in a general purpose regex engine.
But, I am not really an "ideas" person. I see myself more as an engineer. So my inability should not really be taken for gospel. Be skeptical of expertise. That's the foundation of science. :)
Unless I can’t read, ICU4C does not even do streaming normalization, and the buffer-at-a-time one is around 100—200 MB/s or so[1], which looks ... mildly amusing next to your engine :) My own attempt at streaming normalization is currently about two times slower, because it has deeper (and smaller) tables and is just generally dumb, but then ICU4C is not particularly smart either. I expect that normalization at 2x ICU speed or more is possible, but that still won’t make normalize-then-match competitive with no normalization, while encoding all canonical equivalents into the DFA sounds downright hellish (also strictly speaking impossible, given normalization requires unbounded buffer space, but that part is probably solvable).
UTS #18 level 2 (which I’m aware you explicitly did not attempt) kind of says some things about canonical equivalence and then goes “nah, normalization is difficult, let’s go match grapheme clusters, also maybe just prenormalize to NFD”[2]. Which just looks weird, but apparently it means they did try to impose a requirement then gave up more than a decade ago[3]. Does anything even fully implement level 2, I wonder?
So, meh, but not really directed at you—regex is supernaturally fast as far as I’m concerned. Perhaps I’m annoyed at Unicode normalization for being (not really complicated but) so punishingly difficult to do quickly it isn’t really clear how you could wire it into a regex matcher.
There is also the question of how normalization-invariant regexes should even work: should “<C-caron>.” match “<C-cedilla><caron>”? UTS #18 (with invariance requirement restored) seems to imply yes, but it’s hard to imagine when anyone would actually want that. (Note that both pattern and haystack are normalized—the corresponding regex for NFD input would be something like “(C<caron>[[:ccc=0:][:ccc>=230:]]|C[[:ccc>0:]&[:ccc<230:]]<caron>)”, but nothing implements that syntax.) So while UTS #18 gives a possible interpretation of how Unicode regexes should work, I’m not entirely convinced it’s the right one, or even right enough to go on the crusade of implementing a normalization-invariant regex engine.
But I'm not sure how far they got. And most of the links on that page are dead. :-(
And yeah, UTS#18 actually used to have a level 3 (custom tailoring), but they removed it.
I'm content with level 1 support. The regex crate is just about there and that actually makes it have better Unicode support than the vast majority of regex engines. :-)
Alternatively: declare that "regex" has graduated into its own proper term (not a contraction) for whatever this evolving somewhat-too-capable-for-easy-classification tool is.
The term “regex” is already used interchangeably for both classes. The Go regular expression library (which is widely used) does not support backreferences, and is guaranteed to run in linear time.
It seems sillier to say “that’s not a regex” (since it definitely is a regular expression engine), than to say that the others are extended regular expressions or some other, more flexible thing (for better and worse).
I cannot agree here. The term "regular expression" relates to "regular language".
So instead of inventing new words haphazardly, we should look at what kind of language we are able to express with these non-regular expressions, what the name of that language is and then use that name for the expressions.
Here is a starting point: where do regular languages sit in the Chomsky hierarchy:
Here, we see that there are also less inclusive languages included in regular: finite languages and star-free languages, for which the corresponding "finite expression" and "star-free expression" make sense.
In the other direction, maybe some useful language kinds can be identified between "regular" and "context-free" in relation to the capabilities of certain kinds of expressions. However, "context-free expression" isn't a bad start. ("Cfex" [si:fex]?)
Of those, I'd prefer semi-regular expressions (but personally currently lean towards irregular expressions). As they lose the nice properties, there's certainly nothing "super"-regular about them.
Super-x may also mean that it has some extra properties wrt x. In fact, it was the original meaning that has drifted to its more common use today. Cf. “hyper” as in “hypersonic”. Both “super” and “hyper” even mean the same thing (“over”/“above”) in their original languages (Latin and Greek respectively).
I've read that article so many times I knew what it was by seeing the link. The first few times it didn't make sense, and now it seems almost obvious - I can't remember what I was not understanding.
Hah this is a classic. I actually used this as a reference to build my own about a year ago in typescript (documentation a long way to go and still WIP) which I am using in a couple of production ready dsls:
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.