# Recursive Descent Parsing Confusion

3 messages
Open this post in threaded view
|

## Recursive Descent Parsing Confusion

 Hi, So I finally started building the compiler and I must say it is probably the hardest chapter in the book so far. I am a little bit confused about the Recursive Descent Parsing. Specifically,  I am confused by this sentence in 10.1.3 -> "Otherwise, for every non-terminal building block in the rule's right-hand side, the routine can recursively call the routine designed to parse this non-terminal." , where I am not sure if I understand "recursively call" correctly. What I know is that recursive programming is when a method calls itself until it hits the base case. So, I am confused about how one method can call another method recursively. Does it mean that the compile methods need to have return statements? I created this example for myself to help me understand: I stripped the grammar of all the bits and only left if statements, which cannot have any arguments and the only statement they can have is another if statement. So only the allowed code is this(can be infinitely deep): if () {      if ()      {      }   }Then I wrote in python two methods, ifCompile and statementCompile. Assume that both methods have a list of tokens. They work roughly like this: def ifCompile:1]write  to the file 2Process and write if,(,),{ to the file 3] Call statementCompile to find out whether there is another statement or not 4] Process and write } to the file 5]write  to the file 6] return def statementCompile:1] Is next token if? If yes, then call ifCompile 2] If it is not, then return Would this be correct reasoning? It produces correct results for however deep if statements, however I am not sure if I am doing it recursively. Thanks!
 Administrator Yes, your code structure is correct. Recursion, in general, means that some function eventually get called by some combination of functions that it called. The classic factorial implementation ```def factorial(n): if n <= 1: return 1 else: return n*factorial(n-1) ```where factorial() calls itself, is an example of direct recursion. Your test case, where ifCompile() calls statementCompile() calls ifCompile() is an example of indirect recursion. --Mark