boost::fusion parsing long string causes stack overflow

Question

Is there any way how to prevent boost::fusion to overflow stack on certain input? I have grammar similar to

S -> S OR S
S -> a

and on huge input (>1500 OR'd items) it crashes. I don't want to parse such a huge input, but I need somehow to prevent process crashing.

I can probably limit the string to be of some length, but that doesn't solve my problem, as a may be long.

First, it's not fusion crashing, that's Spirit (or more specifically, your rules). Show your code (SSCCE) and I'll try to fix it. — sehe, Nov 27 '14 at 14:55
It looks like you're parsing boolean expressions. Have you looked at [Boolean Expression grammar with Boost Spirit](http://stackoverflow.com/questions/8706356/boolean-expression-grammar-parser-in-c/8707598#8707598) for ideas? There's a [followup that does evaluation](http://stackoverflow.com/questions/12598029/how-to-calculate-boolean-expression-in-spirit/12602418#12602418) too — sehe, Nov 27 '14 at 15:06

score 1 · Answer 1 · edited May 23 '17 at 10:24

This is usually tackled by rewriting right-recursion into a form of iteration, e.g.

myrule = something >> -(',' >> myrule); // right recursion

into

myrule = something *(',' >> myrule); // iteration

Of course, this is a trivial case. In real grammars, you'd often need to somehow keep the operator precedence in check.

In the absense of code see here for examples of refactoring grammars to be much lighter on the stack and allocations:

1 Answers1