Regular readers (both of you) will have noticed a theme. This blog keeps coming back to programming languages and the machinery that runs them: a JIT in Julia, FORTH and FORTH again, FORTRAN, Lisp, Tiny BASIC, tail calls, Zig, and yet another JONESFORTH in WebAssembly. The grown-up way to study all this is to work through the dragon book from cover to cover. I barely scratched its scales. Somewhere around chapter 3 I fell into the rabbit hole that is regular expressions, a hole with only finitely many states that I still haven’t managed to climb out of. It’s the hole charted by the dragon’s more finite cousin, the Cinderella book.

2004

I told part of this story before. In 2004 I translated Ken Thompson’s 1968 paper, Regular Expression Search Algorithm, from IBM 7094 assembly to x86. Thompson’s grep didn’t interpret regular expressions. It compiled them to machine code on the fly, and the lists of states it juggled were lists of branch instructions into that code. Ken patiently answered my questions about AXC **,7. Russ Cox kindly hosted the result, a buggy little hack, and dutifully reported that “it runs for a very long time, making me think it is stuck in an infinite loop somewhere.” I was vaguely aware that something was off, but not bothered enough to chase it. I had a new Wall Street job, and hobby programming took a back seat.

Eighteen years later

In 2022 I started this blog and promptly started nerding out on FORTH. I wrote countless versions: in C, in Python bytecode, in Zig, in WebAssembly. Along the way I picked up a lot more x86 than I ever knew in 2004, with JONESFORTH as my reference.

Then I had an epiphany at work. I finally managed to prompt Claude with a measure of reproducible success. So I turned my attention back to x86.c. My first attempt, asking DeepSeek to find the bug, went nowhere because I wasn’t specific enough. What I needed was a proper minimal reproduction. It turned out to be embarrassingly minimal: a* (doh). I handed that to Claude Opus and, boom, it found two off-by-two errors that cancel out. ALTERN stored a subexpression’s entry point two bytes past the real one, and KLEENE read it back two bytes short. For a(b|c)*d, the only test I had enabled of course, the two errors cancelled perfectly. When * applies directly to a character, they don’t, and a* spins in an epsilon loop until the stack runs out. The fix brought back memories of the endless trial and error of 2004: nudge an offset, reassemble, segfault, repeat. I wouldn’t be surprised if one of those nudges is what introduced the second error.1

Emboldened, I suggested using x86 string instructions, which I had admired in JONESFORTH (its NEXT is just lodsl; jmp *(%eax)) and in sectorlisp. Yay for x86 code golf! Reading the next character used to take movb (%edx), %al; incl %edx. Now it is a single-byte lodsb.

Slowly, an old ambition resurfaced: merging those two niches. The matcher only ever emits four instructions: jmp, cmp, jnz, and call. FORTH already owns a code generator, so why bring a second one? regexp.f is the result. RE" is an IMMEDIATE word that pokes threaded code into whatever definition is being compiled. Where Thompson emitted 7094 transfer instructions and I emitted x86 calls, RE" emits BRANCH, 0BRANCH, EXIT, and a pair of helpers.

Put the two side by side and the family resemblance is striking. On the left is the 7094 code Thompson’s paper prints for a(b|c)*d. On the right is what SEE decompiles after : RE-PAT RE" a(b|c)*d" ;, exactly as the tests pin it down. SEE prints LIT as its bare value, and an XCALL operand as the word it lands in, which is RE-PAT itself.

IBM 7094, Thompson 1968regexp.f, SEE RE-PAT
 
(CNODE, NNODE, FAIL and XCHG are
 runtime routines outside CODE)
: RE-PAT RSP@ RE-RSP ! RE-START
RE-DONE? 0BRANCH ( 16 ) 0 EXIT
RE-PAT+20 >R
RE-THREAD DUP 0BRANCH ( 16 ) >R BRANCH ( -24 )
DROP RE-LOAD
a
 0  CODE  TRA  CODE+1
 1        TXL  FAIL,1,-'a'-1
 2        TXH  FAIL,1,-'a'
 3        TSX  NNODE,4
BRANCH ( 4 )
97 RE-CHAR?
0BRANCH ( 8 ) EXIT
(NNODE)
b
 4        TRA  CODE+16
 5        TXL  FAIL,1,-'b'-1
 6        TXH  FAIL,1,-'b'
 7        TSX  NNODE,4
BRANCH ( 108 )
98 RE-CHAR?
0BRANCH ( 8 ) EXIT
(NNODE)
c
 8        TRA  CODE+16
 9        TXL  FAIL,1,-'c'-1
