What a compiler is

A compiler reads text in one language and writes the same meaning in another. That is the whole job description. Everything else — the phases, the trees, the tables — exists because doing that job in one step is impossible for anything larger than a pocket calculator.

The reason is that the two languages disagree about almost everything. Here is a line of PL/0:

result := arg * arg

and here is roughly what a machine needs to be told to do it, on an ARM64 processor:

ldr  x8, [x29, #-24]
mul  x8, x8, x8
str  x8, [x29, #-32]

Between those two forms sit every question a compiler has to answer:

  • Where does result end up in memory, and how does the machine reach it?
  • Is arg even declared? Declared where — this procedure, or an enclosing one?
  • Does * mean integer multiply here, and what happens when it overflows?
  • Which registers are free, and what must be saved before they are used?

Nobody answers all of those at once. A compiler answers them in an order, and each stage hands the next one a form that has already settled some questions and left the rest. The stages are not the point — the ordering is. That is the idea this whole series is really about, and PL/0 is the smallest program that shows it end to end.

Why this compiler

Niklaus Wirth published PL/0 in Algorithms + Data Structures = Programs (1975), and in full source in Compilerbau (1977). He designed the language for exactly one purpose: to be the largest language a complete compiler for it still fits in a reader’s head.

He got it right, and the proportions are worth stating plainly. PL/0 has:

  • one data type (a signed integer) — so no type checking, no conversions, no layout rules
  • no input or output statements — none at all
  • constants, variables, and nested procedures that take no parameters
  • if … then, while … do, assignment, and call
  • five arithmetic operators and six comparisons

That list is short enough to be suspicious. It is not: everything a compiler must genuinely do is still in there. Names still have scope, and the scope still nests. Procedures still nest inside procedures, so a procedure can read a variable declared two levels out — and that single feature is responsible for most of what a real compiler’s runtime does. Expressions still have precedence. Control flow still needs jumps to places that have not been generated yet.

What PL/0 removes is the bulk, not the ideas. That is why it survived fifty years of curricula, and why the version in this series still earns its keep.

The whole language

Here is PL/0’s grammar, in the notation Wirth invented for it. { x } means “zero or more x”, [ x ] means “optional x”, and | separates alternatives.

program     = block "." .

block       = [ "const" ident "=" number { "," ident "=" number } ";" ]
              [ "var" ident { "," ident } ";" ]
              { "procedure" ident ";" block ";" }
              statement .

statement   = [ ident ":=" expression
              | "call" ident
              | "begin" statement { ";" statement } "end"
              | "if" condition "then" statement
              | "while" condition "do" statement ] .

condition   = "odd" expression
            | expression ( "=" | "#" | "<" | "<=" | ">" | ">=" ) expression .

expression  = [ "+" | "-" ] term { ( "+" | "-" ) term } .

term        = factor { ( "*" | "/" ) factor } .

factor      = ident | number | "(" expression ")" .

That is the complete language. Twenty-two lines.

Read block again, because it is the interesting one: a block contains procedure ident ";" block ";" — a block contains blocks. That recursion is where the nesting comes from, and it is why the parser you will read in chapter 6 is a set of procedures that call each other in a circle.

The surprise

PL/0 has no output statement. Wirth’s solution, which catches everyone the first time, is that every store prints the value stored.

So this program:

{ squares of 1..9, the program every PL/0 introduction opens with }
const max = 10;
var arg, result;

procedure square;
begin
   result := arg * arg
end;

begin
   arg := 1;
   while arg < max do
   begin
      call square;
      arg := arg + 1
   end
end.

prints this:

1
1
2
4
3
9
4
16
5
25
6
36
7
49
8
64
9
81
10

The pairs are arg and then result: arg := 1 prints 1, then result := arg * arg prints 1, then arg := arg + 1 prints 2, and so on. The last lone 10 is the assignment that fails the loop test.

It looks like a quirk. It is actually the feature that makes PL/0 teachable: a program with no I/O can still be watched. You never have to trust that the compiler did the right thing — you can see every value it stored, in order. That property is what turns Wirth’s stack machine into an oracle in chapter 10, and it is why this series can prove its claims instead of asserting them.

Two programs worth reading now

Two more of the six programs shipped with the sources. First, Euclid’s algorithm — the oldest program there is:

var a, b;

procedure reduce;
begin
   while a # b do
   begin
      if a > b then a := a - b;
      if b > a then b := b - a
   end
end;

begin
   a := 48;
   b := 18;
   call reduce
end.

Note what is missing: PL/0 has if … then and no else at all, so a two-way choice is written as two guarded statements. # is “not equal”.

Second, the program that matters most for the back end:

var outer, answer;

procedure middle;
var scratch;
   procedure inner;
   begin
      scratch := outer * 2;
      answer := scratch + 1
   end;
begin
   scratch := 0;
   call inner
end;

begin
   outer := 20;
   call middle
end.

inner reads outer, which is declared two levels out, and writes scratch, declared one level out. Neither variable is in inner’s own frame. Making that work — at all, and then efficiently — is the single hardest thing any PL/0 back end does, and both back ends in this series are measured against it.

What this series builds

By the end of chapter 2 you will have two working PL/0 compilers on your machine. By the end of chapter 9 you will have taken the square program above all the way to native machine code, linked it with a C toolchain, and run the resulting executable — and you will be able to explain every stage it passed through.

That last part is what makes this different from a PL/0 course. Wirth’s original stops at an interpreter for an idealized stack machine, which is the right teaching decision for 1975 and leaves one honest gap: the interpreter is not a real target. The compiler in this series keeps his stack machine — it is far too good a teaching device to lose, and it becomes the reference the rest is checked against — and adds a second back end that emits a real intermediate language and hands it to a production code generator.

Two back ends behind one parse is also, conveniently, the best way to learn what a compiler’s middle really is.

Next: 2 — Get it running, where both compilers get built and run on your machine.