5 ms·
I learned the specific 're1 string re2' decomposition with backward matching from Hyperscan but AFAIK several fast grep-oriented regex engines factor out both p
by psykotic 6y ago
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.
- burntsushi 6y agoThe 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.
- jwilk 6y agoRuss Cox's article in question: https://swtch.com/~rsc/regexp/regexp3.html https://swtch.com/~rsc/regexp/regexp3.html