Recursive Descent Parsing Confusion

[JG1993]

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 <IF statement> 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 </IF statement> 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!

[cadet1620]

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
 

[JG1993]

Thanks for such a quick answer and for clarifying what recursion means!