~/systems/parsers

Parsers and interpreters

Turn text into tokens, tokens into structure, and structure into a value. One small function per grammar rule handles precedence and nesting.

what

Tokenize first, then write one function per grammar rule (expr, term, factor). Each reads the tokens it owns and calls the next rule down, so precedence and parentheses come out right.

use when

Calculators and formulas, nested function-call syntax, S-expressions, config or query strings, URL parameters, toy languages and type signatures.

time

O(n)

space

O(n), or O(depth) beyond the tokens

You’ll recognise it when

The input is text with structure: "2 * (3 + 4)", "add(1, mul(2, 3))", "(a (b c) d)", "a=1&b=2".
There are precedence rules (* before +) or nesting (parentheses, brackets, calls inside calls).
You must reject malformed input with an error instead of guessing.
The task says evaluate, interpret, infer, or “build the tree”.

It’s often confused with a plain stack problem. Bracket matching and simple +/- calculators can be done with a stack, but once there are several precedence levels or a real grammar, one function per rule is easier to get right and to extend.

The idea

Reading a recipe, you don’t see letters, you see words and numbers (“2 cups flour”). Then you see structure: this step, inside that section. Only then do you act on it. Parsers work in the same three stages: tokenize the characters into tokens, parse the tokens into structure, evaluate the structure.

For the parsing stage, write the grammar down first, one rule per precedence level, lowest first:

expr   := term (("+" | "-") term)*
term   := factor (("*" | "/") factor)*
factor := "-" factor | NUMBER | "(" expr ")"

Then give each rule its own function. expr calls term, term calls factor, and factor calls expr again for parentheses. Because a term is always finished before expr looks at the next +, multiplication binds tighter without any precedence table. That’s recursive descent.

How it works

Evaluate 2 * -(3 - 5). The parser keeps tokens and a position pos; peek() looks at the next token and take() consumes it.

Tokenize. Skip spaces, read a run of digits as one number, and keep each symbol as its own token: tokens = [2, "*", "-", "(", 3, "-", 5, ")"]. Any other character is an error right here.
expr asks for a term, and term asks for a factor. factor takes the next tok, the number 2, and returns it.
Back in term, peek() sees *, so it takes it and asks for another factor.
This factor takes -: a minus where a value should start is unary. It returns minus whatever the next factor gives.
That next factor takes (, so it calls expr for what’s inside. The inner expr reads 3, sees -, reads 5, and returns -2. Then factor insists the next tok is ).
Unwind. The unary minus turns -2 into 2. term computes 2 * 2 = 4. expr sees no + or - after it, so it returns 4.
Check the end. pos must equal len(tokens). Leftover tokens (as in "1 2") mean the input wasn’t one expression, so it’s an error, not a silent 1.

Why it’s correct: each function consumes exactly the tokens of one instance of its rule. The while loops in expr and term combine results left to right, so 10 - 4 - 3 is (10 - 4) - 3 = 3, and precedence follows from which function calls which.

class ParseError(ValueError):
    pass


def tokenize(text):
    tokens, i = [], 0
    while i < len(text):
        ch = text[i]
        if ch == " ":
            i += 1
        elif ch.isdigit():
            j = i
            while j < len(text) and text[j].isdigit():
                j += 1
            tokens.append(int(text[i:j]))          # a whole number is one token
            i = j
        elif ch in "+-*/()":
            tokens.append(ch)
            i += 1
        else:
            raise ParseError(f"unexpected {ch!r} at {i}")
    return tokens


