Lexers & Parsers: Recursive Descent and Pratt Parsing

Q: How do I handle whitespace-significant languages?

The lexer emits explicit INDENT and DEDENT tokens by tracking an indentation stack, and the parser then treats them like braces. Python's tokenizer works exactly this way. The subtleties are tabs versus spaces, blank lines, continuation inside brackets, and inconsistent indentation — all of which live in the lexer, which is where you want them.

Lexers & Parsers

Parsing is the first half of every compiler and the part that shows up most often in ordinary work. Any time you're extracting structure from text — a config format, a query language, a template syntax, a log line with nested fields — you're parsing, and the question is only whether you're doing it deliberately or with a regex that will fail on the first nested case.

The job splits cleanly in two. A lexer (or scanner) converts a character stream into a stream of tokens: if, (, identifier x, >, number 0. It handles whitespace, comments, string escapes, and numeric literals, and it produces a much easier input for the next stage. A parser consumes those tokens and builds a tree according to a grammar, which is where operator precedence, nesting, and statement structure get resolved.

The practical recommendation, which surprises people who expect a theory-heavy answer: write it by hand. Recursive descent for statements, Pratt parsing for expressions. It's more code than a parser generator and it gives you better error messages, easier debugging, and the flexibility real languages need — which is why Clang, GCC, TypeScript, and Rust all hand-write theirs.

TL;DR

Lexer: characters → tokens. Parser: tokens → tree. Separating them makes both much simpler.
A grammar defines valid structure; ambiguity in a grammar means the parser has to be told what to prefer.
Recursive descent — one function per grammar rule — is the parser to write by hand.
Pratt parsing (precedence climbing) handles operator precedence elegantly. Use it for expressions.
Emit tokens with source positions; every error message downstream depends on them.
Error recovery matters more than error detection — an IDE needs a tree even from broken code.
Reach for a generator (ANTLR, tree-sitter, yacc) for complex grammars or incremental reparsing.
Don't parse structured formats with regular expressions. Nesting defeats them, by definition.

Quick Example

A complete lexer and Pratt parser for an expression language, in Python:

That INFIX table is the whole of operator precedence. Adding a new operator is one line, and associativity is expressed by which binding power is larger — which is why Pratt parsing beats the traditional cascade of parseTerm calling parseFactor calling parseUnary.

Core Concepts

Why separate lexing from parsing

The lexer is usually a single loop over characters with a switch. The parser is a set of mutually recursive functions. Neither is complicated; combining them makes both messy.

Grammars

That cascade works and gets tedious fast: a language with fifteen precedence levels needs fifteen functions that differ only in an operator set. Pratt parsing collapses the whole cascade into one function plus a table, which is why it's the standard choice for expression grammars.

Ambiguity is a grammar producing more than one tree for the same input. The dangling-else problem is the classic:

Parsing strategies

Left recursion is recursive descent's one real limitation:

Every left-recursive rule can be rewritten this way, and Pratt parsing sidesteps the issue entirely.

Error recovery

Detecting the first error is easy. Producing useful output after it is what separates a compiler from a toy — and it's non-negotiable for anything an editor uses, since editors spend most of their time parsing syntactically invalid code.

Two techniques go a long way: panic-mode synchronization (skip to the next statement boundary) and error nodes in the tree, so downstream passes can operate on a partially valid program. Reporting fifteen real errors in one run is far better than reporting one and stopping.

Source positions

Every token carries a line, a column, and ideally a byte offset. Every AST node carries a span derived from its tokens. Without this, every diagnostic downstream — type errors, lint warnings, IDE squiggles, stack traces — has nowhere to point. Adding positions after the fact means touching every node type, so do it from the first commit.

Parser Generators

Generators earn their place when the grammar is large and changing, when you need incremental reparsing for an editor (tree-sitter), or when a formal grammar is itself the deliverable. They cost you control over error messages, which is precisely what users of a compiler notice most.

Note the pattern: tooling tends to use generators (tree-sitter powers syntax highlighting in many editors), while compilers tend to hand-write. The requirements genuinely differ.

Best Practices

Write the grammar down first

Even informally, in BNF-ish notation as a comment. It clarifies precedence and associativity before you write code, it documents the language, and it's what you'll check against when a parsing bug appears.

Carry source positions everywhere

Line, column, and byte offset on every token; a span on every AST node. Every downstream diagnostic depends on them, and retrofitting is painful.

Use Pratt parsing for expressions

One function plus a precedence table beats a fifteen-level function cascade. Adding an operator becomes a table entry rather than a new function and three call-site edits.

Recover from errors and report many

Panic-mode synchronization at statement boundaries plus error nodes in the tree. A parser that reports one error and exits is unusable in an editor and frustrating on the command line.

Make error messages specific

Tracking the opening token so you can point at both ends of an unbalanced pair is a small amount of bookkeeping and enormously more helpful.

Don't over-engineer the lexer

A single loop with a switch statement handles almost every language. Regular expressions per token type are slower and harder to give good positions. Generated lexers rarely pay off for a hand-written parser.

Test with a corpus, including invalid input

Golden-file tests that parse a source file and compare the printed AST catch regressions precisely. Include deliberately broken files and assert on the error messages — those are the part users interact with most and the part most likely to silently degrade.

Consider a concrete syntax tree for tooling

A formatter or refactoring tool needs whitespace and comments preserved; a compiler doesn't. If you need both, keep a lossless CST and derive the AST from it, which is the approach Roslyn, rust-analyzer, and tree-sitter take.

Common Mistakes

Parsing nested structures with regex

This is a theoretical limitation, not an implementation gap: nesting is beyond what regular languages can express.

Left recursion in recursive descent

Losing source positions

Stopping at the first error

Mixing lexing into parsing

Hardcoding precedence in the call graph

FAQ

Should I hand-write a parser or generate one?

Hand-write for a compiler or interpreter — better errors, easier debugging, and the flexibility to handle the context-sensitivity real languages accumulate. Generate for editor tooling that needs incremental reparsing (tree-sitter), for a large grammar that changes often, or when the formal grammar is itself a deliverable. The industry pattern is telling: production compilers hand-write, editor tooling generates.

What's the difference between a parser and a compiler?

Parsing is one stage of a compiler — the front-end step that produces a tree. A compiler continues with name resolution and type checking, lowering to an IR, optimization, and code generation. Plenty of useful programs are parsers and nothing more: linters, formatters, syntax highlighters, and config loaders.

How do I handle whitespace-significant languages?

The lexer emits explicit INDENT and DEDENT tokens by tracking an indentation stack, and the parser then treats them like braces. Python's tokenizer works exactly this way. The subtleties are tabs versus spaces, blank lines, continuation inside brackets, and inconsistent indentation — all of which live in the lexer, which is where you want them.

What is a parser combinator?

A style where small parsers are composed with higher-order functions — many(digit), sepBy(expr, comma), choice(a, b). It reads close to the grammar and is very pleasant in functional languages (parsec, nom, chumsky). The tradeoffs are performance and error messages, both of which need explicit attention; libraries increasingly provide good tools for the latter.

How do incremental parsers work?

They keep the previous tree and reuse the subtrees unaffected by an edit, reparsing only the damaged region. This is what makes syntax highlighting and IDE features feel instant in a large file — reparsing a 10,000-line file on every keystroke is not viable. tree-sitter is the widely used implementation, and its error tolerance is equally important since editors are usually looking at invalid code.

Do I need to know formal language theory?

A little helps and it's not a prerequisite. Worth knowing: what makes a grammar ambiguous, why regular expressions can't match nested structures, and what left recursion is and how to remove it. The rest of the Chomsky hierarchy is interesting and rarely load-bearing in practice — you can write an excellent hand-rolled parser without being able to prove your grammar is LL(1).