Regular expression causing segfault/stack overflow

Question

(or so I think)...

I'm using boost::xpressive as my regular expression engine to parse something and I get a segfault. I suspect that recursivity and my bad regular expression are to blame, because gdb shows more than 300 stack frames. So, here is my (case-sensitive) regular expression, in perl/python notation:

begin([^e]+)e((?:[^b]|b(?!egin))+)

which I expect to match

beginHEADER HEREeFOLLOWED BY SOME LONG LONG TEXT THAT GOES UNTIL NEXTbegin

with the first uppercase text (HEADER HERE) in the first group, and the second uppercase text in the second group. I always get the segfault if the text that should match group 2 is very long.

Why shouldn't this work?

Amber · Accepted Answer · 2012-03-05T09:21:13.040

5

You can simplify your regular expression a lot by simply using non-greedy matching:

begin(.+?)e(.+?)begin

Try that and see if it works better.

It's likely that your original regex was causing a stack overflow due to a recursive implementation of the |-or grouping in your regex, which was potentially branching with every single character in your second group.

A simple non-greedy .+? on the other hand doesn't need to branch for every single character.

edited Mar 05 '12 at 09:21

answered Mar 05 '12 at 09:15

Amber

507,862
82
626
550

I would keep `[^e]+` in the left hand part, it will probably perform better. – Benoit Mar 05 '12 at 09:35
Thanks, it works now. This backtracking thing is mind-numbing. – dsign Mar 05 '12 at 09:35
Also, xpressive works a lot better when compiled in release-mode (maybe tail-recursion helps?). – dsign Mar 05 '12 at 09:47
Not tail recursion. Compiling in release mode causes many function calls to be inlined, resulting in more efficient use of the stack. – Eric Niebler Mar 06 '12 at 00:18

Regular expression causing segfault/stack overflow

1 Answers1