Regex backtracking on simple pattern

Question

I've got this code in Mathematica that fetches the left or right side of an equation by turning it into pure text then textually getting rid of the other side through regex. I've isolated the faulty pattern and can't understand why it is producing "infinite" backtracking:

(\S+\s*)+(==|>=|<=|>|<)\s*

sample text:

x <= func[abcde,1]

I almost thought it was because of the brackets describing some weird, unwanted character set, but whatever characters I substitute with the brackets:

x <= func:abcde,1:

It still infinitely backtracks. The only way out is if "abcde" is shortened to only 4 characters "bcde", "abcd", "cbde"...

I don't get it. What else is to backtrack? <= matches and that pretty much fixes everything to that point...

• Dehbop: Crap... Just found out (\S+\s*)+(==|>=|<=|>|<)*\s* or (\S+\s*)+(==|>=|<=|>|<)?\s* works... Anybody care to explain why?? Btw, I'd rather have (\S+\s*)+(==|>=|<=|>|<)+\s*

Answer 1

With the caveat that behaviour may vary by regex engine (which are you using?), one thought:

(\S+\s*)+ (the first half) also matches strings matched by (==|>=|<=|>|<)\s* (the second half). Matching is greedy by default, so the first half will swallow the operator, then the second half will fail, then backtracking will begin. If you can use non-greedy matching or tighten up \S to exclude the operators, things should work more reliably.

As for the five vs. four characters, I don't know but am guessing it has to do with how your regex engine builds or optimizes its automata.

• Dehbop: I tried this in bot Mathematica (not thoroughly) and regex101.com... Similar results, so I thought this was by standard and there's just something I'm not getting. Anyways, in the end, I just went with .*(==|>=|<=|>|<)\s*. Didn't need the whole other shebang... Mathematica doesn't care about the structure, so why should I?