Hacker News Reader

Comment by beardyw | Hacker News Reader

Does anyone consider RegEx to be standardised? Moving to a new context is always a relearning exercise in my experience.

View on HN

At some point, I felt like I knew them all. There are probably more regex dialects out there, but I don't encounter them and my set of knowledge works most of the time.

I feel it's like driving a rental car. It behaves slightly different than your own car, some features missing, some other features added, but in general, most of the things are pretty similar.

What a nice analogy. I’ll borrow it in the future.

The ISO/IEC 14882 C++ standard library <regex> mandates [0] implementations for six de jure standard regex grammars: IEEE Std 1003.1-2008 (POSIX) [1] BRE, ERE, awk, grep, and egrep and ECMA-262 EcmaScript 3 [2].

So, yes, at least someone (me) considers regex to be standardized in several published de jure standards.

  [0] https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3690.pdf#chapter.28
  [1] https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap09.html
  [2] https://262.ecma-international.org/14.0/#sec-regexp-regular-expression-objects

"At least six different standards" is an XKCD comic, not a standard.

"The nice thing about standards is that you have so many to choose from." - Andrew Tanenbaum (or Grace Hopper)

<regex> is not exactly an example anyone should follow.

You may be prejudiced against C++, but ISO/IEC 14882 is a published international standard that links to recognized regex standards, so answers the question "does anyone consider RegEx standardised?" very much in the affirmative.

The three big ones I know of are POSIX, Perl/PCRE(aka Perl-Compatible Regular Expression), and Go came along and <strike>added</strike> used re2, which is a bit different from the first too.

A lot of systems implemented PCRE, including JavaScript, since Perl extended the POSIX system with many useful extensions. IIRC, re2 tries to reign in on some of the performance issues and quirks the original systems had, while implementing the whole thing in Go.

edit: Did not realize re2 predated go ...

re2 predates Go and was written in C++.

Go's regex implementation is new in the sense that it's not just a binding to the re2 C++ library, but it uses the same non-backtracking algorithm.

POSIX and PCRE are arguably redundant. They both support backreferences, which puts very significant constraints on their implementations. PCRE is at least functionally a superset of POSIX, whether or not there's some quirky thing POSIX supports that PCRE does not.

re2 adds a legitimate option to the menu of using NDFAs, which have the disadvantage of not supporting backreferences, but have the advantage of having constrained complexity of scanning a string. This does not come for free; you can conceivably end up with a compiled regexp of very large size with an NDFA approach, but most of the time you won't. The result may be generally slower than a PCRE-type approach, but it can also end up safer because you can be confident that there isn't a pathological input string for a given regexp that will go exponential.

This is one of those cases where ~99% of the time, it doesn't really matter which you choose, but at the scale of the Entire Programming World, both options need to be available. I've got some security applications where I legitimately prefer the re2 implementation in Go because it is advantageous to be confident that the REs I write have no pathological cases in the arbitrary input they face. PCRE can be necessary in certain high-performance cases, as long as you can be sure you're not going to get that pathological input.

RE engines don't quite engender the same emotions as programming languages as a whole, but this is not cheerleading, this is a sober engineering assessment. I use both styles in my code. I've even got one unlucky exe I've been working with lately that has both, because it rather irreducibly has the requirements for both. Professionally annoying, but not actually a problem.

I'll add two notes to this:

* Finite automata based regex engines don't necessarily have to be slower than backtracking engines like PCRE. Go's regexp is in practice slower in a lot of cases, but this is more a property of its implementation than its concept. See: https://github.com/BurntSushi/rebar?tab=readme-ov-file#summa... --- Given "sufficient" implementation effort (~several person years of development work), backtrackers and finite automata engines can both perform very well, with one beating the other in some cases but not in others. It depends.

* Fun fact is that if you're iterating over all matches in a haystack (e.g., Go's `FindAll` routines), then you're susceptible to O(m * n^2) search time. This applies to all regex engines that implement some kind of leftmost match priority. See https://github.com/BurntSushi/rebar?tab=readme-ov-file#quadr... for a more detailed elaboration on this point.

Excellent, thank you.

> RE engines don't quite engender the same emotions as programming languages as a whole, but this is not cheerleading, this is a sober engineering assessment.

Good on you.

I love when people pat themselves on the back for being pragmatic. Why wait for others to compliment you when you can do it yourself? (that’s very pragmatic self-care)

Languages invented after Perl will generally use some flavor of Perl regex syntax, but there are always some minor differences. The issue of the meaning of `$` and changing it via multi-line mode is usually consistent though.

I like to think of "whatever browsers do in js" as an updated common baseline. Whatever your regex engine does, describe it as a delta to the js precedent. That thing is just so ubiquitous.

