Tiny Language

This section builds a language with variables, arithmetic, conditionals and loops, one stage at a time. Each chapter takes the output of the previous chapter. Characters become tokens, and tokens become a tree. An interpreter walks the tree. Then a compiler changes the same tree to bytecode for a stack machine. No part needs a kernel, so all of the parts run in this page.

1. A lexer is one pass with one character of lookahead. The lexer removes the whitespace, so no later stage must think about whitespace.
2. Operator precedence is not a table that the parser reads. Precedence is the shape of the call chain: one function for each level, and each function calls the next tighter level.
3. A tree-walking interpreter is a function that switches on the node kind and calls itself. All the other code is bookkeeping about names.
4. A compiler and an interpreter differ in when the walk occurs, not in what the walk computes. The same tree gives the same answer in the two cases.

7 chapters.

• A LexerThe lexer changes characters into tokens. It looks one character ahead and never moves back in the source.
• A ParserOne function for each precedence level. Each function calls the function for the next tighter level.
• A Tree-Walking InterpreterTo evaluate a node, evaluate its children and then combine the results.
• Functions and FramesA call needs a place for its own variables, and a way to return to the caller.
• A Bytecode CompilerThe compiler walks the same tree one time at compile time, not one time for each run.
• A Virtual MachineFetch, decode, execute. A loop over an array, with no tree.
• A Calling ConventionWhere the arguments go, which side removes them, and how the machine returns to the caller.