how does spirit process rules?

Question

This grammar standalone rule code produces the expected result

term        = ( double_ >> "+" >> term ) [_val = _1 + _2]|
              ( double_ >> "-" >> term ) [_val = _1 - _2]|
              ( double_ >> "*" >> term ) [_val = _1 * _2]|
              ( double_ >> "/" >> term ) [_val = _1 / _2]|
              double_                    [_val = _1] ;

while this one does not:

term        = ( term >> "+" >> term ) [_val = _1 + _2]|
              ( term >> "-" >> term ) [_val = _1 - _2]|
              ( term >> "*" >> term ) [_val = _1 * _2]|
              ( term >> "/" >> term ) [_val = _1 / _2]|
              double_                    [_val = _1] ;

I guess this has something to do with recursion ambiguity... What does the second rule tries to do when fed with: "1+2+3" ?

Is there some good document that schematically explains how spirit parsing is performed ? I mean as a pure c or algorithm, with no template or classes.

EDIT: Actually I think that the second rule should fail at compiler time as it is ambiguous.

Answer 1

Spirit is a PEG parser:

• Parsing expression grammar (wikipedia)
• See also the About Page introduction on the http://boost-spirit.com site
• Parser Expression Grammar in the documentation abstracts

Relevant quote:

Syntactically, PEGs also look similar to context-free grammars (CFGs), but they have a different interpretation: the choice operator selects the first match in PEG, while it is ambiguous in CFG

So, no, the second example is not ambiguous at all, it just results in infinite recursion (--> stackoverflow).