Article revision Version 1 of 1 Current

Build a Tiny Expression Parser with Precedence Climbing

Originally published by @nibblebits Oct 25, 2026 at 13:41
View current article
Initial version

Original article publication

This is the article as it appeared before any published revisions.

Snapshot

Article at version 1

Compilers & Toolchains

A compiler front end has to answer a deceptively small question: what structure does an expression describe?

Consider 7 + 2 * 5. If you combine everything from left to right, you get (7 + 2) * 5. The intended grouping is 7 + (2 * 5). Before generating assembly or intermediate representation, your compiler must settle that grouping.

This tutorial builds a small expression parser using precedence climbing. The result is an abstract syntax tree (AST), not an evaluated answer. We will use Python to keep the implementation easy to run and inspect; the same parser structure can be implemented in C or C++.

Define the language before writing the parser

Our toy language supports decimal integers, parentheses, unary + and -, and four binary operators. It deliberately omits variables, calls, division, and assignment.

Binary operator Precedence Associativity
+, - 10 Left
* 20 Left
** 40 Right

A larger number means tighter binding. Prefix signs use precedence 30, so exponentiation binds more tightly than a leading minus:

-2 ** 2       means -(2 ** 2)
(-2) ** 2     means (-2) ** 2

Associativity answers a different question: how do consecutive operators at the same precedence group? Subtraction groups left, while exponentiation groups right:

9 - 4 - 1     means (9 - 4) - 1
2 ** 3 ** 2   means 2 ** (3 ** 2)

These are choices made by this language. The ** operator means exponentiation here; ^ is unsupported. Decimal spellings such as 01 are accepted as the integer one, so this is not a complete Python expression grammar.

Keep the lexer and the tree simple

The lexer emits integers, operator symbols, and an explicit end-of-input token. It records zero-based character offsets for diagnostics. A final catch-all pattern rejects unknown characters instead of silently skipping them. The ** alternative comes before the single-character * alternative so the two-character operator stays together.

The AST has three node kinds: an integer, a unary operation with one child, or a binary operation with two children. Parentheses control construction of the tree; they do not need a node of their own in this example.

We use frozen data classes for the token and node records. Python's data class documentation explains the generated constructors and representations. The regular expression behavior is described in the standard library documentation.

The complete implementation

Save this as expr_parser.py and run it with Python 3.10 or later. It uses only the standard library.

from dataclasses import dataclass
import re


@dataclass(frozen=True)
class Token:
    kind: str
    text: str
    offset: int


@dataclass(frozen=True)
class Node:
    kind: str
    value: int | str
    children: tuple = ()


TOKEN = re.compile(
    r"(?P<WS>\s+)|(?P<INT>[0-9]+)|"
    r"(?P<OP>\*\*|[+*()\-])|(?P<BAD>[\s\S])"
)


def lex(source):
    tokens = []
    for match in TOKEN.finditer(source):
        kind = match.lastgroup
        if kind == "WS":
            continue
        if kind == "BAD":
            raise SyntaxError(
                f"Unexpected character {match.group()!r} "
                f"at offset {match.start()}"
            )
        tokens.append(Token(kind, match.group(), match.start()))
    tokens.append(Token("EOF", "", len(source)))
    return tokens


# operator: (precedence, associativity)
OPERATORS = {
    "+": (10, "left"),
    "-": (10, "left"),
    "*": (20, "left"),
    "**": (40, "right"),
}
PREFIX_PRECEDENCE = 30


class Parser:
    def __init__(self, source):
        self.tokens = lex(source)
        self.index = 0

    @property
    def current(self):
        return self.tokens[self.index]

    def take(self):
        token = self.current
        self.index += 1
        return token

    def prefix(self):
        token = self.current
        if token.kind == "INT":
            self.take()
            return Node("int", int(token.text))
        if token.text in ("+", "-"):
            self.take()
            operand = self.expression(PREFIX_PRECEDENCE)
            return Node("unary", token.text, (operand,))
        if token.text == "(":
            self.take()
            node = self.expression(0)
            if self.current.text != ")":
                raise SyntaxError(
                    f"Expected ')' at offset {self.current.offset}"
                )
            self.take()
            return node
        raise SyntaxError(
            f"Expected an expression at offset {token.offset}"
        )

    def expression(self, minimum=0):
        left = self.prefix()
        while self.current.text in OPERATORS:
            operator = self.current.text
            precedence, associativity = OPERATORS[operator]
            if precedence < minimum:
                break
            self.take()
            next_minimum = precedence + (associativity == "left")
            right = self.expression(next_minimum)
            left = Node("binary", operator, (left, right))
        return left

    def parse(self):
        node = self.expression(0)
        if self.current.kind != "EOF":
            raise SyntaxError(
                f"Unexpected token {self.current.text!r} "
                f"at offset {self.current.offset}"
            )
        return node


