Tiny Language

A language with variables, arithmetic, conditionals and loops, built one stage at a time. Each chapter takes the output of the last: characters become tokens, tokens become a tree, the tree is walked, and then the same tree is compiled to bytecode for a stack machine. None of it needs a kernel, so all of it runs here.

1. A lexer is one pass with one character of lookahead. Whitespace disappears there, which is why no later stage has to think about it.
2. Operator precedence is not a table the parser consults. It is the shape of the call chain: one function per level, each calling the tighter one.
3. A tree-walking interpreter is a switch on the node kind that calls itself. That is the entire idea, and everything else is bookkeeping about names.
4. Compiling and interpreting differ in when the walk happens, not in what it computes. The same tree produces the same answer either way.

7 chapters.

• A LexerCharacters in, tokens out, with one character of lookahead and no backtracking.
• A ParserOne function per precedence level, each calling the tighter one.
• A Tree-Walking InterpreterEvaluate a node by evaluating its children. That is the whole idea.
• Functions and FramesA call needs somewhere to put its own variables, and a way to come back.
• A Bytecode CompilerThe same tree, walked once at compile time instead of once per execution.
• A Virtual MachineFetch, decode, execute. A loop over an array, with no tree in sight.
• A Calling ConventionWhere the arguments go, who cleans up, and how the machine finds its way back.