Compilers Project 2: Recursive Descent Parser

According to Wikipedia

"In computer science, a recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where each such procedure usually implements one of the production rules of the grammar."

What does this even mean? Basically, given a grammar, there is a function for each term in the grammar that handles that term. These functions can call each other or themselves, and they end up constructing a tree that represents the input (e.g. a program).

For example, the grammar:

(funcdef (seq "def" NAME parameters ":" suite))
(parameters (seq "(" (opt paramlist) ")"))
(paramlist (seq (seq NAME (rep (seq "," NAME))) (opt ",")))

leads to the following program structure:

class Parser(object):
    def __init__(self, string):
        ….
    def funcdef(self):
        ….
    def parameters(self):
        ….
    def paramlist(self):
        ….
    def suite(self):
        ….

And given the string:

def double(x):
    return x*x

We get a tree that looks like this (excluding the definition for suite):
                        def double(x):
                            return x*x
                          /                  \
                def double(x)    return x*x
                /                                         \
             (x)                                            ….
            /
          x

(most of the information in this post is from this source: http://matt.might.net/articles/parsing-regex-with-recursive-descent/)