Hacker News Reader

By any chance, do you know an example of a regex library or tool that uses that backwards-matching trick?

I learned the specific 're1 string re2' decomposition with backward matching from Hyperscan but AFAIK several fast grep-oriented regex engines factor out both prefixes and suffixes and use whichever is longer/most rare as a substring anchor. For the suffix case you need backward matching to confirm the regex match after the substring match. Hyperscan actually decomposes the entire state machine graph into 're1 string re2' style fragments, which lets them select the fastest implementation technique for each sub-machine.

I think Russ Cox talks about backward matching in his article series on regular expressions, so it's probably used somewhere in re2.

The grep-oriented tools have it a bit easier. They can (and do) extract inner literals as well. The trick is that the search is line oriented and lines tend to be small. So when you find a match for an inner literal, all you need to do is find the bounds of the line that contains the literal and run the full regex engine on just that line. It works extremely well when matches are somewhat rare.

As for RE2, backward matching is used to find the starting location of a match.

Russ Cox's article in question:

https://swtch.com/~rsc/regexp/regexp3.html

Reply on news.ycombinator.com