The idea: four small programs in a row
A compiler is not one big step. It is a chain of small programs, each turning one form of the program into the next. This page builds the smallest useful chain for arithmetic like 12 + 3 * 4: a lexer cuts the characters into tokens, a parser arranges the tokens into a syntax tree, a code generator flattens the tree into bytecode, and a virtual machine (VM) runs the bytecode.
Pick a program and press Lex, Parse, Compile and Run in order. A button builds any earlier phase that is missing at once, so you can also jump straight to Run. Orange marks what is being worked on; grey marks what has been used up.
1. Lexer: characters to tokens
The source is only a string of characters. The lexer (also called scanner or tokenizer) reads it left to right and groups the characters into tokens, the words of the language. Each token has a kind (NUM, PLUS, STAR, LPAR…) and its text. Spaces only separate words, so the lexer drops them.
The rule for where a token ends is maximal munch: take the longest run of characters that still forms a token. 12 is one NUM token, not 1 followed by 2. At the end the lexer adds an EOF token so the parser knows the input is over (Demo: 12 + 3 * 4 through all four phases). Real lexers are usually written from regular expressions, one per token kind, compiled into a finite automaton; see Regex to NFA to DFA.
2. Parser: tokens to a syntax tree
The parser checks that the tokens come in an order the language allows and builds a tree that shows the structure. The allowed orders are written as a grammar, here three rules:
expr → term (('+' | '-') term)*
term → factor (('*' | '/') factor)*
factor → NUMBER | '(' expr ')'A recursive-descent parser turns each rule into one function. expr() calls term(), term() calls factor(), and factor() calls expr() again when it sees (. That recursion is how nested parentheses work. The parser looks at one token at a time, the lookahead, to decide what to do next. The canvas shows the call stack of these functions growing and shrinking, with the rule each one is running lit up in the grammar.
Precedence and associativity come from the grammar
Nobody writes "multiply before adding" into the parser. It follows from the layering: expr joins terms with +, and each term is built completely, including its *, before expr sees the next +. So in 12 + 3 * 4 the * node ends up deeper in the tree and is computed first. Parentheses send the parser back to expr from inside a factor, so (12 + 3) * 4 gives the other tree (Demo: parentheses change the tree).
The loop in each rule makes operators of the same level left-associative: in 9 - 4 - 2, expr() builds 9 - 4, then sees the second - and makes the tree so far the left side of a new node. The result is (9 - 4) - 2 = 3, not 9 - (4 - 2) = 5 (Demo: 9 - 4 - 2, left associativity).
The syntax tree
The tree the parser builds is an abstract syntax tree (AST): it keeps only what matters for meaning. Spaces are gone, and so are parentheses, because the shape of the tree already says which operation comes first. Number nodes are leaves; operator nodes have a left and a right child. Every later phase works on this tree, never on the text again.
3. Code generation for a stack machine
The VM on this page is a stack machine: instructions take their inputs from an operand stack and push their result back. Generating code for it is one post-order walk of the tree: emit the code for the left child, then for the right child, then the instruction for the node itself. A number becomes PUSH n; an operator becomes ADD, SUB, MUL or DIV. When the operator's instruction runs, its two operands are exactly the two values on top of the stack. A PRINT at the end prints the result.
| instruction | stack before → after |
|---|---|
PUSH n | … → … n |
ADD / SUB / MUL / DIV | … a b → … (a op b) |
PRINT | … v → … (prints v) |
The output is a flat list with no tree and no parentheses. That is why stack bytecode is popular: the JVM, CPython, WebAssembly and the .NET CLR all use a stack machine for the same reason.
4. The VM runs the bytecode
The VM is a loop: fetch the instruction at the program counter (pc), do it, move pc to the next one. For 12 + 3 * 4 the stack goes [12], [12, 3], [12, 3, 4], then MUL pops 4 and 3 and pushes 12, giving [12, 12], then ADD leaves [24] and PRINT prints 24. The stack never holds more than the deepest part of the tree needs.
Which phase catches which error
Each phase knows only its own rules, so each one finds a different kind of mistake, and a later phase never runs if an earlier one failed.
| program | caught by | why |
|---|---|---|
2 @ 3 | lexer | no token starts with @ (Demo: lexer error) |
2 + * 3 | parser | every token is valid, but factor() needs a number or ( after + and finds * (Demo: syntax error) |
8 / (4 - 4) | VM, at run time | the program is well formed; the divisor is 0 only when it runs (Demo: run-time error) |
A real compiler adds a semantic analysis phase between parsing and code generation: undeclared names, wrong types, missing returns. An optimizing compiler might even fold 4 - 4 to 0 at compile time and warn about the division; this page's compiler does no folding, so the error waits for the VM.
The same chain in real compilers
javac scans and parses Java into a tree, checks it, and writes JVM bytecode; CPython parses Python into an AST and compiles it to bytecode for its own stack VM; Lua and many scripting languages do the same in a few thousand lines. The lexer and parser are often generated by tools (lex/flex and yacc/bison, ANTLR) from the token regexes and the grammar, but many production compilers (GCC, Clang, Go, V8) use hand-written recursive-descent parsers like the one here, because they give better error messages.
See also How a Java Program Is Compiled and Run for every javac phase on a real class file, Compiler vs Interpreter for why one would compile at all, and Regex to NFA to DFA for how a lexer can be built from regular expressions.
What the page leaves out
Variables, statements, functions and control flow (which need a symbol table, jumps and call frames), semantic analysis and types, error recovery (a real parser reports several errors instead of stopping at the first), operator-precedence and LR parsing, optimization, register allocation and machine code, and how a JIT turns hot bytecode into machine code.