What's a recursive descent parser?

A parser is simply a programming system for recognizing certain patterns in text. For instance, when you run source code through a compiler, the way the compiler knows int x = 4 means "the variable x will hold an integer value, with the value of 4" is that it has a parser looking for statements that start with a type (in this case int), followed by a name (in this case x), possibly followed by an equals sign and a beginning value.

"Recursive descent" refers to a particular algorithm used in defining the patterns a parser is looking for. It's one of the simplest ways to implement a parser.

So what's recursive descent?

Recursive descent is a system where functions know how to match certain sub-rules, and call each other in order to match complete rules. That is, to parse int x = 4;, you might create a function like:

``` bool match_declaration(char* line_to_parse) { /* each function moves line_to_parse forward on success, so we need to be able to restore where it was on failure */

char* backtrack_on_failure = line_to_parse;

if (match_typename(line_to_parse))
{
    if (match_identifier_name(line_to_parse))
    {
        if (match_semicolon(line_to_parse)) return true;
        else if (match_equals_sign(line_to_parse))
            if (match_number(line_to_parse))
                if (match_semicolon(line_to_parse)) return true;
    };
};

line_to_parse = backtrack_on_failure;
return false;

} ```

This isn't complete. It doesn't handle C-style struct literals, for instance. But the concept is there. Each function tries to match what it knows how to match, and some functions do that by calling other functions.

• General Questions
• Stack Overflow Concerns
• Administrative Questions