I keep getting stack overflows when trying to use Spirit to parse stuff

Question

I figured when I started getting stack overflow it was time to come here to ask ;)

I'm trying to learn how to use Boost Spirit right now. I've figured out the basic stuff. Since I had K&R handy (which contains the grammar of C) I decided to see if I could make an acceptor for the language. This was more or less my original goal anyway, since I eventually want to use this as a preprocessor to gather some information from data structures and stuff.

I'm able to parse constants and strings, but when I try to parse this I start having problems.

postfix_expression = 
    primary_expression
    // omitting some other rules for simplicity's sake
    | (postfix_expression >> chseq+p("++"))
    | (postfix_expression >> chseq_p("--"));

primary_expression = 
    identifier
    | constant
    | string_literal;

// The parsers for constants and strings are 
// pretty trivial so I'm not going to C+P them here.

When I pass in something like i++ it fails. I assume this is because i is a valid primary_expression and so it doesn't go on to check for the ++ or --. I tried putting it at the bottom, and then I get stack overflows. I'm getting some infinite left recursion here but I don't know how to solve it.

Answer 1

You'll have to get rid of the left recursion. This Wikipedia article explains some techniques:

http://en.wikipedia.org/wiki/Left_recursion

However, it may not be possible. C has a pretty flexible syntax and may not provide enough context to allow a recursive descent parser to function unless Boost Spirit allows backtracking. Or you'll be able to do it but the associations will be backwards.

You may be better off using an LALR based tool such as bison.