0

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.

einpoklum
  • 118,144
  • 57
  • 340
  • 684

1 Answers1

0

Spirit doesn't rewrite your grammar at all, it runs exactly what you've wrote.

Nikita Kniazev
  • 3,728
  • 2
  • 16
  • 30
  • So are you saying this kind of syntax would result in a compilation error? Runtime error? – einpoklum Jul 01 '18 at 21:44
  • 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 01 '18 at 21:52