Brainfxcker

Brainfuck has only eight instructions, acting on a tape of memory cells and a pointer. The language is trivial: all the interest is in the translation. It was the perfect excuse to understand assembly and the stages of a compiler, without getting lost in the grammar of a complex language.

The lexer only keeps the eight meaningful characters. The parser builds a tree in which each [ ] loop holds its own block. That tree is then flattened into intermediate instructions: ADD, MOVE, SET, OUTPUT, INPUT, LOOP_BEG, LOOP_END.

An optimisation pass merges repeated instructions (+++ becomes ADD 3, >> becomes MOVE 2) and spots reset loops such as [-]. The code generator finally writes NASM code: the 30,000-byte tape is reserved in .bss, the pointer lives in rbx, and input / output go straight through the read, write and exit system calls.

Instructions are stored in a hand-written “paged vector”: an array of 64-element pages that grows without ever moving the elements already stored. Since I work on a Mac, the compiler runs in a linux/amd64 Docker container to produce and run real x86-64 binaries.