Support for infinite loops detection and reporting

[igordejanovic]

In the case of left recursive grammar Arpeggio will end with RecursionError. It would be nice to have a detailed report why that happen and where in the grammar is the left recursive loop.

[igordejanovic]

This is in relation with the idea to fully support left recursive grammars #5

[igordejanovic]

Another example of infinite loop is using expression that could succeed without consuming any input in repetition. For example, using Optional inside ZeroOrMore.

[Ygg01]

Interesting problem. Any ideas how to solve this issue?

Best I've found were: https://github.com/orlandohill/peg-left-recursion

Alternatively, you could limit nesting within a AST via some kind of decrementing counter.

[igordejanovic]

Thanks for the link. There are several papers published on the subject. I had plans to support left recursive grammars (there is still issue registered) but I'm not so sure anymore that it is the right way to go.

PEGs have a nice property that they are representation of recursive descent parser and thus are easy to reason about and debug. Introducing support for left recursion would break that simplicity.

For the time being I think that detection of infinite loops on the grammar level is good enough. Idea is to run those checks during grammar design so there should be no run-time overhead. I have some vague idea of how that can be done but I still must find some more time to investigate.