class Calculator:
    # expr   := term (("+" | "-") term)*
    # term   := factor (("*" | "/") factor)*
    # factor := "-" factor | NUMBER | "(" expr ")"

    def evaluate(self, text):
        self.tokens = tokenize(text)
        self.pos = 0
        value = self.expr()
        if self.pos != len(self.tokens):
            raise ParseError(f"unexpected {self.tokens[self.pos]!r}")
        return value

    def peek(self):
        return self.tokens[self.pos] if self.pos < len(self.tokens) else None

    def take(self):
        tok = self.peek()
        if tok is None:
            raise ParseError("unexpected end of input")
        self.pos += 1
        return tok

    def expr(self):
        value = self.term()
        while self.peek() in ("+", "-"):
            if self.take() == "+":
                value += self.term()
            else:
                value -= self.term()
        return value

    def term(self):
        value = self.factor()
        while self.peek() in ("*", "/"):
            op, right = self.take(), self.factor()
            if op == "*":
                value *= right
            elif right == 0:
                raise ParseError("division by zero")
            else:
                q = abs(value) // abs(right)       # round toward zero, like C++ and Java
                value = q if (value < 0) == (right < 0) else -q
        return value

    def factor(self):
        tok = self.take()
        if tok == "-":
            return -self.factor()                  # unary minus
        if tok == "(":
            value = self.expr()
            if self.take() != ")":
                raise ParseError("expected )")
            return value
        if isinstance(tok, int):
            return tok
        raise ParseError(f"unexpected {tok!r}")

#include <cctype>
#include <stdexcept>
#include <string>
#include <vector>
using namespace std;

struct ParseError : runtime_error {
    using runtime_error::runtime_error;
};

struct Token {
    char kind;            // 'n' for a number, else the symbol itself: + - * / ( )
    long long value = 0;
};

vector<Token> tokenize(const string& text) {
    vector<Token> tokens;
    size_t i = 0;
    while (i < text.size()) {
        char ch = text[i];
        if (ch == ' ') {
            i++;
        } else if (isdigit((unsigned char)ch)) {
            long long v = 0;
            while (i < text.size() && isdigit((unsigned char)text[i])) v = v * 10 + (text[i++] - '0');
            tokens.push_back({'n', v});              // a whole number is one token
        } else if (string("+-*/()").find(ch) != string::npos) {
            tokens.push_back({ch});
            i++;
        } else {
            throw ParseError(string("unexpected ") + ch);
        }
    }
    return tokens;
}

class Calculator {
    // expr   := term (("+" | "-") term)*
    // term   := factor (("*" | "/") factor)*
    // factor := "-" factor | NUMBER | "(" expr ")"
    vector<Token> tokens;
    size_t pos = 0;

    char peek() const { return pos < tokens.size() ? tokens[pos].kind : '\0'; }

    Token take() {
        if (pos >= tokens.size()) throw ParseError("unexpected end of input");
        return tokens[pos++];
    }

    long long expr() {
        long long value = term();
        while (peek() == '+' || peek() == '-') {
            if (take().kind == '+') value += term();
            else value -= term();
        }
        return value;
    }

    long long term() {
        long long value = factor();
        while (peek() == '*' || peek() == '/') {
            char op = take().kind;
            long long right = factor();
            if (op == '*') value *= right;
            else if (right == 0) throw ParseError("division by zero");
            else value /= right;                     // C++ already rounds toward zero
        }
        return value;
    }

    long long factor() {
        Token tok = take();
        if (tok.kind == '-') return -factor();       // unary minus
        if (tok.kind == '(') {
            long long value = expr();
            if (take().kind != ')') throw ParseError("expected )");
            return value;
        }
        if (tok.kind == 'n') return tok.value;
        throw ParseError(string("unexpected ") + tok.kind);
    }

public:
    long long evaluate(const string& text) {
        tokens = tokenize(text);
        pos = 0;
        long long value = expr();
        if (pos != tokens.size()) throw ParseError("unexpected trailing input");
        return value;
    }
};

import java.util.*;

class ParseError extends RuntimeException {
    ParseError(String message) { super(message); }
}

class Calculator {
    // expr   := term (("+" | "-") term)*
    // term   := factor (("*" | "/") factor)*
    // factor := "-" factor | NUMBER | "(" expr ")"
    private List<Object> tokens;   // Long for a number, Character for a symbol
    private int pos;

