README

Crenshaw: Let's Build a Compiler in Free Pascal

An implementation of Jack Crenshaw's classic tutorial series "Let's Build a Compiler!" (1988–1995), rewritten for modern Free Pascal. Crenshaw was a software engineer and longtime columnist at Embedded Systems Programming who wrote a sixteen-part series walking the reader, from first principles, through the construction of a small but complete recursive-descent compiler. The original targeted Turbo Pascal and emitted Motorola 68000 assembly. This project has two implementations living side by side: v1 is a faithful port of chapters 1–10, preserving the pedagogical one-file-per-chapter structure and still emitting 68k assembly; v2 covers chapters 11–16 and takes the final TINY 2.1 language all the way through a unit-based compiler and a stack virtual machine so programs actually execute.

Directory layout

crenshaw/
????????? README.md              This file
????????? Makefile               Top-level build/test driver
????????? ci.sh                  Runs the complete test matrix
???
????????? cradle.pas             Ch 1  ??? I/O cradle
????????? expression.pas         Ch 2???3 ??? expression parser -> 68k
????????? interpreter.pas        Ch 4  ??? expression interpreter
????????? control.pas            Ch 5  ??? IF/WHILE/FOR/LOOP/REPEAT/BREAK
????????? boolean.pas            Ch 6  ??? boolean expressions, relational ops
????????? kiss.pas               Ch 7  ??? lexical scanner, keyword table
????????? tiny.pas               Ch 10 ??? single-file TINY 1.0 compiler
????????? verify.sh              v1 test harness (21 asserts)
????????? test1.tny              Sample v1 TINY sources
????????? test2.tny
????????? test3.tny
???
????????? v2/
    ????????? tinytypes.pas      Unit: shared types (TTokKind, TOpcode, TSymbol, ...)
    ????????? scanner.pas        Unit: lexical scanner (Ch 11???12)
    ????????? symtab.pas         Unit: symbol table, scopes
    ????????? codegen.pas        Unit: bytecode emitter, jump patching
    ????????? vm.pas             Unit: stack VM executing the bytecode
    ????????? tiny2.pas          Program: parser + driver (TINY 2.1)
    ????????? verify.sh          v2 demo suite (12 .tny tests)
    ????????? demo1.tny..demo7.tny  Feature demos
    ????????? adversarial/       11 tests probing error paths
    ????????? stress/            15 tests for perf/scale (run.sh)

Prerequisites

• Free Pascal Compiler 3.2.2 or later. Earlier 3.0.x releases are untested. Install with:
  bashCopy

  brew install fpc           # macOS
  sudo apt install fpc       # Debian/Ubuntu

• A POSIX shell (bash or zsh) for verify.sh, ci.sh, and Makefile.
• No other dependencies — no emulator, no assembler, no linker scripts.

Building

v1 (chapters 1–10)

Each chapter is a self-contained program. Build any one of them individually:

cd crenshaw
fpc -Mfpc cradle.pas
fpc -Mfpc expression.pas
fpc -Mfpc interpreter.pas
fpc -Mfpc control.pas
fpc -Mfpc boolean.pas
fpc -Mfpc kiss.pas
fpc -Mfpc tiny.pas

The -Mfpc flag selects FPC's native dialect (rather than ObjFPC/Delphi mode), which matches Crenshaw's Turbo Pascal idioms most closely.

v2 (chapters 11–16, TINY 2.1)

v2 is split into Pascal units. Compiling the main program is enough — FPC follows uses clauses and builds the dependency graph automatically:

cd crenshaw/v2
fpc -Mfpc tiny2.pas

This produces tiny2, the TINY 2.1 compiler-plus-VM executable. Feed it a source file:

./tiny2 demo1.tny

Top-level Makefile

From the repo root:

make all     # build every v1 chapter and v2
make test    # run the complete test matrix (v1 + v2 + adversarial + stress)
make clean   # remove binaries and .o/.ppu artifacts

Chapter-by-chapter breakdown

Chapters 8, 9, and 15 are Crenshaw's prose chapters; they have no accompanying program. All code chapters are complete.

TINY 2.1 language reference

TINY 2.1 is the language accepted by v2/tiny2. It extends the original Crenshaw TINY with typed variables, procedures and functions, short-circuit boolean operators, and proper WRITE/WRITELN semantics.

EBNF grammar

program        = "PROGRAM" ident ";" block "." ;

