Does Boost Spirit X3 support left recursion?
Multi tool use
Does Boost Spirit X3 support left recursion?
One of the shortcomings/implementation challenges of recursive-descent parsers is dealing with left recursion, e.g.
<expr> := <expr> '+' <num>
| <num>
The parser needs to parse an expr before it can parse an expr...
Now, Boost::Spirit::X3 generates recursive descent parsers. Does that mean it doesn't support left-recursion, or does it have workarounds for it?
Note: Left recursion can (often? always?) be eliminated from the grammar beforehand (like in the solution to this question), but that's not what I'm asking.
1 Answer
1
Spirit doesn't rewrite your grammar at all, it runs exactly what you've wrote.
Qi only tries to check for direct left recursion at compile time, while X3 does not do even this. The infinity recursion should (and will) lead to a crash with stack overflow at runtime.
– Nikita Kniazev
Jul 1 at 21:52
Please put that in the answer so I can accept...
– einpoklum
Jul 2 at 6:45
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
So are you saying this kind of syntax would result in a compilation error? Runtime error?
– einpoklum
Jul 1 at 21:44