Hacker News Reader

Comment by kccqzy | Hacker News Reader

Russ Cox's articles on regex engine remain the gold standard: https://swtch.com/~rsc/regexp/

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.

View on HN

They really don't (remain the gold standard, that is).

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".

Hyperscan may be idiosyncratic but is quite an accomplishment, and by all accounts the fastest there is, kudos!

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?

These difficult constructs are a brace of unpleasant questions, all quite distinct. Laurikari has some good work on capturing; we also did capturing in Hyperscan in an unreleased branch during the closed-source days (idea: run a trace of states from the NFA backward, then follow the trace forward, emulating what a backtracker would do).

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.

I feel like this is like describing GCC or Clang as "a bunch of ideas taped together". That is more or less true but also fails to capture a pretty big achievement.

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.

GCC and Clang have phases that communicate synergistically. If I'm working on instruction scheduling, I can get the benefits of an upstream pass that did code motion. Conversely, if I'm working on a backend for x86, I can both share benefit of the front-end generic optimizations with an ARM backend [ edit: and not be concerned about what's going on in the other backend as well ]

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").

Hm decomposing the problem and integrating automata and backtracking sound interesting. Although I'll say you can't claim that the RE2 articles aren't the gold standard if you haven't worked on or published this yet! :) (as code or prose)

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.

> I frankly think we're still waiting for a 'gold standard' in regular expression implementation.

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/Red-lang goes more towards "a more pragmatic regular language for pattern recognition"

Rebol and Red use embedded PEG parsers, which, by definition, support context-free, and not just regular, languages.

I'm fascinated by PEG parsers, but I don't know whether they can be implemented in a way that's remotely as performant as even mediocre regular expression implementations, much less tuned SIMD extravaganzas.

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).

Not, sure - but I just came across this in the Nim standard library:

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.

I've written a lot of things that are "hopefully competitive" with something else, but generally benchmarking is the ideal. :-) Hard to benchmark PEG vs regex fairly. Not dismissing it out of hand, as I've had many years to observe the weak spots of regex at quite a short distance.

Proper regular expressions don't need backtracking.

Creating strings that match a regex can be very useful for testing too, as it allows you to fuzz a regex engine without using another regex engine as oracle.

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/

You can use the regular expression engine itself as an oracle to some extent.

Eg you can say that if string s match expression e, than s should also match e|e'. (Where e' is some other expression.)

That is very limited in practice. In my experience, it doesn't scale to more complex features.

Well, regular languages are a specific, well defined subset of all formal languages.

If you want arbitrary parsing, use a parsing library?

I disagree with the sibling comments: regular expressions should still be about regular languages. It's not because Larry Wall committed yet another atrocity that we should all follow him off the cliff. Perl can keep its monster.

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.

Indeed, that's my opinion as well.

Regular languages are closed under a host of more interesting operations than those that have 'grown with the capabilities of our pattern matching engines'.

Regex engines don't just parse regular languages - that ship sailed a long time ago. As I understand it, any regex engine supporting backtracking is no longer working with regular languages.

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).

[0] https://raku.org/archive/doc/design/apo/A05.html

Another interesting exercise is generating a uniformly random string of length N of a given regular expression (that has no limits on number of characters).

What do you mean by 'fully match'?

Do you mean write a process that enumerates all finite members of the regular language in question in finite time?

The second part seems related to logic programming, branch interleaving, etc.

Reply on news.ycombinator.com