RecursionError with moderately nested expressions

[ilkka-torma]

It seems that idiomatically written expression parsers cannot handle more than a few dozen nesting levels before triggering a RecursionError with Python's default recursion limit. For example, the calculator example from the documentation can't handle the expression

1+(1+(1+( ... 1+(1) ... )))

with 46 pairs of nested parentheses. The number of nested function calls produced by parsy seems to increase more or less linearly with the nesting depth of the expression, so one workaround is to temporarily increase the recursion limit.

I ran into this issue when using a more complex parser on some computer-generated code. It seemed to have a nesting depth of about 10, but the number of calls per nesting level is likely higher than with the calculator example, since I have many more expression types.

[spookylukey]

Thanks for the bug report.

I can reproduce this on Python 3.13, with the default maximum recursion limit of 3000, with ~220 nested expressions.

Using https://parsy.readthedocs.io/en/latest/howto/lexing.html#calculator

simple_eval('(1+' * 250 + '(1)' + ')'*250)

Unfortunately, I don't think there is much that we can do to fix this. With some work it might be possible to make parsy use slightly fewer stack frames, but ultimately the design will mean that you will very quickly hit the same limit.

It might just be possible to do something very clever with how parsy runs to fix this, but I suspect that 1) I'm not that clever 2) it would complicate the design of parsy enough that it wouldn't be worth it.

I think the only option for you use case is to increase the recursion limit in Python, or use a parsing library that can handle parsing recursive structures by using the heap instead of the stack.

So I'm going to close this as 'not planned' - it's a genuine issue, but we don't plan to do anything about it. Sorry!