RegExp Lookbehind Assertions | Hacker News Reader

RegExp Lookbehind Assertions

v8project.blogspot.com

28 pointsshawndumas17 comments

Wow, I didn't even know there was a different way to implement lookbehinds in such a way that variable-length patterns were even allowed:

> Generally, there are two ways to implement lookbehind assertions. Perl, for example, requires lookbehind patterns to have a fixed length. That means that quantifiers such as or + are not allowed. This way, the regular expression engine can step back by that fixed length, and match the lookbehind the exact same way as it would match a lookahead, from the stepped back position.*

> The regular expression engine in the .NET framework takes a different approach. Instead of needing to know how many characters the lookbehind pattern will match, it simply matches the lookbehind pattern backwards, while reading characters against the normal read direction. This means that the lookbehind pattern can take advantage of the full regular expression syntax and match patterns of arbitrary length.

> Clearly, the second option is more powerful than the first. That is why the V8 team, and the TC39 champions for this feature, have agreed that JavaScript should adopt the more expressive version, even though its implementation is slightly more complex.

regular-expressions.info has roughly the same explanation here: http://www.regular-expressions.info/lookaround.html

I guess I had just assumed that if even Perl didn't implement variable-length lookbehinds, then the performance or implementation cost must have been severe enough to justify leaving out such useful flexibility. What is the tradeoff that .NET and now JavaScript are willing to make?

edit: According to a comment in the posted article, Perl 6 now implements variable-length lookbehinds http://www.perl6.org/archive/rfc/72.html

20-odd years of Moore's law?

Implementing lookbehind by reading backwards is not more computationally expensive than reading forward. It adds some complexity to the regexp engine, yes, but that's manageable.

There are some quirks vs. stepping back and reading forward, like the article already explains.

I guess Perl initially just did not implement it this way, whatever the reason was.

> Yang Guo, Regular Expression Engineer

Interesting and specialized job :-)

To clarify, this is not a real job title. Chrome and V8 blog posts are written by engineers who worked on the feature being blogged about, and can choose a funky title to go with the name :)

I use regex quite often and I'm happy we have it now more powerful in Chrome. Though, what is so painful in regex is all those flavors of it. I with it was standardized across all languages / implementations.

I wonder what code could profit from such a niche feature. I cannot even imagine a situation where I would want to use this.

Ever used \b? This is like that, but for other patterns. Very useful in many situations, like tokenizing (because you have to match on things the last match already consumed).

Maybe I've used \b before, but I can't recall using regexes for tokenizing. They've either been too powerful or not powerful enough for my tokenizing needs.

I usually use look ahead negation to make tests that string doesn't match regex.

What do you mean by "usually"? What situation calls for this? I wonder why people seem to consider this a worthy addition where in my view it only serves to complicate the implementation.

From what I see these additions become useful long past the point where using a regex was sensible in the first place.

I've used lookbehind assertions (and negative lookbehind assertions) many times. Most recently I used them to do some complex find/replaceing across a pretty large codebase. My editor supports regex, and I'm glad it does because it made the job easy.

From what I see these additions become useful long past the point where using a regex was sensible in the first place.

Regex stops being a sensible solution when your pattern starts getting overly complex. The fact that you use one of these features doesn't imply your pattern is overly complex. These are not complex features, they're easy to use, and often extremely useful. For example when straightforward find/replace doesn't cut it. What would you suggest, I take 10 minutes to write a Python script for what took me about 15 seconds in my editor's Find/Replace box?

I see how this can be useful for ad-hoc replacements.

To clarify, I'm not asking about the usefulness of the feature in general but why it makes sense to add this to JS.

Because JS is a general purpose language?

I once argued that it `could not be so hard to write a regexp that validates Debian package versions`. Ohboy. Let's just say that in the end it became a point of pride to come up with something.

Debian package version numbers have leading and trailing optional parts and if they are specified, then the characters used as separator of these parts are allowed as part of the version number.

The resulting regexp ended up being essentially four different regexp expressions with four leading conditions utilizing look-ahead and look-behind matching to select which inner regexp to use. It was sufficiently beyond actually regular, even if supported by modern RE tools.

And this is a common pattern in my experience. If you frequently need look-ahead or look-behind, you are often past something you should reasonably disassemble using regexp and should instead start defining a grammar and parse the input stream against it.

The Debian version format was not made to be easy.

https://www.debian.org/doc/debian-policy/ch-controlfields.ht...

But in any case, this works.

  ^(\d+:|(?!.*:))(?!.*-[^-]*:[^-]*$)\d(-?[A-Za-z0-9.+:~])*$

Actually, I think I variable-width lookbehind might be handy here to check the hyphens, but I don't have Chrome 49, so I'll forgo it.

I'd contend that it was "made" at all.

When I first looked at the relevant section of the policy manual, my takeaway was that they had a script that iteratively removed the leading and trailing optional fields, making use of the separators safe only if the fields were there so the script did not misfire.

They then took the runtime behavior of that existing script and called it the standard.

Reply on news.ycombinator.com