    static List<Object> tokenize(String text) {
        List<Object> tokens = new ArrayList<>();
        int i = 0;
        while (i < text.length()) {
            char ch = text.charAt(i);
            if (ch == ' ') {
                i++;
            } else if (Character.isDigit(ch)) {
                int j = i;
                while (j < text.length() && Character.isDigit(text.charAt(j))) j++;
                tokens.add(Long.parseLong(text.substring(i, j)));   // a whole number is one token
                i = j;
            } else if ("+-*/()".indexOf(ch) >= 0) {
                tokens.add(ch);
                i++;
            } else {
                throw new ParseError("unexpected " + ch + " at " + i);
            }
        }
        return tokens;
    }

    long evaluate(String text) {
        tokens = tokenize(text);
        pos = 0;
        long value = expr();
        if (pos != tokens.size()) throw new ParseError("unexpected " + tokens.get(pos));
        return value;
    }

    private Object peek() { return pos < tokens.size() ? tokens.get(pos) : null; }

    private Object take() {
        if (pos >= tokens.size()) throw new ParseError("unexpected end of input");
        return tokens.get(pos++);
    }

    private long expr() {
        long value = term();
        while (Objects.equals(peek(), '+') || Objects.equals(peek(), '-')) {
            if (take().equals('+')) value += term();
            else value -= term();
        }
        return value;
    }

    private long term() {
        long value = factor();
        while (Objects.equals(peek(), '*') || Objects.equals(peek(), '/')) {
            Object op = take();
            long right = factor();
            if (op.equals('*')) value *= right;
            else if (right == 0) throw new ParseError("division by zero");
            else value /= right;                     // Java already rounds toward zero
        }
        return value;
    }

    private long factor() {
        Object tok = take();
        if (tok.equals('-')) return -factor();       // unary minus
        if (tok.equals('(')) {
            long value = expr();
            if (!take().equals(')')) throw new ParseError("expected )");
            return value;
        }
        if (tok instanceof Long number) return number;
        throw new ParseError("unexpected " + tok);
    }
}

Division rounds toward zero here, the way C++ and Java do. Python’s // rounds down instead (-7 // 2 is -4, not -3), so the Python version computes the quotient of the absolute values and fixes the sign. When a problem defines division, follow its rule exactly.

Building a tree instead of a number

The same functions can return nodes instead of values: factor returns ("num", 5), and term returns ("*", left, right). You then evaluate, print, or type-check the tree in a separate pass. Do that whenever the result is needed more than once, or a later level adds variables, functions or types.

S-expressions are the simplest case: the structure is the parentheses.

def parse(tokens):             # tokens: "(", ")" and atoms, in order
    tok = tokens.pop(0)        # use an index or a deque in real code
    if tok == "(":
        node = []
        while tokens[0] != ")":
            node.append(parse(tokens))
        tokens.pop(0)          # drop ")"
        return node
    return tok

# "(define (sq x) (* x x))" -> ['define', ['sq', 'x'], ['*', 'x', 'x']]

Why it’s O(n)

The tokenizer looks at each character once. The parser consumes each token once, and every function call either consumes a token or returns, so the work is O(n) for n characters. The tokens take O(n) space, and the call stack grows with the nesting depth: O(depth), which is O(n) in the worst case like ((((1)))).

That worst case matters in Python: a few thousand nested parentheses hit the default recursion limit. If the input can be that deep, raise the limit with care, or switch to an explicit stack (the shunting-yard algorithm does precedence with two stacks).

Common mistakes

Right-recursive rules flip subtraction

Writing expr := term "-" expr looks natural, but it groups from the right: 10 - 4 - 3 becomes 10 - (4 - 3) = 9. Loop over the operators instead.

return left - self.expr()        # ✗ 10 - (4 - 3)
while self.peek() == "-":        # ✓ (10 - 4) - 3
    value -= self.term()

Not checking for leftover tokens

expr happily stops after 1 in "1 2" or after 2 in "2)". Without a final check, malformed input returns a number instead of an error.

return self.expr()                                  # ✗ "1 2" gives 1
value = self.expr()
if self.pos != len(self.tokens): raise ParseError   # ✓ all input used

Treating every minus as subtraction

In 2 * -3 and -(1 + 2), the minus is unary: it appears where a value should start. Handle it in factor, which is exactly the place where a value starts.

