Recursive descent parsing: tokenizers, grammars and precedence
How to parse formulas, JSON and patterns by hand: split input into tokens, write the grammar down, turn each rule into a function, handle precedence, and report exact error positions.
A parser turns text into structure: "2 + 3 * x" into "add 2 to (3 times x)". Recursive
descent is the hand-written way to do it: one function per grammar rule, each calling the others.
It works the same in every language.
Tokenize first
Don't parse characters directly. First split the input into tokens, each remembering where it started:
input: 12.5 * (A1 + 3)
tokens: NUMBER(12.5)@0 STAR@5 LPAREN@7 CELL(A1)@8 PLUS@11 NUMBER(3)@13 RPAREN@14 END@15The tokenizer handles whitespace, number formats and names; the parser only sees clean tokens.
Always end with an END token, so "unexpected end of input" is an ordinary error.
Write the grammar down
Before writing code, write the rules, lowest precedence first:
expression := term (("+" | "-") term)*
term := unary (("*" | "/") unary)*
unary := "-" unary | power
power := primary ("^" unary)?
primary := NUMBER | CELL | NAME "(" arguments ")" | "(" expression ")"* means "repeat", ? means "optional", | means "or". Each rule refers only to rules below it,
except where nesting is allowed (the parentheses send you back to the top).
One function per rule
Each rule becomes a function that consumes tokens and returns a value or a tree:
function term():
left = unary()
while next token is "*" or "/":
op = take token
right = unary()
left = combine(op, left, right)
return leftprimary looks at the next token to decide which alternative applies: a number, a cell, a
function call (a name followed by () or a parenthesised expression. JSON is the same shape:
value dispatches on the first character to object, array, string, number or a literal.
Precedence and associativity
The order of the rules is the precedence: * binds tighter than + because term is called
from inside expression. Associativity is loop versus recursion:
- Left-associative (
8 - 3 - 2=(8 - 3) - 2): awhileloop, as intermabove. - Right-associative (
2 ^ 3 ^ 2=2 ^ (3 ^ 2)): parse the right side with a rule that leads back to the same one, aspowerdoes throughunary.
Where unary minus sits matters too. In the grammar above, unary is above power, so
-2 ^ 2 is -(2 ^ 2) = −4, as in maths, while 2 ^ -1 still works because the exponent is a
unary. Swap the two rules and -2 ^ 2 becomes 4. Decide on purpose, and evaluate -2^2,
2^3^2 and 7-2-1 by hand with your grammar before coding.
Error positions
Every error should say what was expected and where, using the position stored in the token:
"2 + * 3" -> error at 4: expected a number, cell or "(" but found "*"
"(1 + 2" -> error at 6: expected ")" but reached the end
"1 2" -> error at 2: unexpected "2" after a complete expressionThe last one is easy to forget: after parsing an expression, check that the next token is END.
Depth limits
Recursive descent uses the call stack: each ( or [ is a nested call. Input such as 100,000
opening brackets will overflow the stack and crash the program. Count the depth as you descend,
and fail with a clean error past a limit (JSON parsers commonly use a few hundred to a thousand).
Patterns are languages too
A regular expression is parsed the same way, with alternation | as the lowest precedence, then
concatenation, then the postfix operators *, +, ?:
alternation := concatenation ("|" concatenation)*
concatenation := repeat*
repeat := atom ("*" | "+" | "?")*
atom := CHAR | "." | CLASS | "(" alternation ")"The parser's output is then compiled into a state machine. Build both in a safe regex engine for Sieve Mail.
Questions and answers
- Do I need a parser generator for an expression parser?
- No. A hand-written recursive descent parser is a few dozen lines for arithmetic, is easy to debug, and gives better error messages. Most production compilers parse this way.
- How do I make 2^3^2 equal 2^9 (right associative)?
- In the function for ^, parse the right-hand side by calling the same rule again (recursion) instead of looping. Left-associative operators like - use a loop; right-associative ones use recursion.
Practise it in a project
These projects put this guide to work, with tickets, tests and code review.
Sheetwise
A formula engine for Sheetwise
Write the formula engine behind Sheetwise's cells: a tokenizer and a recursive-descent parser with correct precedence, precise error positions, cell references and functions.
- tokenizers
- recursive descent
- operator precedence
- error reporting
Configo
A JSON parser for Configo
Write the strict, dependency-free JSON parser at the heart of Configo: exact error positions, Unicode escapes, depth limits, compact output and path lookups.
- recursive descent
- recursive data types
- Unicode and UTF-8
- defensive parsing
Sieve Mail
A safe regex engine for Sieve Mail
Write the regular-expression engine behind Sieve Mail's filter rules: a parser, Thompson's NFA construction and a simulation that runs in linear time, so no rule can hang the mail servers.
- parsing
- automata
- Thompson's construction
- worst-case complexity
Tracehound
Log analysis for Tracehound
Parse structured log lines, quoted values and all, then compute error rates and p95 latencies so on-call engineers find the slow endpoint in seconds.
- tokenising
- key-value parsing
- percentiles
- aggregation
Read next
- State machines in practice: transition tables, guards and event logs
Model order statuses, CSV quoting and regex matching as state machines: one transition table, guards for business rules, event logs you can replay, and NFAs that track several states.