Parsers: Recursive Descent Versus Generators

Sooner or later something needs parsing — a configuration format, a query language, a data file, an expression evaluator. The options are a hand-written recursive descent parser, a parser generator, or a parser combinator library.

For a separate people-operations perspective, the practical guide covers the limits of self-reported data.

The choice is usually made by whichever one the author has used before. It is worth making on the merits.

First: do not parse with string manipulation

The approach that always seems sufficient at the start.

split(',') works until a value contains a comma. Quoting is added. Escaped quotes are added. Nesting appears. A year later the function is 300 lines of special cases and nobody can change it safely.

The tell is a growing set of special cases. If you have added the third exception to a splitting routine, you are writing a parser badly. Stop and write one properly — it is usually less code than the special cases already are.

And the corollary: if a standard format exists, use its library. Hand-rolled parsers for CSV, JSON, YAML, dates and URLs are a reliable source of security advisories, and the edge cases in each are worse than they appear.

The structure of a parser

Lexing turns characters into tokens: identifiers, numbers, operators, punctuation. Whitespace and comments are usually discarded here.

Parsing turns tokens into a tree reflecting structure and precedence.

Separating them is worth it. A parser that works on tokens is much simpler than one working on characters, and the lexer is easy to test independently.

Recursive descent

One function per grammar rule, calling each other as the grammar nests.

def parse_expression(self):
    left = self.parse_term()
    while self.peek() in ('+', '-'):
        op = self.next()
        right = self.parse_term()
        left = BinaryOp(op, left, right)
    return left

def parse_term(self):
    left = self.parse_factor()
    while self.peek() in ('*', '/'):
        ...

The structure mirrors the grammar directly, and precedence falls out of the nesting — parse_expression calls parse_term, so multiplication binds tighter than addition without any precedence table.

Advantages:

Error messages. By far the strongest reason. You can say "expected a closing parenthesis to match the one on line 4" because you know exactly what you were doing. Generated parsers say "syntax error at token 47" unless considerable work goes into fixing that, and error message quality is most of what users experience from a parser.

Debuggable. It is ordinary code with an ordinary call stack.

No build step, no dependency, no generated code in the repository.

Error recovery is possible. Continuing after an error to report several problems at once — which every good compiler does — is achievable by hand and awkward in generated parsers.

Disadvantages:

No formal guarantee that it matches a grammar, because there is no grammar written down anywhere except in the code.

Left recursion does not work directly. A rule referring to itself as its first element recurses forever, and the grammar must be rewritten iteratively — which is what the while loop above is.

More code, and the grammar is implicit.

Parser generators

You write a grammar; a tool generates the parser.

Advantages:

The grammar is the specification, readable and reviewable in one place.

Ambiguity is detected. The tool reports conflicts, which is genuine correctness information that hand-written parsers never surface — an ambiguous grammar simply resolves silently in favour of whichever branch is checked first.

Handles constructs recursive descent finds awkward, including left recursion.

Disadvantages:

Error messages are poor by default and improving them is real work.

Conflicts are hard to debug. Understanding a shift-reduce conflict requires understanding the generated automaton, which is a different skill from the one you were using.

A build step and generated code, which complicates the toolchain.

Parser combinators

Small parsers composed into larger ones using ordinary functions.

number = regex(r'\d+').map(int)
expr   = number.sep_by(char('+'))

Advantages: the grammar is code, so it is composable and testable; no build step; and it reads well for simple grammars.

Disadvantages: performance is typically worse; error messages need explicit attention; and deeply composed parsers produce stack traces that are difficult to read. Backtracking behaviour also needs care, or you get the same exponential problem as catastrophic backtracking in regular expressions.

Choosing

Simple, well-understood grammar; error messages matter — recursive descent. This covers most application needs, and it is why most production compilers use hand-written parsers despite generators existing.

Complex grammar, formal specification matters, ambiguity detection valuable — a generator.

Small grammar, in a functional language, prototyping — combinators.

A standard format — a library, always.

Things people get wrong

No position information. Every token and node should carry its line and column. Adding this later means touching everything, and without it every error message is useless.

Only reporting the first error. Users want to know about all the problems. Recovery — skipping to a synchronisation point such as a statement terminator and continuing — is more valuable than it looks.

Unbounded recursion on deeply nested input. A file with ten thousand nested brackets overflows the stack, and if the input is untrusted that is a denial of service. Set a depth limit.

Losing comments and formatting, which is fine for a compiler and fatal for a formatter or a tool that rewrites the file. Decide early which you are building, because retrofitting is expensive.

Not separating the tree from the semantics. Parse into a tree, then analyse. Doing both at once produces something that cannot be reused and is hard to test.

No fuzzing. A parser handling untrusted input should be fuzzed. It is one of the few places where fuzzing reliably finds crashes quickly, and modern fuzzing tools make it an afternoon's setup.

The summary

Do not parse with string splitting. The third special case is the signal to stop.

Use a library for standard formats, always.

Recursive descent for most things, because error message quality dominates the user experience and it is ordinary debuggable code.

A generator when the grammar is complex enough that ambiguity detection is worth the toolchain cost.

Carry position information from the first line you write, set a depth limit, and fuzz anything that reads untrusted input.