Concepts / State, data structures and algorithms inside objects / Parsing and tokenizing

Parsing and tokenizing

Expressions, commands and file paths turned into structures.

Low-level design conceptState, data structures and algorithms inside objects2 Nov 2026

01The intuition

The problem it solves

A calculator must evaluate strings such as "2 + 3 * (4 - 1)". The first version walks the characters and tries to compute as it goes, with special cases bolted on each time a test fails.

def calc(s: str) -> int:
    total, num, op = 0, 0, "+"
    for ch in s + "+":
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch in "+-*":
            total = total + num if op == "+" else total - num if op == "-" else total * num
            num, op = 0, ch
    return total

It gets 2 + 3 * 4 wrong, because multiplication is applied to the running total instead of to 3 alone, and it has no idea what a bracket is. Patching it means more flags and more cases. The fix is to stop mixing two jobs: deciding what the pieces are, and deciding what they mean.

Build it one piece at a time

Step one: a tokenizer. It turns the string into a list of typed tokens, numbers and operators and brackets, and nothing else. Whitespace disappears here, multi-digit numbers are assembled here, and an unknown character is reported here with its position.

from dataclasses import dataclass

@dataclass(frozen=True)
class Token:
    kind: str       # "num", "op", "lparen", "rparen"
    text: str
    pos: int

def tokenize(s: str) -> list[Token]:
    out: list[Token] = []
    i = 0
    while i < len(s):
        ch = s[i]
        if ch.isspace():
            i += 1
        elif ch.isdigit():
            j = i
            while j < len(s) and s[j].isdigit():
                j += 1
            out.append(Token("num", s[i:j], i)); i = j
        elif ch in "+-*/":
            out.append(Token("op", ch, i)); i += 1
        elif ch in "()":
            out.append(Token("lparen" if ch == "(" else "rparen", ch, i)); i += 1
        else:
            raise ValueError(f"unexpected {ch!r} at {i}")
    return out

Step two: a parser that knows the grammar. Write the rules as small functions that call each other: an expression is terms joined by plus or minus; a term is factors joined by times or divide; a factor is a number or a bracketed expression. This is recursive descent, and precedence falls out of which function calls which.

class Parser:
    def __init__(self, tokens: list[Token]) -> None:
        self.toks, self.i = tokens, 0

    def peek(self) -> Token | None:
        return self.toks[self.i] if self.i < len(self.toks) else None

    def take(self) -> Token:
        t = self.toks[self.i]; self.i += 1; return t

    def expr(self) -> int:
        value = self.term()
        while (t := self.peek()) and t.kind == "op" and t.text in "+-":
            self.take()
            rhs = self.term()
            value = value + rhs if t.text == "+" else value - rhs
        return value

    def term(self) -> int:
        value = self.factor()
        while (t := self.peek()) and t.kind == "op" and t.text in "*/":
            self.take()
            rhs = self.factor()
            value = value * rhs if t.text == "*" else value // rhs
        return value

Step three: the leaf rule, and a clear error when the input ends early or a bracket is missing. Because the parser already produces a value, this is an evaluator; returning a node object instead of an integer would give a syntax tree that other code can print, simplify or compile.

class Parser(Parser):   # continued
    def factor(self) -> int:
        t = self.peek()
        if t is None:
            raise ValueError("unexpected end of input")
        if t.kind == "num":
            self.take(); return int(t.text)
        if t.kind == "lparen":
            self.take()
            value = self.expr()
            closing = self.peek()
            if closing is None or closing.kind != "rparen":
                raise ValueError(f"missing ) at {t.pos}")
            self.take(); return value
        raise ValueError(f"unexpected {t.text!r} at {t.pos}")

def calc(s: str) -> int:
    p = Parser(tokenize(s))
    value = p.expr()
    if p.peek() is not None:
        raise ValueError("trailing input")
    return value

Tokens for "2 + 3 * (4 - 1)" and the call chain that evaluates them:

Tokenkindconsumed by
2numexpr → term → factor
+opexpr loop
3numterm → factor
*opterm loop
(lparenfactor, which calls expr again
4 − 1num op numinner expr → 3
)rparenfactor

The inner term computes 3 × 3 = 9 before the outer expr adds 2, which is exactly the precedence the flat loop could not express.

Why it works

The invariant of the tokenizer is that its output is a faithful, typed version of the input with positions, so every later error can point at a character. The invariant of recursive descent is that each rule function consumes exactly the tokens of one construct and leaves the cursor just after it; precedence is encoded by nesting, the deepest rule binding tightest. Together the two layers mean each bug has one home.

Where it breaks: left recursion. A rule written as "expr is expr plus term" calls itself forever; the loop form above is the standard fix. Very deep nesting hits the recursion limit, so a production parser either limits depth or uses an explicit stack. And a grammar that needs to look more than one token ahead needs a smarter parser than this one.

tokenize: one pass, n characters. parse: each token consumed once, n tokens. Total linear in the input

The trade-off you must say out loud

For a fixed tiny language, a shunting-yard stack can be shorter; for a language that will grow (variables, functions, comparison operators) recursive descent is easier to extend, one function per rule. Say that you separated tokenizing from parsing on purpose, and whether you return values or a tree. The follow-up that usually comes next is "add variables" or "add a new operator", and the answer is a new token kind plus one rule change.

Where it shows up in the 100 Google problems

02Used in these problems