Infinite recursion when parsing expression grammar about parsy HOT 5 CLOSED

If you are trying to google for other solutions, this is a well-known problem with this type of parsing approach, called left recursive grammar.

from parsy.

You're getting infinite recursion because you've said that (modulo compare and optional lparen) an expression starts with an expression. Of course, that causes parsy to recurse.

There are ways to write code like this differently so that it's not recursive, check out simple_eval in the examples folder.

We're also thinking (see #5) about enhancing parsy to better handle cases like this. In a future version, it should be a) very easy to make code like yours work (automagic recursion elimination) and b) even easier to achieve what you're trying to achieve in more comprehensive way and less lines of code (chaining combinators).

from parsy.

I see. So, would I be better off waiting on the left-recursion elimination, trying to rewrite to eliminate it, or go with an LR solution?

I'm having a bit of trouble following the parsing logic in simple_eval.py. I see that the expr top-level parser is the additive parser, which first tries to yield a multiplicative, and then multiplicative tries to yield a simple, which in turn tries to yield an expr or a number. This seems oddly tangled to me; where does the parsing "bottom out", at the number case?

And then both additive and multiplicative contain infinite loops which then break out when they can find no more operations. I'm guessing doing it this way is to handle operator precedence, which makes sense. But the tangled interdependence is hard to follow sans comments.

My apologies, this isn't a general help forum. But thank you for offering advice.

from parsy.

I see. So, would I be better off waiting on the left-recursion elimination, trying to rewrite to eliminate it, or go with an LR solution?

Try to eliminate it, it's not at all that hard.

I'm having a bit of trouble following the parsing logic in simple_eval.py. I see that the expr top-level parser is the additive parser, which first tries to yield a multiplicative, and then multiplicative tries to yield a simple, which in turn tries to yield an expr or a number. This seems oddly tangled to me; where does the parsing "bottom out", at the number case?

It's very important that simple starts with either number (which ends the recursion) or a non-optional lparen (and then a recursive expr again). But in any case, we parse at least one more input character.

I'm guessing doing it this way is to handle operator precedence, which makes sense.

Yes, this is to handle operator precedence and associativity (1 - 2 - 3 ≠ 1 - (2 - 3)). If you don't care about those, it gets much simpler, ex. your boolean expressions could be parsed like this:

op = simple '&&' expr | simple '||' expr | '!' expr
simple = 'true' | 'false' | '(' op ')'
expr = simple | op

(This is not parsy code, but should hopefully make sense). Again, this demonstrates the same idea: no left recursion, delegate to simple which always parses at least one character from the input.

But the tangled interdependence is hard to follow sans comments. My apologies, this isn't a general help forum. But thank you for offering advice.

You see, there's a lot of theory behind this (called the formal language theory) — it describes regular expressions, context-free grammars, LL and LR parsers, and so on. That way of manual left recursion elimination and that way to parse expressions are very standard and familiar for people who know the theoretical side of things. simple_eval example is not meant to be an introduction into formal language theory for those who don't, it's more of an example how to use parsy specifically, i.e. how those theoretical concepts (if you know them) map to parsy's operators and combinators.

If you're interested in writing complex parsers or even compilers, I recommend you to read up on these things, e.g. this book will teach you all of that and more.

from parsy.

It's been ages since I read the Dragon Book. I might need a refresher.

Thanks for your help.

from parsy.