Building a compiler with astero¶

This walks through examples/tinypy/, a complete compiler for a Python subset, written with astero and nothing else. It is about 170 lines and its output agrees with CPython on every program it accepts.

TinyPy has integers, variables, if, while, arithmetic, comparison and print. It compiles to a stack machine, because a stack target produces post-order code.

Read this to learn what astero is for. It is a library of derivations over a declared grammar: you import it and ask it questions, and the answers replace tables you would otherwise write by hand and have to keep correct.

Everything quoted below is the real file. tests/a_unit/test_tutorial.py fails if this page and the example drift apart.

1. Declare the language¶

astero declares Python once, in lang_py. A subset is that grammar restricted to the productions you admit:

ADMITTED = frozenset({
    "Module", "FunctionDef", "arguments", "arg", "Return",
    "Assign", "AugAssign", "If", "While", "Expr", "Pass",
    "Name", "Constant", "BinOp", "Compare", "Call",
    "Add", "Sub", "Mult", "FloorDiv", "Mod",
    "Lt", "LtE", "Gt", "GtE", "Eq", "NotEq",
})

and the grammar is built from that set:

TINYPY = PY.subset(ADMITTED, name="tinypy")

What you did not write: the fields of any production, their shapes, their sorts, their conditions, or which of them bind a name. All of that came with PY. A production TinyPy does not name is simply absent, so a rewrite that tries to build one fails at the rule rather than downstream.

2. Refuse what is outside it¶

Because the admitted set is data, refusing is one comprehension:

def check(tree: ast.AST) -> list[str]:
    """Refuse what TinyPy does not admit, naming the production."""
    return [
        f"line {n.lineno}: {type(n).__name__} is not TinyPy"
        for n in ast.walk(tree)
        if isinstance(n, (ast.stmt, ast.expr)) and type(n).__name__ not in ADMITTED
    ]

A language whose admitted set is a frozenset cannot have a refusal that disagrees with its grammar.

3. Desugar¶

x += 1 becomes x = x + 1, in one rule:

DESUGAR = Pass(
    "desugar",
    rules("ast.AugAssign(_t, _o, _v) => ast.Assign([_t], ast.BinOp(_t, _o, _v))"),
    eliminates=(ast.AugAssign,),
    grammar=TINYPY,
)

Two things.

The rule never mentions a context. In Python's AST an assignment target carries ctx=Store() and a read carries ctx=Load(), and a hand-written transformer has to set them. astero derives ctx from the field's role, so the rule cannot get it wrong. b[1] += 5 and x += 5 go through the same rule; a real compiler in this project once produced NaN for the first because its hand-written version set the wrong context on the subscript.

eliminates is a postcondition. If any AugAssign survives the pass, it raises. A pass that silently fails to fire is a pass you debug later.

4. Allocate slots¶

Every local needs a number. That means knowing which names a function binds; roles say exactly which positions bind:

def slots(fn: ast.FunctionDef) -> dict[str, int]:
    names = [a.arg for a in fn.args.args]
    for node in ast.walk(fn):
        names += sorted(names_bound_by(node, TINYPY, VARS))
    return {n: i for i, n in enumerate(dict.fromkeys(names))}

You do not enumerate target shapes. A tuple target, a starred target, a subscript, an as clause: bound_names answers for all of them, from the grammar. Three separate compilers in this project shipped a bug that was an enumeration of binding positions missing one shape.

5. Emit expressions¶

A stack machine wants the operator after its operands. Template composition gives you that for free. Put the operator last:

vm.rule("Name", "PUSH {id:slot}")
vm.rule("Constant", "CONST {value:lit}")
vm.rule("BinOp", "{left}\n{right}\n{op:binop}")
vm.rule("Compare", "{left}\n{comparators}\n{ops:cmp}")

Four rules and four projections. A projection is the escape hatch: {id:slot} runs a host function to turn a name into its slot number.

Emitter(TINYPY, levels=None): no precedence table, because a stack machine has no brackets. The same notation with a levels table emits bracketed infix JavaScript; the brackets are then derived from binding powers.

6. Emit statements: you write this yourself¶

case ast.While(test=test, body=body):
    top, done = self.label(), self.label()
    self.emit(f"{top}:")
    self.value(test)
    self.emit(f"JZ {done}")
    ...

astero has no notation for control flow: a template composes text, and a loop is a label, a conditional jump and a back edge. Every compiler in this project writes this by hand.

Here, astero gives you the gate.

7. Gate the dispatch against the grammar¶

def coverage() -> Coverage:
    """Every statement TinyPy admits is emitted. The gate, from the grammar."""
    return Coverage(handled=match_arms(Program.statement), expected=STATEMENTS)

match_arms reads the case ast.X() patterns back out of your source, so a match is measurable against a declaration. Add a statement to ADMITTED and forget to emit it, and this fails by name instead of your users finding it.

8. Run it¶

code = compile_source("def f(n):\n    t = 0\n    i = 0\n    while i < n:\n        t += i\n        i = i + 1\n    return t\n")

STORE 0
CONST 0
STORE 1
...
L1:
PUSH 2
PUSH 0
LT
JZ L2

examples/tinypy/vm.py runs it, so every program can be checked against CPython. That differential is the point: a compiler that agrees with itself proves nothing, and the source language is the oracle you already have.

What this cost, and what it did not¶

Where astero does not reach yet¶

1. Statements have no notation. Section 6. This is the largest piece of hand-written code astero has never addressed: five compilers in this project write the same match over the same statement productions, differing only in how the target spells a jump.
2. Emission renders text where a back end may want structure. to_text returns one string with newlines, so a line-oriented target splits it, and a back end that emits into a stream has to capture instead.

Two gaps this tutorial found on its first run are now closed, which is why the code above is shorter than the note that recorded them: declaring a subset needed a MACHINERY set the reader had to know about, and asking what a statement bound meant fetching the production and its Field first. Grammar.subset and names_bound_by both exist because writing this page found them missing.