Introduction
The parser is the heart of a compiler's front end. It checks that the tokens follow the grammar and builds a tree that later phases use. The simplest kind of parser to write by hand is recursive descent: each grammar rule becomes a function, and the functions call each other the same way the rules mention each other. GCC, Clang, Go, the TypeScript compiler and CPython's newer parser are all recursive-descent parsers at heart. If you can write a grammar, you can write this kind of parser.
How it works
Start from a grammar for expressions with operators at several precedence levels:
expr → term (("+" | "-") term)*
term → unary (("*" | "/") unary)*
unary → "-" unary | power
power → atom ("^" unary)?
atom → NUMBER | NAME | "(" expr ")"
Each rule becomes one function. Lower precedence calls higher precedence, so expr calls term, which calls unary, and so on. That alone makes * bind tighter than +: by the time expr sees a +, both sides have already been parsed as complete terms.
Associativity comes from the shape of the code. A while loop that builds (op, left, right) and keeps going makes the operator left-associative: 8 − 3 − 2 becomes (8 − 3) − 2. Calling the function again on the right-hand side makes it right-associative: 2 ^ 3 ^ 2 becomes 2 ^ (3 ^ 2), as in mathematics.
Left recursion is the one thing recursive descent cannot handle directly. The natural rule E → E + T would make expr call expr immediately, forever. The fix is to rewrite it as E → T (+ T), which is exactly the loop above. In general, A → A α | β becomes A → β α.
The parser consumes tokens with two helpers: peek looks at the next token, and take consumes it, optionally checking that it is the expected one. When something unexpected appears, the parser raises an error that names what it found, so the user knows where the problem is.
Syntax
def expr():
node = term()
while peek() in ("+", "-"): # loop: left-associative
node = (take(), node, term())
return node
def power():
base = atom()
if peek() == "^": # recursion on the right: right-associative
take(); return ("^", base, unary())
return base
Example
import re
def parse(text):
tokens = re.findall(r"\d+|[A-Za-z_]\w*|\S", text)
pos = 0
def peek():
return tokens[pos] if pos < len(tokens) else None
def take(expected=None):
nonlocal pos
token = peek()
if expected and token != expected:
found = "the end" if token is None else repr(token)
raise SyntaxError(f"expected {expected!r} but found {found}")
pos += 1
return token
def expr():
node = term()
while peek() in ("+", "-"):
node = (take(), node, term())
return node
def term():
node = unary()
while peek() in ("*", "/"):
node = (take(), node, unary())
return node
def unary():
if peek() == "-":
take()
return ("neg", unary())
return power()
def power():
base = atom()
if peek() == "^":
take()
return ("^", base, unary())
return base
def atom():
token = peek()
if token == "(":
take()
node = expr()
take(")")
return node
if token is not None and (token.isdigit() or token.isidentifier()):
return take()
raise SyntaxError(f"unexpected {token!r}")
tree = expr()
if peek() is not None:
raise SyntaxError(f"unexpected {peek()!r} after the expression")
return tree
def lisp(node):
if isinstance(node, str):
return node
return "(" + " ".join([node[0]] + [lisp(child) for child in node[1:]]) + ")"
for text in ["1 + 2 * 3", "(1 + 2) * 3", "2 ^ 3 ^ 2", "-x ^ 2", "8 - 3 - 2", "1 + * 2", "(4 + 5"]:
try:
print(f"{text:12} -> {lisp(parse(text))}")
except SyntaxError as error:
print(f"{text:12} -> error: {error}")Line by line
- The lexer is one regular expression: numbers, names, or any single non-space character.
expr,term,unary,powerandatomfollow the grammar, one level each.- The tree is printed in prefix form, such as
(+ 1 (* 2 3)), where each bracket is one node with its operator first. 2 ^ 3 ^ 2groups to the right,8 - 3 - 2to the left, and-x ^ 2is the negation of x², as in mathematics.1 + * 2fails at the*, which cannot start an operand, and(4 + 5fails because the input ends where the closing bracket should be.
Expected result
1 + 2 * 3 -> (+ 1 (* 2 3))
(1 + 2) * 3 -> (* (+ 1 2) 3)
2 ^ 3 ^ 2 -> (^ 2 (^ 3 2))
-x ^ 2 -> (neg (^ x 2))
8 - 3 - 2 -> (- (- 8 3) 2)
1 + * 2 -> error: unexpected '*'
(4 + 5 -> error: expected ')' but found the end
In the real world
Hand-written recursive-descent parsers are popular because they are fast, easy to debug and give good error messages. Clang parses all of C, C++ and Objective-C this way. Many parsers use a variant called Pratt parsing or precedence climbing, which handles dozens of operators with one function and a precedence table.
Common mistakes
- Writing E → E + T directly, which recurses forever: rewrite it as a loop.
- Getting the precedence order backwards: the lowest-precedence operator belongs in the outermost function.
- Making every operator right-associative by recursing, so 8 − 3 − 2 becomes 8 − (3 − 2).
- Forgetting to check that all tokens were used, so
1 + 2 3is silently accepted.
Best practices
- Write the grammar first, then translate it rule by rule.
- Keep
peekandtakeas the only ways to touch the token list. - Print the tree in prefix form while testing; it shows the grouping at a glance.
Summary
A recursive-descent parser has one function per grammar rule. Calling lower-precedence functions from higher ones in order gives precedence; loops give left associativity and recursion on the right gives right associativity. Left recursion must be rewritten as a loop, and every unexpected token should produce a clear error.
Quick check
Key takeaways
- One function per precedence level, lowest first, gives precedence for free.
- A loop gives left associativity; a recursive call on the right gives right associativity.
- Rewrite E → E + T as E → T (+ T)* before writing the parser.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.