10        TXH  FAIL,1,-'c'
11        TSX  NNODE,4
BRANCH ( 56 )
99 RE-CHAR?
0BRANCH ( 8 ) EXIT
(NNODE)
|
12        TRA  CODE+16
13        TSX  CNODE,4
14        TRA  CODE+9
15        TRA  CODE+5
BRANCH ( 20 )
XCALL RE-PAT
BRANCH ( -84 )
*
16        TSX  CNODE,4
17        TRA  CODE+13
XCALL RE-PAT BRANCH ( 20 )
XCALL RE-PAT BRANCH ( 4 )
·d
18        TRA  CODE+19
19        TXL  FAIL,1,-'d'-1
20        TXH  FAIL,1,-'d'
21        TSX  NNODE,4
BRANCH ( 4 )
100 RE-CHAR?
0BRANCH ( 8 ) EXIT
(NNODE)
·eof
22        TRA  FOUND
RE-ACCEPT ;

Row by row the correspondence is nearly one to one:

  • Out slots. Every block starts with a jump that is really the previous block’s exit. Thompson’s compiler back-patches it, and so does RE-PATCH. Look at the b row: Thompson’s TRA CODE+16 and my BRANCH ( 108 ) both send whatever follows a into the closure.
  • Character tests. Thompson’s TXL/TXH pair brackets the character held in index register 1 and jumps to FAIL on either side. 97 RE-CHAR? 0BRANCH ( 8 ) EXIT does the same thing, and EXIT is FAIL: both return to the next entry of the current list.
  • Successors. TSX NNODE,4 and (NNODE) both call a routine whose return address is the next state, which it files away on the next list.
  • Branching. CNODE and XCALL are mirror images. CNODE at x queues x+1 and carries on at x+2. XCALL runs its operand first and leaves its continuation on the return stack, which is the current list. The closure takes four cells instead of two because of the empty-string revision Thompson describes in the paper’s notes2, which is also what keeps a** from looping forever. XCALL is R> DUP @ SWAP 4+ >R >R ;, which is precisely call rel32: take the target from the cell that follows, push the cell after that as the return address, and let its own EXIT transfer control. Note that EXECUTE cannot stand in for it. The reason SEE prints the operand as RE-PAT is that the target is a cell in the middle of RE-PAT, not a word of its own: there is no code field for EXECUTE to jump through, and EXECUTE runs one word rather than setting IP and carrying on through the block.
  • Accepting. TRA FOUND becomes RE-ACCEPT.

What makes this possible is that a FORTH compiler is not a black box. It is a loop that reads a word and either executes it or appends it to the definition being compiled, depending on STATE. Everything else is ordinary words you can call or redefine:

  • : switches STATE to compiling, and [ and ] switch it back and forth in the middle of a definition. : '*' [ CHAR * ] LITERAL ; runs CHAR * while compiling, then LITERAL compiles the result as a constant. That is how regexp.f spells character constants.
  • An IMMEDIATE word runs even while STATE says “compile”. That is the hook. When the compiler meets RE" inside : RE-PAT RE" a(b|c)*d" ;, it doesn’t compile a call to RE". It runs it. RE" then reads the pattern straight off the input stream with KEY, so it gets to define its own little syntax, and runs all three of Thompson’s stages right there, in the middle of compiling RE-PAT.
  • The code generator is just ,, the same word the compiler uses to append a cell at HERE. HERE @ is Thompson’s pc. Inside a definition, ' quotes the next cell instead of executing it, so ' BRANCH , appends a BRANCH in the definition being built. That is FORTH’s answer to Thompson’s instruction('tra', ...).

Thompson needed an ALGOL procedure to assemble 7094 instruction words, and x86.c needed mprotect(PROT_EXEC) plus hand-encoded opcodes. In FORTH the dictionary is already executable, so the matcher RE" produces is an ordinary word. You can EXECUTE it, SEE it, and FORGET it like any other.

Thompson dismisses the first two stages of his compiler as “straightforward and not discussed”. The first inserts explicit concatenation operators, and the second is Dijkstra’s shunting yard, which converts the result to reverse Polish notation. They’re short enough to play with right here. sieve is the first stage. It turns each operator into its index in SYMBOLS, so comparing two operators compares their precedence, and it inserts · wherever one operand follows another:

postfix is the second stage, the shunting yard. Operands go straight to the output. Operators wait on a stack until one that binds no tighter arrives. The closing ) that sieve appends flushes whatever is left. The two editors share an interpreter, so run the one above first:

The third stage is the fun one. Below, regexp.f runs on top of jonesforth.f, inside a hand-crafted WebAssembly FORTH interpreter, tabulate.wast, in your browser. Typing a pattern really does compile it to threaded code and run it over the text.

Try:

The syntax is the one from the paper: concatenation, | for alternation, * for closure, (…) for grouping and \ to escape. Thompson’s machine reports the shortest match at the leftmost position, so (a|b)*a stops at the first a rather than running to the last one.

What happens when you click Match?

More than you’d think. JavaScript hands the pattern to a WebAssembly function, which is a FORTH interpreter. The interpreter compiles the pattern into a new FORTH word and executes it. That word pushes and pops the addresses of NFA states on FORTH’s two stacks, all inside machine code that V8’s TurboFan compiled from the WebAssembly. I wanted to see all of it at once, so I instrumented the interpreter’s inner loop and froze it halfway through Thompson’s own example, a(b|c)*d, matching abccbcccd. Nothing below is drawn from memory. It was measured in Node 24 (V8 13.6) on an Apple silicon Mac.

Every layer of the regexp.f demo, frozen halfway through matching Thompson's example regex against abccbcccd

The part that still delights me is the return stack. Thompson’s CLIST, the states still to try for the current character, is simply the return stack above the sentinel. RE-NLIST collects the states for the next one. When a state matches, (NNODE) pops its own return address and files it away, because the “return address” of that call is the next state. When a state fails, it just EXITs, and returning lands in the next pending thread. The whole NFA simulation is carried by FORTH’s calling convention.

Full circle

There’s a certain irony in all this. FORTH is famous for having almost no syntax. As I put it before, there is “no tokenizer, lexer, or syntax tree”, only words separated by spaces. Regular expressions, meanwhile, are the foundation of every lexer generator from Lex onward. The dragon book devotes a whole chapter to turning them into automata. So here is the language that never needed a lexer, compiling the very thing lexers are made of.

Twenty-two years after my first attempt, the journey comes full circle3: from Thompson’s 7094 to x86, from x86 to FORTH, and from FORTH back to something Ken would recognize, a regular expression compiled on the fly into code whose lists of states are just jumps into itself. Finally without the infinite loop.

  1. Confirming that fix meant reading compile()’s emitted bytes off PR #73’s Appendix B hex dump by hand, which is exactly as slow as it sounds, so cps.c (PR #110) recasts the same one pattern, a(b|c)*d, as ordinary, portable C instead, one function per operand, so a real compiler (clang -target i386-none-elf -O0 -fomit-frame-pointer -S) can confirm the shape instead of a human squinting at hex. It is continuation-passing style in the most literal sense: a character node never returns true or false, it either calls nnode(k) to schedule its continuation k against the next character or just returns, leaving no continuation to run. ALTERN and KLEENE each splice two continuations together by calling one for real and then __attribute__((musttail))-tail-jumping into the other, so both run against the same character without growing the stack — exactly the “every call already in tail position” discipline CPS depends on, and exactly the call/jmp pair x86.c’s bytes already encode. Asking an LLM to write and code-review that reconstruction is the same trick as asking Claude Opus to find the ALTERN/KLEENE bug in the first place: a nice demonstration that an LLM is as good at helping crack open a twenty-year-old hack and push it a little further as it is at writing new code from scratch. ↩

  2. jit.py, a Python port of x86.c that emits x86-64 or arm64 and calls it through ctypes, uses an alternative: Anne Brüggemann-Klein’s Star Normal Form (SNF) (doi:10.5555/896333). Instead of patching jumps while generating code, it first rewrites the pattern so that no * applies to anything that matches the empty string: e* becomes e'*, where e' is e without the empty string, so (a*b*)* becomes (a|b)*. With no empty loops left to break, the revision isn’t needed at all. ↩

  3. The cast of characters, in order of appearance:

    Date Topic Event
    15 Jan 1962 IBM 7094 IBM announces the 7094
    Jun 1968 Thompson “Regular Expression Search Algorithm” appears in CACM 11(6) (doi:10.1145/363347.363387)
    1968 FORTH Chuck Moore first calls his language FORTH, at Mohasco (Rather, Colburn & Moore, HOPL-II)
    May 1995 JavaScript Brendan Eich writes it at Netscape in ten days (Wirfs-Brock & Eich, HOPL IV)
    13 Sep 2007 JONESFORTH Richard W.M. Jones announces it on Lambda the Ultimate
    17 Jun 2015 WebAssembly Google, Microsoft, Mozilla and WebKit announce it

    ↩