block          = { var-decl | proc-decl | func-decl } "BEGIN" statements "END" ;

var-decl       = "VAR" type ident { "," ident } ";" ;
type           = "INT" | "LONG" | "WORD" | "BYTE" | "CHAR" ;

proc-decl      = "PROCEDURE" ident [ "(" param-list ")" ] ";"
                 { var-decl } "BEGIN" statements "END" ";" ;

func-decl      = "FUNCTION" type ident [ "(" param-list ")" ] ";"
                 { var-decl } "BEGIN" statements "END" ";" ;

param-list     = param { "," param } ;
param          = type ident ;

statements     = statement { ";" statement } ;

statement      = assignment
               | if-stmt
               | while-stmt
               | read-stmt
               | write-stmt
               | return-stmt
               | halt-stmt
               | call-stmt
               | empty ;

assignment     = ident "=" expression ;

if-stmt        = "IF" expression statements
                 [ "ELSE" statements ]
                 "ENDIF" ;

while-stmt     = "WHILE" expression statements "ENDWHILE" ;

read-stmt      = "READ"   "(" ident { "," ident } ")"
               | "READCH" "(" ident ")" ;

write-stmt     = "WRITE"   "(" write-arg { "," write-arg } ")"
               | "WRITELN" "(" [ write-arg { "," write-arg } ] ")"
               | "WRITECH" "(" expression ")" ;
write-arg      = expression | string-literal ;

return-stmt    = "RETURN" [ expression ] ;
halt-stmt      = "HALT" ;
call-stmt      = ident [ "(" [ expression { "," expression } ] ")" ] ;

expression     = or-expr ;
or-expr        = and-expr { ("OR" | "XOR") and-expr } ;
and-expr       = rel-expr { "AND" rel-expr } ;
rel-expr       = add-expr [ rel-op add-expr ] ;
rel-op         = "=" | "<>" | "!=" | "<" | "<=" | ">" | ">=" ;
add-expr       = mul-expr { ("+" | "-") mul-expr } ;
mul-expr       = unary    { ("*" | "/" | "%") unary } ;
unary          = [ "-" | "+" | "NOT" | "!" ] primary ;
primary        = number
               | char-literal
               | ident [ "(" [ expression { "," expression } ] ")" ]
               | "(" expression ")" ;

ident          = letter { letter | digit | "_" } ;
number         = digit { digit } ;
char-literal   = "'" any-char "'" ;
string-literal = '"' { any-char-except-quote } '"' ;

Reserved keywords

PROGRAM   BEGIN    END      VAR
PROCEDURE FUNCTION RETURN
IF        ELSE     ENDIF
WHILE     ENDWHILE
READ      WRITE    WRITELN  READCH   WRITECH
HALT
AND       OR       XOR      NOT
INT       LONG     WORD     BYTE     CHAR

Keywords are recognised case-insensitively (the scanner uppercases them) but most examples use uppercase for historical fidelity to the Crenshaw style.

Types

Promotion rule. The result of any binary arithmetic or relational operation has the type of the widest operand. Mixing BYTE + LONG produces a LONG. No implicit narrowing: assigning a wider value to a narrower variable (e.g. a LONG expression into a WORD) compiles, but the compiler emits a warning of the form

warning: narrowing assignment from LONG to WORD at line 42

and the runtime performs a truncating store.

Operators and precedence

Listed lowest to highest. All operators in a row are left-associative (unary operators are prefix and right-associative).

NOT and ! are synonyms (! is retained from Ch 6); likewise <> and !=. Arithmetic on signed integers uses two's-complement wrap-around on overflow — there are no runtime checks.

Short-circuit evaluation

AND and OR short-circuit: the right operand is not evaluated when the left already determines the result. XOR evaluates both operands, since both are always needed.

IF p <> 0 AND p.value > 0 ...    { p.value never read when p = 0 }

(Note: TINY 2.1 has no record syntax — the example is illustrative of the ordering guarantee only.)

Sample program

PROGRAM hello;

VAR LONG i;
VAR LONG n;

FUNCTION LONG square(LONG x);
BEGIN
    RETURN x * x
END;

BEGIN
    WRITELN("Hello from TINY 2.1");
    n = 5;
    i = 1;
    WHILE i <= n
        WRITE(i, " squared is ", square(i));
        WRITELN();
        i = i + 1
    ENDWHILE;
    WRITELN("done.")
