Overcoming Infinite Left Recursion In Textx Parser

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: Rec

Solution 1:

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.

Solution 2:

This is more typically written as:

multop: '*' | '/'
addop: '+' | '-'
Factor: INT | STRING | '(' Expr ')' ;
Term: Factor [multop Factor]... ;
Expr: Term [addop Term]... ;

Now Expr will not directly recurse to itself until first matching a leading '('. You will also get groups that correspond to precedence of operations. (Note that the repetition for Expr and Term will end up producing groups like ['1', '+', '1', '+', '1'], when you might have expected [['1', '+', '1'], '+', '1'] which is what a left-recursive parser will give you.)