3 — The shape of a compiler

Open either twin’s directory and you find seven source files. They are not seven arbitrary slices — they are seven parts in one order, and the order is the lesson.

diagnostics  ←  scanner  ←  symbols  ←  pcode  ←  spectra  ←  parser  ←  driver

Each part names only parts to its left. scanner may use diagnostics; diagnostics may not use anything. parser may use everything before it; the driver may use all of them, and nothing uses the driver.

That arrow direction is the single most useful thing to know about the layout, because it tells you where to start reading (the left) and it tells you that nothing behind you can surprise you.

The seven

Roughly two and a half thousand lines for a complete compiler with two back ends. (The Mica twin is longer for one reason only: its comment density is higher, because it doubles as teaching material. The code itself is very nearly line for line.) You can read the whole thing over a weekend, and after this series you will want to.

Why that order

Every dependency in that line exists for a reason you can state in one sentence:

• diagnostics first, because every other part can fail, and a part that reports must not depend on anything that might itself fail.
• scanner before symbols, because an identifier’s spelling has a maximum length, and the table stores spellings.
• symbols before the back ends, because a procedure’s handle — the number the back end hands out — is stored in the symbol table.
• pcode before spectra, for one small thing: the two back ends must agree on what a comparison answers, down to the bit, and one of them has to own that decision.
• parser after both back ends, because the parser drives them.
• the driver last, because deciding which road to take is not the parser’s business.

Nothing in that list is a matter of taste. Each edge is forced by a fact about the program, and if you tried to reverse one you would find out immediately.

Front end, middle, back end

Those three words get used loosely. Here they have exact referents:

    source text
         │
         ▼
    ┌─────────────────────────────┐
    │ FRONT END                   │   scanner · symbols · parser
    │ what the program says       │   → is it well formed? what do the names mean?
    └─────────────────────────────┘
         │
         │   the seam: an interface, not a data structure
         ▼
    ┌─────────────────────────────┐
    │ BACK END                    │   pcode  →  a stack machine
    │ what the machine does       │   spectra →  Dragon → native code
    └─────────────────────────────┘

The front end is the part that knows PL/0. The back end is the part that knows a machine. Neither knows the other, and the whole reason this compiler can have two back ends is that the boundary between them is an interface rather than a shared data structure.

That is worth dwelling on, because it is the design decision that most often goes wrong in real compilers. Wirth’s original had no seam at all: his parser called gen(f, l, a) directly, which emitted a stack-machine instruction on the spot. It is a perfectly good program — but the parse could not exist without the p-code, and the p-code could not be replaced without rewriting the parse.

Naming the seam costs, in C, one struct of function pointers. It buys a second back end. Chapter 7 is entirely about that trade.

What flows across it

Here is the thing that surprises people who have read about compilers but not written one: PL/0’s front end never builds a syntax tree.

There is no AST in this compiler. The parser walks the source once and calls the back end as it goes:

case number:
    parser->backend->load_constant(parser->backend, parser->scanner.number);
    scanner_next(&parser->scanner);
    break;

That is a factor being parsed and a constant being emitted, in the same breath. This is called syntax-directed translation, and it is how compilers were built before memory was cheap. It is still how simple compilers are built, and it is the clearest possible demonstration that a tree is not a requirement — it is a tool you reach for when you need to look at the program more than once (to optimize it, to reorder it, to type-check it in several passes).

PL/0 needs none of that, so it has none of that. When you meet a compiler that does build a tree, you will know precisely what the tree bought.

The protocol across the seam

If the parser is not handing over a tree, what is it handing over? A sequence of operations, in a stack discipline:

load_constant 3      →   push 3
load_variable 0,1    →   push the variable
arithmetic op_add    →   pop two, push their sum
store_variable 0,2   →   pop, store it

That shape is not chosen at random. PL/0’s expressions are naturally stack-shaped — a * b + c evaluates by pushing, combining, pushing, combining — so a stack protocol is the smallest interface that carries them.

And here is the part worth remembering: a back end does not have to be a stack machine to implement a stack protocol. Wirth’s back end is one, so it implements arithmetic by emitting one instruction. The Dragon back end is not — it wants three-address code, t3 = t1 + t2 — so it keeps a stack at compile time, pops two operand names, and emits one three-address instruction. Nothing is on a stack when the program runs.

That single trick — a compile-time stack turning stack-shaped input into register-shaped output — is one of the most reusable things in this series.

The two roads, end to end

                          ┌──→  pcode  ──→  interpret  ──→  the oracle
   text → scan → parse ───┤                                 (what the program means)
                          └──→  spectra ──→  Dragon    ──→  native code
                                                            (what the machine runs)

The top road is a complete compiler-and-interpreter in 500 lines. It is slow, it is idealized, and it is definitional: whatever it prints is what the program means.

The bottom road goes through validation, control-flow analysis, an SSA middle-end, storage placement, register allocation and instruction emission — the same code that compiles the Mica language — and produces an executable.

Both roads run from the same parse. If they ever disagree, the bottom one is wrong. That asymmetry is what makes the top road worth keeping, and it is the subject of chapter 10.

How to read the source from here

You now have enough to open either twin and not get lost. A suggested order, which is also the order of the chapters that follow:

1. diagnostics — read it whole, it is 80 lines and it makes everything else easier to follow
2. scanner — read scanner_next / NextSymbol; skip the helpers on the first pass
3. symbols — read it whole
4. parser — read block, then statement, then expression / term / factor
5. pcode — read the interpreter’s switch first, then the emitter
6. spectra — last, and read chapter 9 beside it

Resist reading spectra early. It is the part that talks to a production backend, and it is much easier once you have seen what the other back end does with the same calls.

Next: 4 — The scanner, where text becomes words.