END.

Expected output:

Hello from TINY 2.1
1 squared is 1
2 squared is 4
3 squared is 9
4 squared is 16
5 squared is 25
done.

VM ISA specification

The v2 virtual machine is a classic stack machine with a separate call stack frame model. Each instruction is one opcode byte followed by zero or one 32-bit signed operand. Values on the operand stack are 32-bit signed integers; sub-word loads/stores sign-extend (or zero-extend for CHAR) on read and truncate on write.

Notation: [a b c ...] describes the stack top-down, so c is the topmost element. → separates the pre-state from the post-state.

Control flow

Memory

Arithmetic

Division by zero traps and halts the VM with an error message and the faulting instruction pointer.

Logical (bitwise, operating on full 32-bit values)

Because TINY 2.1 treats non-zero as true and zero as false, these double as logical operators for the straight-line (non-short-circuiting) cases. The parser emits jump-threaded code for AND/OR to implement short-circuit.

Relational (push 1 for true, 0 for false)

I/O

READ/READCH take a destination operand; the compiler encodes whether it refers to a global or a local via a type bit in the operand. String literals used by WRITE(...) and WRITELN(...) are emitted into a constant pool and printed with PRINTS.

Calling convention

Arguments are pushed left to right by the caller. CALL/CALLF saves the return address and jumps. The callee immediately executes ENTER M to reserve M local slots, then uses LOADL/STOREL at fixed offsets:

            high addresses
        +-----------------+
        |   param 1       |  local offset  -(N+1)
        |   param 2       |  local offset  -N
        |      ...        |
        |   param N       |  local offset  -2
        +-----------------+
        |  return address |
        +-----------------+
        |   saved FP      |  <-- caller's frame pointer
        +-----------------+
        |   local 1       |  local offset  0
        |   local 2       |  local offset  1
        |      ...        |
        |   local M       |  local offset  M-1
        +-----------------+  <-- SP on entry to body
            low addresses

LEAVE pops the M locals and restores FP. RET pops the return address and resumes the caller. RETV is identical to RET except that the topmost stack value is preserved across the frame teardown so the caller sees it as the function's result.

Testing

The project ships with four test suites totalling sixty-plus cases. All pass on the reference build (fpc 3.2.2 on macOS arm64).

Running everything:

make test        # rebuild + run all suites
./ci.sh          # same, used by continuous integration

Individual suites can be run directly:

cd crenshaw        && ./verify.sh
cd crenshaw/v2     && ./verify.sh
cd crenshaw/v2/adversarial && ./run.sh
cd crenshaw/v2/stress      && ./run.sh

All tests currently pass.

Known limitations

This is a pedagogical project, not a production language. The following are deliberately out of scope:

• No arrays, records, pointers, or floating point. The only types are the four integer widths.
• No strings as first-class values. String literals appear only as arguments to WRITE/WRITELN; you cannot assign them to variables, read them, or concatenate them.
• No nested procedures or functions. Every routine is declared at the top level of the program block.
• No forward declarations or mutual recursion. A routine can only call routines that have already been parsed.
• Single compilation unit. There is no IMPORT or module system at the TINY level; each source file is a standalone program.
• v1's 68000 assembly is not executed. There is no bundled emulator; verification inspects the emitted text only.
• Single-error recovery. The compiler halts on the first syntax or type error. There is no error recovery or "continue after error" mode.
• No optimisation. Bytecode is emitted naively; the VM makes no attempt at inlining, constant folding, or register-like caching.

History and references

• Jack Crenshaw's original tutorial lives at [https://compilers.iecc.com/crenshaw/](https://compilers.iecc.com/crenshaw/)) Sixteen installments, written between 1988 and 1995 and still one of the friendliest introductions to hand-written compilers in existence.
• Crenshaw targeted Turbo Pascal on DOS and emitted assembly for the Motorola 68000, which was then the dominant CPU in high-end embedded systems and workstations.
• This project ports the text to Free Pascal 3.2.2, keeping v1 as close to the original idioms as possible (one file per chapter, -Mfpc dialect, 68k output preserved for inspection) and retargeting v2 to a stack virtual machine so that the final TINY 2.1 language can actually execute its programs without an external assembler or emulator.
• The structure of v2 into separate Pascal units (tinytypes, scanner, symtab, codegen, vm, tiny2) is itself the worked example for Chapter 16, Unit Construction.