What Is Recursive Descent Parser: Explanation and Example

A recursive descent parser is a simple type of parser used in compilers that processes input by calling functions for each grammar rule recursively. It breaks down the input step-by-step, matching parts of the language using these function calls to build a structure representing the input.

How It Works

A recursive descent parser works like a set of small helpers, each responsible for understanding a specific part of a language. Imagine you are reading a recipe and you have a helper for each step: one helper reads the ingredients, another reads the instructions, and so on. Each helper calls another helper when it needs to understand a smaller part.

In the parser, each helper is a function that tries to match a piece of the input text according to a grammar rule. If the function finds what it expects, it moves forward; if not, it backtracks and tries another path. This process continues recursively, meaning the functions call themselves or each other to handle nested structures.

Example

This example shows a simple recursive descent parser in Python that parses and evaluates basic arithmetic expressions with addition and multiplication.

python

def parse_expression(tokens):
    def parse_term():
        nonlocal pos
        value = parse_factor()
        while pos < len(tokens) and tokens[pos] == '*':
            pos += 1
            value *= parse_factor()
        return value

    def parse_factor():
        nonlocal pos
        if tokens[pos].isdigit():
            val = int(tokens[pos])
            pos += 1
            return val
        raise ValueError('Expected number')

    pos = 0
    value = parse_term()
    while pos < len(tokens) and tokens[pos] == '+':
        pos += 1
        value += parse_term()
    if pos != len(tokens):
        raise ValueError('Unexpected token')
    return value

# Example usage
expr = '2 + 3 * 4'
tokens = expr.replace(' ', '').replace('+', ' + ').replace('*', ' * ').split()
result = parse_expression(tokens)
print(result)

Output

14

When to Use

Recursive descent parsers are great for simple to moderately complex languages where the grammar is easy to express with clear rules. They are easy to write and understand, making them popular for teaching and small projects.

They work well when the grammar is free of left recursion and ambiguity. Real-world uses include parsing simple configuration files, small programming languages, or domain-specific languages where quick development and clarity are more important than handling very complex syntax.

Key Points

• Recursive descent parsing uses one function per grammar rule.
• Functions call each other recursively to process nested structures.
• It is easy to implement and understand but not suitable for all grammars.
• Backtracking may be needed if the grammar is ambiguous.
• Commonly used in simple compilers and interpreters.

Key Takeaways

Recursive descent parsers break input into parts using recursive function calls for each grammar rule.

They are simple to implement and good for clear, non-left-recursive grammars.

Best suited for small languages, teaching, and quick parsing tasks.

Backtracking helps handle choices but can slow down parsing.

Each function tries to match a piece of input and calls others for nested parts.