The front end: text to tree¶

Three questions, in order. What are the words? What is the structure? And, going back the other way, how do I turn a structure into words again?

Words: the lexer¶

A compiler does not work on characters. The first thing it does is chop the text into the smallest pieces that mean something on their own, called tokens. let x = 42 is four of them:

front/lexer.py does that, and it is mostly one regular expression with a named group per kind, tried in the order written. Everything after this point works on tokens, which is why the grammar never has to think about whitespace.

Two of OCaml's rules need real code, and they are why this is a file of its own rather than part of the grammar.

Comments nest. (* a (* b *) c *) is one comment, not a comment ending at the first *). No regular expression can say that, so skip_comment counts the pairs.

'a' is a character and 'a is a type variable. They start the same way. The fix is one ordered choice: try the character pattern first, because a character literal always has a closing quote and a type variable never does.

    | (?P<char>  ' (?: {escape} | [^\\'] ) ' )
    | (?P<tyvar> ' [a-z_][A-Za-z0-9_']* )

That ordering is the rule. Swap the two lines and 'a' becomes a type variable followed by a stray quote.

Structure: the parser¶

Given the tokens, what is the shape? front/peg.py is a small engine and front/parser.py is the grammar written on top of it.

The engine provides the pieces any grammar needs. A parser is a function from a position in the token list to either a result and a new position, or None for "did not match", and the combinators build bigger ones out of smaller:

def seq(*parsers): ...      # a, then b, then c
def alt(*parsers): ...      # try a; if it fails, try b
def many(parser): ...       # as many as there are
def opt(parser): ...        # one, or none

This style is called PEG, for parsing expression grammar, and it has two properties that matter here. alt tries its alternatives in order and takes the first that works. many is greedy and takes as much as it can.

Those two properties are why OCaml suits it. The language is full of forms that run as far to the right as they can:

let x = 1 in a; b            (* the let's body is `a; b`, not just `a` *)
match n with 0 -> a; b       (* the arm's body is `a; b` *)
if a then if b then c else d (* the else belongs to the inner if *)
fun x -> a; b                (* the function's body is `a; b` *)

Greedy repetition gets all four right by simply not stopping early. A parser generator in the older LR style resolves the same four conflicts, but only after somebody writes a table of precedences telling it how.

The grammar reads close to the notation a textbook uses:

if_expr = act(
    seq(lit("if"), seq_expr, lit("then"), expr, opt(seq(lit("else"), expr))),
    lambda v: s.If(v[1], v[3], v[4][1] if v[4] else None),
)

seq(...) matches the pieces, and act says what to build out of them: an If node whose parts are the second, fourth and fifth things matched.

One table, ten rules¶

OCaml has ten levels of binary operator. Writing ten near-identical rules would work and would be ten places to make a mistake, so the table is data and the rules are generated from it:

LEVELS: tuple[tuple[tuple[str, ...], str], ...] = (
    (("||",), "right"),
    (("&&",), "right"),
    (("=", "<>", "<", "<=", ">", ">="), "left"),
    (("@", "^"), "right"),
    (("::",), "right"),
    (("+", "-", "+.", "-."), "left"),
    (("*", "/", "*.", "/.", "mod", "land", "lor", "lxor"), "left"),
    (("**", "lsl", "lsr", "asr"), "right"),
)

Loosest first. _level turns one row into one rule, and the cascade is built by folding over the table. Add an operator to a row and the parser has it.

The table is used a second time, on the way out.

Packrat¶

"Packrat" means the engine remembers. Rule caches what it found at each position, so a seventeen-level cascade costs one pass rather than seventeen. Eight lines, and it makes performance a question nobody has to think about again.

Back the other way: the printer¶

front/emit.py turns a tree into text. Two uses, and the second is why it exists.

It shows you what the compiler thought you wrote. If a bracket appears that you did not type, the parser grouped it differently from you.

And it is how the parser is checked. Print a tree, read the printed text back, compare the two trees:

assert parse(unparse(parse(source))) == parse(source)

Over all forty-one corpus programmes, plus eighteen hand-written cases where dropping a bracket would change the meaning. A grammar rule that groups the wrong way survives every assertion somebody thought to write, and dies here.

Brackets are the difficulty of printing, and none of them is counted by hand. astero.emit supplies the rule — a child needs brackets when it binds less tightly than the position it sits in — and this file supplies the table. The table is parser.LEVELS, the same rows the parser cascades over:

OPERATOR_LEVEL: dict[str, Level] = {
    op: Level(BINARY_BASE + index, ASSOC[assoc])
    for index, (ops, assoc) in enumerate(LEVELS)
    for op in ops
}

One declaration, two consumers: it groups on the way in and brackets on the way out. A row added to LEVELS changes both, and they cannot disagree.

It caught a defect the first time it ran. Constructor arguments and list elements shared a helper, so C (a, b) printed as C (a; b). Four programmes parsed, resolved and looked right; only the reparse disagreed.

Why write the engine at all¶

Because the test suite runs on Python 3.11 through 3.15 with pytest and nothing else installed, and astero and both its sibling examples have no dependencies. peg.py is 125 lines of code, which is what that costs.

There is a note in the file saying that if it ever passes about two hundred, take lark instead. The point of writing it down is that the decision has a stated ceiling rather than being permanent by inertia.

Next: the middle end, where the tree stops being a shape and starts having a meaning.