if tok == "-": raise ParseError     # ✗ rejects "2 * -3"
if tok == "-": return -self.factor()  # ✓ unary minus binds tightest

Splitting on spaces instead of tokenizing

"(1+2)*3".split() is one token, and "12 3" would happily become 123 if you delete spaces first. Tokenize character by character, reading whole numbers.

tokens = text.replace(" ", "")   # ✗ "12 3" becomes 123
tokens = tokenize(text)          # ✓ [12, 3]: then the parser rejects it

Variations

More precedence levels. Each new level is one more rule and one more function: comparisons below +, exponent above *. A right-associative operator like ^ recurses on its right side instead of looping.
Function-call syntax. add(1, mul(2, 3)): factor sees a name, then (, then a comma-separated list of exprs, then ). Look the name up in a table of functions.
Spreadsheets. Each cell’s formula references other cells, which makes a dependency graph. Detect cycles and recompute in topological order.
Type inference. Parse type signatures into trees, then unify the formal parameter types with the actual ones: bind each generic name to a concrete type, fail on a conflicting binding, and substitute into the return type.
Config and query strings. Even “simple” formats have a grammar: key=value pairs, separators, escapes, repeated keys. Write it down before coding, and reject what it doesn’t allow.

Climb the ladder

Our parser problems in ladder order.

Tokenize an arithmetic expression: the first stage on its own.
Parse a label printer’s key=value line: a tiny grammar with strict errors.
URL Query Parameter Parsing: rules applied in a fixed order.
String to Integer (atoi): a scanner that reads as much as it can.
Evaluate String Expression: nested calls by recursive descent.
Validate edge pairs and print the S-expression: build a tree, validate it, print it.
Toy language type inference: type trees, unification, then parsing signatures.
Subword tokenizer: train, encode, decode: learned merges, the tokenizer behind language models.
ML config loader: inheritance, overrides, interpolation and validation.

Check yourself

5 quick questions. Pick an answer to see why it's right or wrong.

1
This parser handles subtraction by recursing on the right. What does this print?
```
def expr(tokens):
    left = tokens.pop(0)
    if tokens and tokens[0] == "-":
        tokens.pop(0)
        return left - expr(tokens)
    return left

print(expr([10, "-", 4, "-", 3]))
```
The recursion evaluates 4 - 3 first and subtracts that from 10, so it computes 10 - (4 - 3) = 9. Subtraction groups from the left: (10 - 4) - 3 = 3. A while loop that folds each new term into the running value gets that right.
2
A recursive descent parser has the rules expr := term (("+" | "-") term)* and term := factor (("*" | "/") factor)*. Why does it evaluate 2 + 3 * 4 as 14?
expr never sees a *: it asks term for a whole term, and term keeps multiplying until the next token isn’t * or /. So 3 * 4 comes back as one value, 12. Precedence comes from which function calls which, not from reordering tokens or from the host language.
3
A calculator problem says division rounds toward zero. What does this print in Python?
```
print(-7 // 2, int(-7 / 2))
```
// rounds down (toward minus infinity), so -7 // 2 is -4. int() drops the fraction, rounding toward zero, so int(-3.5) is -3. C++ and Java integer division round toward zero too. For big integers avoid the float: divide the absolute values and fix the sign.
4
Spreadsheet cells hold formulas like =A1 + B2 * 2 that refer to other cells, and some sheets contain reference cycles that must be reported. What’s the right plan?
Parse each formula to find the cells it uses, add those edges, and evaluate in topological order: every cell is computed once, after its inputs, and the cells left over form cycles. Repeating passes may never settle on a cycle, recursion without a memo redoes shared work and loops forever on a cycle, and eval runs arbitrary code.
5
A calculator returns 1 for the input "1 2" instead of reporting an error. Its expr, term and factor functions are correct. What’s missing?
expr correctly parses the expression 1 and stops at a token it can’t use. Only the caller knows the whole input should be one expression, so it must check that the position reached the end. Looping in expr would make 1 2 parse as something; joining numbers would turn it into 12.

Practice problems

Solve these right here, in Python, C++ or Java. Tests run as you go.

All 9 problems on this topic