I do wonder though what's the highest number of different regex syntaxes I've ever encountered (perhaps written?) within a single line: bash, grep and sed are never not in a "hold my beer" mood!

Reason #2 to use powershell - consistent regex.

I've got "hold my beer" commits in .net - I've balanced brackets. I believe that's impossible in sed and grep. If I were going to write a json parser in a script, then a) stop me and b) it's got to be in powershell.

That seems like just a web front-end developer’s perspective.

Isn't JavaScripts regex one of the worst modern regex implementations?

They seem to improve. Negative lookbehind isn't missing anymore [1]. But still lack the handy \Q and \E to escape stuff [2].

[1] https://stackoverflow.com/a/3950684

[2] https://stackoverflow.com/q/6318710

I’ll go along with that, as long as someone ports pcre to JavaScript and that’s the browser syntax we land on.

> I do wonder though what's the highest number of different regex syntaxes I've ever encountered (perhaps written?) within a single line: bash, grep and sed are never not in a "hold my beer" mood!

Your comment is missing a trigger warning, lol. But seriously, this is one of my flags for "this should probably be a script, or an awk or perl one-liner."

Delightfully, RFC 9485 https://datatracker.ietf.org/doc/rfc9485/ "I-Regexp: An Interoperable Regular Expression Format" was published just back in October last year!

My working assumption has always been to check the docs of your specific regexp parser, and to write some tests (either automated or manually in a REPL) with specific patterns that you are interested in using.

My understanding is it was standardised for Posix but the variants in popular use have so many variations.

I consider sed to be the baseline. If you can do sed you can do anything but it’s seriously limited.

POSIX specifies two flavours of regular expressions: basic regular expressions (BRE) and extended regular expressions (ERE). There are subtle differences between the two and ERE supports more features than BRE. For example, what is written as a$bc$\{3\}d in BRE is written as a(bc){3}d in ERE. See https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1... for more details.

The regular expression engines available in most mainstream languages go well beyond what is specified in POSIX though. An interesting example is named capturing group in Python, e.g., (?P<token>f[o]+).

Indeed, and the most common is Perl since it was the source of many of the extensions.

I would hazard that nowadays it’s Java due to its broad permeation of the application space

If anything it would be ECMAScript (JavaScript dwarfs Java use) or PCRE (the de-facto contiuation of Perl regular expressions written in C but used in many languages).

Yes I think you’re right actually. I’m about 10 years off :)

> what is written as $f..$\1 in BRE is written as (f..)\1 in ERE

Oddly, there are no backreferences in POSIX EREs.

You are right indeed. Looked at the specification again and indeed there is no back-reference in POSIX ERE.

Quoting from <https://pubs.opengroup.org/onlinepubs/9699919799.2008edition...>:

> It was suggested that, in addition to interval expressions, back-references ( '\n' ) should also be added to EREs. This was rejected by the standard developers as likely to decrease consensus.

Updated my comment to present a better example that avoids back-references. Thanks!

That’s because POSIX EREs are actual regular expressions thank god.

No gnu tool can balance brackets, afaics. So you can't do everything in sed. And sed is, by design, useless for matching text that spans lines, so good luck picking out paragraphs with it.

Sorry I meant to write “if you can do it in sed you can do it in anything” thereby implying it is a subset of the more generally available flavours. The issue at hand however is that there isn’t much in the way of standardisation but 95% of sed should work across all of them. Of course you should get more into the specifics of whatever your solution space supports.

I am pretty sure even pure Awk can do it; or am I mistaken? I thought there was an even more sophisticated example in the Awk book.

Edit: oh, you mean via regex engines available in GNU tools; I am dumb. Hmm... is there no GNU extension with PCRE?

"Sed" is the name of a specific tool. It is not defined by the GNU tools, but has existed in some form since 1974, well before Perl. GNU sed and POSIX sed both support BRE and EREs, but not PCREs.

Maybe there's some other implementation of sed that supports PCREs but that would really be an extension of that implementation of sed rather than a property of sed.

And maybe there's some GNU tool that uses PCREs, but that GNU tool would not be GNU sed, so it would not be a relevant property.

Anyway, they probably should have said BREs or EREs rather than "sed"...

Nope. Gnu regex tools also do not support lookahead or alternation. Lookahead is really useful.

It's a problem for Linux that it can't move on. The cold dead hand of gnu is firmly around the community's neck.

> the cold dead hand …

Android, Busybox and Muscl have entered the chat

And don't get me started about find and replace, what is the symbol to insert the match?

kind of a trick question; there is POSIX and then there is the app you're using and whichever flags are enabled (albeit by default or explicitly defined)

Reply on news.ycombinator.com