Reading a compiler teaches you its shape. Changing one teaches you why it has that shape.
These exercises are ordered by difficulty and each says which files it touches and where the difficulty actually is. Do them in either twin — or, if you want the strongest version of the lesson, do one in both and watch which language makes which part easier.
After every change, run both roads and compare. That habit is the whole of chapter 10:
make && make run
diff <(../build/c/pl0 run ../testdata/gcd.pl0) \
<(echo "run ../testdata/gcd.pl0" | ../build/Pl0/Pl0)1 — A better message · ten minutes
Pick a diagnostic you find unclear and improve its wording.
Touches: parser, and the self-check table in the driver.
The point: the table in the driver pins the number, not the text, so a better sentence does not break the check — while the count of diagnostics does. Notice which properties a test suite chooses to be strict about, and why.
2 — else · an hour
PL/0 has if … then and no else. Add it:
if a > b then a := a - b else b := b - aTouches: scanner (one reserved word — mind the alphabetical order in the
table), parser (parser_conditional).
Where the difficulty is: the code shape. Today the conditional reserves one label:
Label after = backend->new_label(backend);
condition(...); backend->jump_if_false(backend, after);
statement(...); backend->place_label(backend, after);With else you need two, and the then-branch must jump over the else-branch.
Draw the four instructions before you write them; this is the exercise where
drawing beats typing.
Check: rewrite gcd.pl0 with else and confirm both roads still print the
same trace.
3 — Exponentiation · an hour
Add ^, binding tighter than *, so 2 * 3 ^ 2 is 18.
Touches: scanner (one character), parser (one new procedure), and both
back ends.
Where the difficulty is: nowhere in the parser, which is the lesson. From
chapter 6: precedence is the nesting of
the procedures, so a tighter operator is a new procedure between term and
factor, and term calls it instead of factor. Fifteen lines.
The real work is in the back ends — PL/0’s machine has no power instruction, so you must decide: a loop of multiplications emitted inline, or a call to a runtime helper? Try inline first.
Extra credit: make ^ right-associative (2^3^2 is 512, not 64). Right
associativity is recursion where left associativity is iteration — one word
in the routine’s shape.
4 — Constant folding · two hours
Make the compiler compute 2 + 3 at compile time and emit lit 0 5.
Touches: either back end, or the seam.
Where the difficulty is: deciding where it belongs. Three defensible answers:
- in
parser_term, before callingarithmetic— simple, and it duplicates the work in every parser routine - in each back end’s
arithmetic— the p-code back end can look at the last emitted instruction; the Spectra one already has a compile-time operand stack and can check whether both operands are literals - in neither, because Dragon already folds constants in its SSA middle-end
Look at square.il and check whether the folding already happened. Finding out
that the work is already done somewhere else is a real and common result — and
noticing it before writing the code is a skill worth practising.
5 — Input and output · two hours
Add ? x (read into a variable) and ! e (write an expression), which is what
Wirth added in the 1984 Modula edition.
Touches: scanner, parser, both back ends.
Where the difficulty is: the back ends, and they diverge sharply. The
interpreter reads from stdin and writes with fprintf — five lines. The
Spectra road must emit a call to a runtime function, which means declaring its
signature in the unit, building an argument bundle, and naming an external
symbol the link must resolve. Read spectra_write_line_signature first; the
write half is that function with your own format.
The lesson: the same language feature is trivial in an interpreter and structural in a compiler. That asymmetry is why “just add a feature” estimates are so often wrong.
6 — Procedure parameters · a day
PL/0’s procedures take no parameters. Give them one value parameter:
procedure square(n);
begin
result := n * n
end;
...
call square(7)Touches: everything except diagnostics.
Where the difficulty is: the activation record. The parameter must live in the callee’s frame, but the caller computes its value — so somebody must define who writes it, and when, relative to the three housekeeping cells. That contract is called a calling convention, and this exercise is the smallest one you will ever design.
Decide, and write it down before you code:
- Where does the argument go — pushed before the frame header, or into a slot inside it?
- Who removes it, caller or callee?
- What does the symbol table store for a parameter, and how does
factortell a parameter from a variable?
The lesson: this is the exercise that makes the difference between reading about compilers and understanding them. Every question above has several correct answers and no obvious one, and the two back ends will force you to be precise in ways the interpreter alone would let you fudge.
7 — A second type · a day
Add boolean as a declared type, with true and false, and make the compiler
refuse if 3 then … and x := a > b where x is an integer.
Touches: symbols (an entry gains a type), parser (every expression
routine must now return a type), diagnostics (new messages).
Where the difficulty is: the parser’s shape. Today parser_expression
returns void, because there is only one type and nothing to say. The moment
there are two, every expression routine must answer what type did I just
produce — and that single change is what turns a syntax-directed translator
into a type checker.
The lesson: you now know exactly what a type system costs in a compiler’s structure, and it is not what most people expect. It is not the checking. It is that every routine’s signature changes.
8 — A new target · a weekend
Write a third back end. Fill in the sixteen operations of the seam and emit something else entirely: a stack machine of your own design, JavaScript, WebAssembly text format, or C.
Touches: one new file. Nothing else at all.
Where the difficulty is: in the target, not the compiler — which is the
entire point of chapter 7. Emitting C is the
easiest and the most illuminating, because C has no goto-free way to express
what place_label means and you will have to confront it.
Do this one if you do only one after the warm-ups. It is the exercise that proves the seam was worth naming, and it is the one that will change how you design your own interfaces.
9 — Fuzz the two roads · a weekend
Write a generator of random valid PL/0 programs, run each through both roads, and compare the output.
Touches: nothing in the compiler. A separate program.
Where the difficulty is: generating programs that are valid — names declared before use, levels within the limit, no division by zero — and that are interesting, meaning deeply nested and non-local. A generator that only produces flat arithmetic will find nothing.
The lesson: this is how production compilers are actually tested, and running it against a compiler you wrote yourself is the fastest way to understand why. Expect to find something. Everyone does.
Where to go next
The rest of Wirth. Appendix A is the 1975 compiler; his later Compiler Construction editions carry Oberon-0, which is PL/0’s successor with types, arrays, records and procedures with parameters — exercises 6 and 7 above, done properly by the person who designed the exercise.
The dragon book. Aho, Lam, Sethi and Ullman, Compilers: Principles, Techniques, and Tools. Everything this series showed you in one program, in full generality. Much easier to read once you have seen a working compiler.
A real backend. The Dragon SDK — the engine behind chapter 9 — is the same interface a serious frontend would use. If you want to write a compiler for a language of your own and get native code out of it, that is the road, and PL/0 is the worked example of driving it.
Read the twins whole. You have now seen every part of them. Two and a half thousand lines, and there is nothing left in there that this series has not explained.
One last thing
The most valuable thing in this series is not any technique. It is the shape of the whole:
A compiler is a sequence of representations, each one closer to the machine than the last, with an interface at every boundary you might want to replace.
PL/0 has four representations — text, symbols, an operation stream, and either p-code or Spectra — and one replaceable boundary. GCC has a dozen of each. The difference is quantity.
You can now read a compiler.
Back to: the chapter list · Appendix A — Wirth’s original