I am writing a parser for an existing language, using the TextX Python Library (based on the Arpeggio PEG parser)
But when I try to use it to parse a file, I get the exception:
RecursionError: maximum recursion depth exceeded while calling a Python object
Here is a minimal example that raises this exception:
#!/usr/bin/env python
from textx import metamodel_from_str
meta_model_string = "Expr: ( Expr '+' Expr ) | INT ;"
model_string = "1 + 1"
mm = metamodel_from_str(meta_model_string, debug=True)
m = mm.model_from_str(model_string, debug=True)
I tracked it down to Arpeggio's left recursion issue, where it state that a rule like A := A B is unsupported and should be converted to a rule where there is no such recursion.
So my question is: Is it possible to rewrite the Expr := Expr '+' Expr rule above in a way that does not use left recursion? Note that the real Expr rule is much more complicated. A slightly less simplified version of it will be:
Expr: '(' Expr ')' | Expr '+' Expr | Expr '*' Expr' | '!' Expr | INT | STRING ;
textX author here. In addition to Paul's excellent answer, there is expression example which should provide you a good start.
Top-down parsers in general are not handling left-recursive rules without hacks like this. If your language is going to be complex and heavily expression oriented it might be better to try some bottom-up parser that allows for left recursion and provides declarative priority and associativity specification. If you liked textX then I suggest to take a look at parglare which has similar design goals but uses bottom-up parsing technique (specifically LR and GLR). Quick intro example is the exact language you are building.
In this post I blogged about rationale of starting parglare project and differences with textX/Arpeggio.