CODEWITHSUNDEEP
parsingrecursive-descentinfinite-recursion
Monolith
Monolith

Reputation: 1147

Infinite recursion for parsing arithmetic expressions using a recursive descent parser

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?

Upvotes: 2

Views: 513

Answers (1)

rici
rici

Reputation: 241911

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 ")"

Upvotes: 1

Related Questions