I am trying to create my own recursive descent parser in python, but when my parser runs into a rule concerning arithmetic expressions, it surpasses the python recursion limit. Here is the grammar:
Term --> Factor {( "+" | "-" ) Factor}
Factor --> Grouping {( "*" | "/" | "%" ) Grouping}
Grouping --> Expression | "(" Expression ")" | "-" Factor
Expression --> Integer | Float | Tuple | ID | Term
The curly braces in the grammar denote that they can repeat (but also is optional), and are implemented using a while loop in my parser. I feel that what is causing this is the fact that a Grouping rule can be and Expression (whcih can recur over and over because the right side of the Factor and Term rule are optional).
What I am asking is: Is there a way to implement the left recusion with a recursive descent parser or eliminate it in my grammar somehow?
EDIT: I was browsing around and iit seem this type of recursion is called indirect left recursion, perhaps this has something to do with it?
As you observe, the infinite recursion is the result of the infinite loop
Expression ⇒ Term ⇒ Factor ⇒ Grouping ⇒ Expression
which must be broken. But it's a simple transcription error; Expression needs to start from the top, in a hierarchy of syntactic precedence:
Expression ⇒ Term {( "+" | "-" ) Term}
Term ⇒ Factor {( "*" | "/" | "%" ) Factor}
Factor ⇒ Item | "-" Factor
Item ⇒ Integer | Float | Tuple | ID | "(" Expression ")"