Don't get me wrong: I like RE2. However, it's 2-3 fairly standard ideas taped together in an idiosyncratic way that happens to work pretty well for Google and many other users.
I will confess (having designed Hyperscan), that it's 200-300 ideas ranging from 'boring as heck' to 'wildly non-standard' taped together in a idiosyncratic way that happens to work pretty well for a different subset of users (mostly in much more heavyweight network IPS cases)
I frankly think we're still waiting for a 'gold standard' in regular expression implementation. I daydream of a system that doesn't have the elephantine complexity of Hyperscan (and isn't inherently tied to x86) but still supports large scale regular expression matching and streaming. Ideally this system would also not have the weird "corners" of RE2 (dynamically constructing a DFA at run-time).
Even nicer: native support for 'difficult' constructs like backtracking - by native I mean "one integrated algorithm" not "first one run approach, then run the other from scratch if the fast path matches".
Do you know of any resources describing how to handle 'difficult' constructs in DFAs? Capture groups, zero-width assertions, and high-trip-count loops are examples: these are all straightforward in pcre-style backtracking, but require novel techniques in DFAs. Some of these techniques are research papers (tagged DFAs), some are yet-to-be-written papers (re2 drives the loop "one ahead" for zero-width assertions), some are open questions. What's the path forward here?
Zero-width assertions are painful for automata-based approaches, especially forwards asserts. Backward asserts are easy in an bit-parallel NFA although I'm not aware of anyone actually doing that (you just need to have special "AND" states rather than the usual relation of being OR'd on if any of your predecessors are on). Even streaming would be doable.
As a rule, forward asserts are ugly and are "as easy to do as determinizing the two patterns together from that point on" - which can be trivial, or it can be a horrible world-smashing explosion.
High trip count loops were a lot of work in Hyperscan. We special-cased out the single-character width ones to properly handle /foo.{1500}bar/ and the like, but of course even Unicode can screw this up; something as trivial as /foo.{100,200}bar/ with anything but "dot means any single byte" - e.g. UTF-8, or even a 2-byte code unit of any size - much harder.
Wrapping a fully general regular expression inside a large bounded repeat is a nightmare. I have some ideas kicking around for how to do this that I've toyed with for years.
As might be apparent, I'm thinking of returning to the general regular expression fray (probably with a new project), so I've been thinking a lot about this stuff.
Or same with v8 and SpiderMonkey. They have a bunch of different optimization techniques tuned for specific workloads.
That is, regexes are a rich enough language now, with enough different use cases, that I think it will be true for any future implementation.
---
I think the articles themselves are great, but they're also pretty dense, and I wish there was a version for regex users, not implementers. It seems like people still have a lot of problems with the backtracking regex vs. regular language distinction in practice.
By contrast, both Hyperscan and RE2 have a tendency to just throw different, well understood techniques at the problem of matching regular expressions, without necessarily getting much decomposition of the problem. Hyperscan goes further but at great expense and complexity - and many of the decisions we made are very "one size fits all".
One of the consequences of this is that the regex vs regular language distinction you speak of tends to pop up aggressively and annoyingly, even when there are perfectly good possibilities for a solution that integrates automata and back-tracking based matching. RE2 handles this by taping back-tracking to a automata-based approach, and Hyperscan doesn't solve this at all (unless you count Chimera, which tapes libpcre to Hyperscan).
Users probably shouldn't have to know about the underlying engine, but the other problem of the idiosyncratic nature of all of our 'taping' jobs is that each system has weird corners that users can wind up suddenly finding out about (and often can't really control). My dream library would allow users to indicate which tradeoffs they want (potentially telling them to "go away" when they ask for the impossible or unimplemented; e.g. "I want fully general backreferences, streaming and fixed-sized stream state").
Many things may have changed since they were written, but as far as I can tell they haven't been demonstrated in a friendly way, i.e. with the short example code in those articles.
Is it the implementations, or is it regexes themselves? I was under the impression that SNOBOL/SPITBOL/REBOL was the gold standard... But I guess you're saying that given some (posix?) regex syntax, implementations can/should be improved? (while eg REBOL/Red-lang goes more towards "a more pragmatic regular language for pattern recognition", I guess ?)
Rebol and Red use embedded PEG parsers, which, by definition, support context-free, and not just regular, languages.
That would be a stretch goal for me: build a regular expression / automata library that's sufficiently modular to keep some components and drop in more expressive constructs (not necessarily PEGs, but maybe pushdown automata).
http://nim-lang.github.io/Nim/pegs.html
> Simple PEG (Parsing expression grammar) matching. Uses no memorization, but uses superoperators and symbol inlining to improve performance. Note: Matching performance is hopefully competitive with optimized regular expression engines.
It is indeed quite subtle to be "productive" (that's how we say we will explore both "+"). I wrote a paper about how to do it well a few years ago, with quite a few tricks: https://regex-generate.github.io/regenerate/
Eg you can say that if string s match expression e, than s should also match e|e'. (Where e' is some other expression.)
If you want arbitrary parsing, use a parsing library?
However, that doesn't mean we shouldn't strive for richer feature (within the confine of regularity), or that a parsing library automatically does the job better.
For instance: intersection and complement are regular operators that works very well in regular expressions. lookahead is a regular operator (lookbehind and backreferences are not), etc. Those operators do not necessarily work at all in richer parsing libraries. When added to regular expressions, they should be well handled and optimized by regex engines (which is is currently not the case). There's still work to do, features to add, which require appropriate testing techniques.
Regular languages are closed under a host of more interesting operations than those that have 'grown with the capabilities of our pattern matching engines'.
As the author of Perl's regex engine Larry Wall puts it[0]:
> “Regular expressions” […] are only marginally related to real regular expressions. Nevertheless, the term has grown with the capabilities of our pattern matching engines, so I’m not going to try to fight linguistic necessity here. I will, however, generally call them “regexes” (or “regexen”, when I’m in an Anglo-Saxon mood).
Do you mean write a process that enumerates all finite members of the regular language in question in finite time?
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.