Saxon

I think that worst-case regex performance is always going to be exponential in input sentence length and the only question is trying to avoid this worst-case effect as often as possible.

I'm surprised that replacing '(-|–|−)' with '\p{Pd}' should make any difference and I don't observe much effect from that change.

I'm not surprised that (^|\w+){1,5} should be inefficient and I'll see if there's any way the optimizer can be tweaked to recognise such cases. Reducing (\w+){1,5} to (\w+) is easy enough, but the "^" alternative complicates things a lot. I'm reluctant to put in an optimizer rule that will handle this special case and nothing else.

Between 9.5 and 9.6 we completely replaced the regex engine in Saxon, and it's not surprising that some cases optimised by one regex engine should not be optimised by another, and vice versa.

The capturing group also makes the rewrite more difficult: we don't know statically that regex-group() isn't being used and any rewrite of the regex therefore needs to preserve the semantics of capturing groups: that's a challenge. However, the spec gives implementations some flexibility: "For example given the regular expression (a*)+ and the input string "aaaa", an implementation might legitimately capture either "aaaa" or a zero length string as the content of the captured subgroup."

Maybe, instead of trying to improve performance for pathological fringe cases, issue a warning when the algorithm detects that it’s taking “too many” steps in relation to the input length?

Just an observation: the performance here depends on the length of the longest word. In the last example appears the 30-character word Finanzstabilisierungsfazilität. The expression (^|\w+){1,5} is going to try and match this in something like 3029282726 different ways; that is, the performance is O(N^5) where N is the length of the longest word. This is why changing it to {1,3} makes a big difference.

(Just realised that the way I wrote that is in German word order; clearly reading this text has activated my German-speaking brain circuits!)

The classic way that some regex engines avoid exponential performance in such cases is by performing a single scan of the input, keeping track of all the possible states in the FSA at each step. So after reading "F" the only possible counter values are (11); after reading "Fi" they are (21) and (12); after "Fin" the possible combinations are (31), (21 + 11), (12 + 11), (1*3). The number of possible states here is O(n^2) because there are two nested loops. The problem is that (a) although this approach avoids the worst-case performance problems, it's not better at handling typical cases, and (b) it's hard to see how to do it without a total rewrite.