Self-Hosting Begins: A Lexer, a Parser, and a Shared Tree

The last part ended on a small self-reference: a Mere program generating documentation about Mere. Part V is about the large one this whole series has been building toward — a Mere program that processes Mere itself. The compiler so far is written in OCaml: an OCaml lexer, an OCaml parser, an OCaml type checker, evaluator, and code generators. Self-hosting means rewriting all of that in Mere, until the language can compile its own source. This episode is the front end: the part that turns a string of source text into a structured syntax tree.

The pretty-printer came first, and it set the target

There is an obvious order in which to build a compiler front end — lexer, then parser, then everything that consumes the parser’s output. This project did it backwards on purpose, and the reason is worth understanding, because it shaped everything after.

The first self-hosted component wasn’t the parser; it was the pretty-printer — the tool that takes a syntax tree and formats it back into clean source text. That seems out of sequence: how do you format a tree before you have a parser to produce one? The answer is that the pretty-printer was fed hand-written trees at first, and in being written it had to declare the one thing everything downstream depends on: the shape of the syntax tree itself. To format a tree, you must first say what a tree is — what a let node looks like, what an if holds, how a function application is represented. The pretty-printer defined that data type.

Which means that when the parser came to be written, it did not get to invent its own output. It had a fixed target: produce exactly the tree the pretty-printer already consumes. The contract was set before the parser existed. And the payoff was concrete at every step — with the pretty-printer working, each stage of the front end had a visible result. The formatter already ran in the browser on hand-coded trees; the parser was, in the project’s own words, the last obstacle to a real in-browser formatter that accepts typed source instead of hand-built trees.

The shared tree is the spine

That syntax tree — the abstract syntax tree, or AST — is the most important object in the whole self-hosted compiler, because it is the contract between every phase. The parser produces it. The pretty-printer consumes it. The type checker, the evaluator, and the code generator, all coming later in this part, consume it too. Define it once, and every component speaks the same language to every other. Defining it first, through the pretty-printer, meant the parser aimed at a fixed point rather than a moving one, and everything built afterward inherited the same fixed point.

And here a decision from the very start of the series pays off again. An AST is, structurally, a sum of node shapes: an expression is a literal or a variable or an if or an application or a match, and each shape carries its own fields. That is precisely an algebraic data type — a variant of records — which is exactly what Mere, as a small ML-family language, was built to represent cleanly. The episode near the start on choosing OCaml made the bet that a host with algebraic data types would make writing a compiler natural; the self-hosted compiler collects on the same bet in the language’s own terms. Mere describing Mere’s syntax tree is the language turned on itself, and it fits because a syntax tree is the canonical thing sum types are for.

Lexer, then parser, held to a reference

With the tree defined, the front end is two pieces. The lexer turns the raw source string into a flat list of tokens — keywords, operators, literals, identifiers — the small vocabulary of the language recognized and separated out. The parser is a recursive-descent walk over that token list, climbing through the language’s dozen levels of operator precedence and assembling the tree the pretty-printer defined. Neither is conceptually novel; both are the standard shape of a hand-written front end, now expressed in Mere.

What keeps them honest is the same discipline that governed the backends. There is already an OCaml lexer and an OCaml parser — the original front end — and they serve as the reference. The self-hosted parser is cross-validated against them: given the same source, it must produce the same tree the OCaml parser produces. This is the parity rule from Part IV, moved up a level. Where the four backends were held to the interpreter’s bytes, the self-hosted front end is held to the OCaml front end’s trees — two implementations of “parse this source,” required to agree, so that a divergence is caught automatically instead of trusted away.

The front end could also be smaller than its reference, because it only has to parse the subset of Mere that the self-hosted compiler is itself written in. The constructs the compiler doesn’t yet use on itself could be deferred — the same minimal-honest-version discipline the whole project runs on, now applied to the compiler parsing its own kind. You build exactly enough of the language to read the language you actually wrote.

The front end now exists in Mere: source text goes in, a shared syntax tree comes out, and it matches the reference. But a parser that only its author has run is not yet proven. The sharpest test is to turn it on the most demanding input available — its own source code, and the source of the other self-hosted components. Next: the formatter and the cross-validation harness, and the moment the self-hosted front end parses the self-hosted front end.