def show(node):
    if node.kind == "int":
        return str(node.value)
    children = " ".join(show(child) for child in node.children)
    return f"({node.value} {children})"


if __name__ == "__main__":
    examples = ["7 + 2 * 5", "9 - 4 - 1", "2 ** 3 ** 2",
                "-2 ** 2", "(-2) ** 2"]
    for source in examples:
        print(f"{source} -> {show(Parser(source).parse())}")

Running python expr_parser.py prints:

7 + 2 * 5 -> (+ 7 (* 2 5))
9 - 4 - 1 -> (- (- 9 4) 1)
2 ** 3 ** 2 -> (** 2 (** 3 2))
-2 ** 2 -> (- (** 2 2))
(-2) ** 2 -> (** (- 2) 2)

The display puts each operator before its children, making grouping visible. (- 2) is a unary minus; (- 9 4) is subtraction. The actual node also stores its kind, so later compiler stages do not have to infer that distinction from the printed form.

Why the minimum precedence matters

The core routine is expression(minimum). It first obtains a left operand from prefix(). It then consumes binary operators whose precedence is at least the requested minimum.

When it encounters an operator, it recursively builds the right operand. The threshold for that recursive call controls associativity:

next_minimum = precedence + (associativity == "left")

Python treats the comparison result as zero or one in this addition. For a left-associative operator, the right operand requires a strictly higher precedence. For a right-associative operator, equal precedence is allowed.

Walk through 9 - 4 - 1. The first subtraction has precedence 10. Its right-hand recursive call uses minimum 11, so it consumes 4 and stops before the next subtraction. The outer loop builds 9 - 4, then attaches the remaining - 1.

For 2 ** 3 ** 2, the right-hand call keeps minimum 40. The second ** is allowed inside that call, giving the tree 2 ** (3 ** 2).

For 7 + 2 * 5, the right operand of + is parsed with minimum 11. Multiplication has precedence 20, so 2 * 5 becomes one subtree before the addition node is built.

Prefix signs work through the same threshold mechanism. A leading minus calls expression(30), allowing exponentiation at 40 inside its operand while leaving multiplication at 20 outside. Thus -2 ** 2 becomes a unary minus around an exponentiation tree. A negative exponent such as 2 ** -3 also parses: the right operand can begin with a prefix sign.

Reject leftover input

Finishing an expression is not the same as finishing the input. Without the end-of-input check in parse(), the source 2 3 could be mistaken for a successful parse of 2, with 3 ignored.

Try these malformed inputs:

for source in ["", "2 3", "7 +", "(1 + 2", "1 @ 2"]:
    try:
        Parser(source).parse()
    except SyntaxError as error:
        print(repr(source), "->", error)

They exercise a missing operand, trailing input, an incomplete operation, an unmatched parenthesis, and an illegal character. The offsets refer to positions in the source string, not byte addresses.

For regression tests, assert tree shapes as well as evaluated answers. Two grouping mistakes can occasionally produce the same value. Before publication, this implementation's trees were checked against Python's ast parser for 5,000 generated expressions within the shared grammar, alongside eight explicit tree cases and 19 invalid-input cases. The comparison parses expressions; it does not execute them.

Where this fits in a compiler

The parser consumes syntax and builds structure. A later pass can resolve names, check operand types, fold constants, or emit instructions. Keeping those jobs separate makes it easier to inspect whether a failure comes from parsing or from a later compiler stage.

The example materializes all tokens and allocates tree nodes. It is a learning prototype: it has no input-length or nesting limits, and deeply nested input can exceed Python's recursion limit. Large integer conversions can also fail independently of syntax. A fuller front end should add resource limits, source spans on AST nodes, and diagnostics appropriate to its users.

As a next exercise, add identifiers as primary expressions and display their nodes before attempting code generation. The existing binary-operator loop can remain the same.

For a larger C++ example, LLVM's Kaleidoscope parser and AST tutorial shows how expression parsing fits alongside function definitions and other language constructs.

compilersparsingastpythonlanguage-design