Build your own programming language

"Write your own language" sounds like a career, not a blog post. But the core of an interpreter is small and the same in every language: turn text into tokens, tokens into a tree, then walk the tree and do what it says. We will build one that handles arithmetic and variables, and actually runs.

The one idea

Source code is a string, and a string is useless to a machine until it has structure. An interpreter builds that structure in stages: characters to tokens (scanning), tokens to a tree (parsing), tree to a result (evaluation). Each stage takes a messier input and hands the next stage something cleaner.

Stage 1: scanner

The scanner groups characters into tokens: numbers, names, operators.

import re

def scan(src):
    tokens = []
    for tok in re.findall(r"\d+\.?\d*|[A-Za-z_]\w*|[-+*/()=]", src):
        if tok[0].isdigit():
            tokens.append(("num", float(tok)))
        elif tok[0].isalpha() or tok[0] == "_":
            tokens.append(("name", tok))
        else:
            tokens.append((tok, tok))
    tokens.append(("eof", None))
    return tokens

scan("x = 3 + 4 * 2") gives a clean list of tagged tokens. No parsing decisions yet, just words.

Stage 2: a Pratt parser

Parsing math is where people get stuck, because 3 + 4 * 2 must become "3 plus (4 times 2)," not "(3 plus 4) times 2." A Pratt parser handles precedence with one idea: each operator has a binding power, and we keep consuming operators as long as they bind tighter than the level we are at.

class Parser:
    def __init__(self, tokens):
        self.toks = tokens
        self.i = 0
    def peek(self): return self.toks[self.i]
    def next(self):
        t = self.toks[self.i]; self.i += 1; return t

    BP = {"+": 10, "-": 10, "*": 20, "/": 20}

    def expr(self, min_bp=0):
        kind, val = self.next()
        if kind == "num":   left = ("num", val)
        elif kind == "name": left = ("var", val)
        elif kind == "(":
            left = self.expr(0); self.next()   # consume ")"
        else:
            raise SyntaxError(f"unexpected {kind}")
        while True:
            op = self.peek()[0]
            if op not in self.BP or self.BP[op] < min_bp:
                break
            self.next()
            right = self.expr(self.BP[op] + 1)  # +1 = left-associative
            left = ("bin", op, left, right)
        return left

Statements are either name = expr or a bare expr:

    def stmt(self):
        if self.peek()[0] == "name" and self.toks[self.i + 1][0] == "=":
            name = self.next()[1]; self.next()  # consume "="
            return ("assign", name, self.expr(0))
        return ("print", self.expr(0))

The result is an abstract syntax tree: nested tuples like ("bin", "+", ("num", 3.0), ("bin", "*", ("num", 4.0), ("num", 2.0))). The precedence is now baked into the shape.

Stage 3: walk the tree

Evaluation is a recursive function that returns a value for each node, carrying an environment of variables.

def ev(node, env):
    kind = node[0]
    if kind == "num":    return node[1]
    if kind == "var":    return env[node[1]]
    if kind == "bin":
        _, op, a, b = node
        a, b = ev(a, env), ev(b, env)
        return {"+": a + b, "-": a - b, "*": a * b, "/": a / b}[op]
    if kind == "assign":
        env[node[1]] = ev(node[2], env); return env[node[1]]
    if kind == "print":
        v = ev(node[1], env); print(v); return v

def run(src, env=None):
    env = env if env is not None else {}
    p = Parser(scan(src))
    return ev(p.stmt(), env)

Prove it runs

env = {}
run("x = 3 + 4 * 2", env)   # assignment: x = 3 + (4*2) = 11
run("x", env)               # a bare expression, so it prints
run("y = x * 10", env)      # uses a variable
run("y - 1", env)           # prints

11.0
109.0

x became 11, not 14, so precedence worked (the assignment itself prints nothing; the bare x on the next line is what shows 11). y read x back out of the environment. That is a real, if tiny, interpreter.

From here to a real language

Functions are the natural next step and reuse everything above: a function is a tree plus a captured environment (a closure), a call is "make a new environment binding the arguments, then ev the body." Add conditionals and loops (more node types), a bytecode compiler if you want speed instead of walking the tree each time, and error messages with line numbers. But the spine does not change: scan, parse, evaluate.

Understanding this is why syntax stops being scary, you can see the tree behind any code you read. That is the whole premise of the compilers track: the tools that run your code are programs you could have written.