Build a Language

Turn the text 2 + 3 * 4 into the number fourteen

Take the text 2 + 3 * 4. You know it is fourteen. A computer holding that text has nine characters and no opinion at all: no numbers in it, no plus sign, nothing that could be added to anything. There is a character whose code happens to be the one for the digit two, and there is a character usually drawn as a cross.

Getting from those nine characters to fourteen takes four moves, and every language ever built makes the same four. First, split the text into words. The part that does this is the tokeniser and the words it makes are called tokens. Second, arrange the tokens into a shape. That part is the parser and the shape it builds is called a tree. Third, work the shape out. That part is the evaluator. What comes out is the answer. Fourth, and only if the language compiles rather than interprets: turn the shape into instructions instead of working it out on the spot. That part is the compiler. Four names for four jobs. This course builds them in that order, so if a name means nothing to you yet, it will by the step that builds it.

Break a line of characters into tokens

The first stage has one job: turn a run of characters into a list of tokens. A token is a small piece with a type attached. This is a number. This is a name. This is an operator. This is an opening bracket.

And this is a string: the word everyone uses for a piece of text written between quote marks, "hello", as opposed to a name or a number. It is called that because it is a string of characters threaded one after another. The tokeniser is where a string gets recognised and where its quote marks are removed, because it is the only stage that ever sees them.

It is also the only stage that ever sees a space, and it throws every one of them away.

Build the lexer

The tokeniser has a second name you will meet everywhere, including in the code below: a lexer, from the Greek word for a word. Same stage, same job, shorter to type, and the function that does it is almost always called lex. The whole lexer is one loop over a cursor. A cursor is a position in the text, like the blinking bar in a typing box, except that this one only ever moves forward. Look at the character the cursor is on. That single character decides what kind of token is starting. Then a small loop runs the cursor forward while the characters still belong to it.

Written out, with the awkward cases left in, it is about forty lines. Here is the shape of all of them. One word in it is worth knowing before you read it. continue jumps straight back to the top of the while. So each branch handles one kind of token completely and then hands control back, rather than nesting the next test inside itself.

function lex(src) {
  const tokens = [];
  let i = 0;

  while (i < src.length) {
    const c = src[i];

    if (c === ' ' || c === '\n') { i++; continue; }        // separators, kept by nobody

    if (c === '/' && src[i + 1] === '/') {                  // a comment, kept by nobody either
      while (i < src.length && src[i] !== '\n') i++;
      continue;
    }

    if (isDigit(c)) {                                       // a number
      const start = i;
      while (i < src.length && isDigit(src[i])) i++;
      tokens.push({ type: 'num', text: src.slice(start, i), from: start });
      continue;
    }

    if (isLetter(c)) {                                      // a name, or a keyword
      const start = i;
      while (i < src.length && isLetterOrDigit(src[i])) i++;
      const word = src.slice(start, i);
      tokens.push({ type: KEYWORDS[word] ? 'kw' : 'name', text: word, from: start });
      continue;
    }

    if (TWO_CHAR.includes(src.slice(i, i + 2))) {           // >= and friends, longest first
      tokens.push({ type: 'op', text: src.slice(i, i + 2), from: i });
      i += 2;
      continue;
    }

    tokens.push({ type: 'op', text: c, from: i });
    i++;
  }
  return tokens;
}

Write the rules that say which lines are legal

A grammar is a list of rules saying which sequences of tokens are allowed. Sprout's whole grammar fits on a postcard, and nothing outside it is a Sprout program.

Two words from those rules are worth having straight away, because everything from here uses them. An expression is anything that has a value: 4, price, 2 + 3 * 4, n > 0. Ask an expression what it is worth and there is an answer. A statement is a whole instruction, something the program does: let x = 1, print x, a whole if, a whole while. Ask a statement what it is worth and the question makes no sense. A Sprout program is a list of statements, and most statements have an expression somewhere inside them. That is why 2 + 3 on its own is refused: it is a perfectly good expression and not a statement, an answer nobody asked for.

The notation is small, and five marks do all of the work in it. Anything in quotes is a token typed exactly as it appears. A bar means "or". Square brackets mean "optional". Curly braces mean "none or more of whatever sits between them", and a star after a single item means none or more of that one item. Round brackets group things so that a bar or a star covers all of them at once. A name on the left of an arrow can be used on the right of any rule, including its own. That last part is how nine rules cover an endless number of programs.

Build a tree from a flat list of tokens

A tree here is a picture drawn upside down. At the top sits one box. Lines run down from it to the boxes under it, and lines run down from those to more boxes, for as long as you like. Each box is a node. The single node at the top is the root. A node with lines going down from it is the parent of the nodes at the other end, and those are its children. A node with nothing at all underneath it is a leaf. In Sprout every leaf is a number or a name, because those are the only things that need nothing else worked out first. How far down a node sits is its depth: the root is at depth nought, its children at depth one, and so on.

The parser reads the token list once, left to right, and builds a tree out of it. The cursor never goes backwards.

Nodes get made from the bottom up, which has a consequence worth holding on to: the last node made is always the root, because a parent cannot be built until it has children to hold.

Make 2 + 3 * 4 come out fourteen, not twenty

2 + 3 * 4 is fourteen. Nothing in the tokens says so. The rule that settles it has a name: precedence. An operator with higher precedence takes hold of its neighbours before a lower one gets near them, and people also say it binds tighter. So 3 * 4 is grabbed as one lump, and the plus only ever sees the twelve. Multiply and divide bind tighter than plus and minus, in Sprout and in nearly every language and in the arithmetic you already do without thinking about it. The token list is identical whichever answer you want and the difference is entirely which node ends up above which.

A parser with one level of rules, one function taking every operator as equally important, reads left to right and confidently produces twenty. Splitting those rules into levels, one per tightness, with multiply on a tighter level than add, produces fourteen without one line of special-case code.

Write one function per rule, and let them call each other

One function per rule. parseExpr calls parseSum, which calls parseTerm, which calls parseFactor. And parseFactor, the moment it meets an opening bracket, calls parseExpr again.

That last call is what makes it recursive, and it is why brackets nest as deeply as you like without a single line of code anywhere about nesting.

function parseSum() {                       // sum → term { ( '+' | '-' ) term }
  let left = parseTerm();
  while (at('+') || at('-')) {
    const op = next();
    const right = parseTerm();
    left = { type: 'Bin', op: op.text, left, right };
  }
  return left;
}

function parseTerm() {                      // term → factor { ( '*' | '/' | '%' ) factor }
  let left = parseFactor();
  while (at('*') || at('/') || at('%')) {
    const op = next();
    const right = parseFactor();
    left = { type: 'Bin', op: op.text, left, right };
  }
  return left;
}

function parseFactor() {                    // factor → NUMBER | NAME | '(' expr ')'
  const t = peek();
  if (t.type === 'num')  { next(); return { type: 'Num', value: Number(t.text) }; }
  if (t.type === 'name') { next(); return { type: 'Var', name: t.text }; }
  if (t.text === '(') {
    next();                                 // step past the bracket, then start again at the top
    const inner = parseExpr();
    expect(')');
    return inner;
  }
  fail('expected a number, a name, or an opening bracket');
}

Something has to remember where each of those calls had got to. When parseSum calls parseTerm, parseSum is not finished: it is waiting, and when the answer comes back it has to carry on from the exact line it stopped on. So every call that is in progress gets a small note to itself, saying which function it is and how far through it has got. That note is called a frame. Frames pile up newest on top, and the pile is the call stack. The frame on top is the one actually running. Everything under it is a call that is waiting for an answer. When a function returns, its frame comes off and the one underneath carries on. Step 12 uses the very same stack for Sprout's own functions. Here it belongs to the parser.

Point at the exact character that caused an error

Every node kept the character positions it was built from. Two small numbers per node, costing almost nothing, and they buy a surprising amount.

They are why a compiler can say line 4, column 12. Why an editor can highlight the whole expression under your cursor when you double-click it. Why a debugger can show you which line you are stopped on. All of that is two integers that somebody remembered to keep.

Walk the tree and get an answer out

To find out what a tree is worth, ask the root. It cannot answer without its children, so it asks them, and they ask theirs, until something is asked that already knows the answer: a number.

Then the values come back up, one per node, until the root is holding the only one left.

function evalNode(node, env) {
  if (node.type === 'Num') return node.value;
  if (node.type === 'Var') return lookUp(env, node.name);

  if (node.type === 'Bin') {
    const a = evalNode(node.left, env);      // ask the left child
    const b = evalNode(node.right, env);     // ask the right child
    if (node.op === '+') return a + b;       // then do one small thing
    if (node.op === '-') return a - b;
    if (node.op === '*') return a * b;
    if (node.op === '/') return a / b;
  }
  fail('no rule for a ' + node.type + ' node');
}

One thing in there is borrowed from the next step and can be taken on trust for now. env is where the variables live: every name that is currently in reach, with the value it is holding. lookUp(env, name) fetches one of them, or stops with an error if nothing is called that. Step 10 is about nothing else and pulls it apart properly. For this step, read those two lines as "a number already knows its own value, and a name has to be looked up somewhere". The other nine lines are the whole idea. They need nothing you have not got.

Give a value a name, and decide where the name lives

A variable is a name and a box. The evaluator needs somewhere to keep those pairs, and that somewhere has a name: an environment.

One environment is not enough, because two parts of a program may want the same name for different things. A pair of curly braces on their own, { ... }, is a block. Every block gets an environment of its own: empty when the block opens, thrown away when it closes. The stretch of program in which a particular variable can be seen is that variable's scope, and scope is the word everybody uses. An environment is the box; a scope is the reach. So environments come in chains: the block's, then whatever that block sits inside, out to the outermost one of all. That outermost one is the global scope, because every part of the program can see it. A lookup starts at the innermost environment and walks outwards until it finds the name, or runs out and reports that nothing is called that.

Add if and while, and turn a calculator into a language

Two node types and about ten lines of evaluator between them, and they are the difference between a calculator and a language.

The one thing worth watching is that while works out its condition again at the top of every pass. Everywhere else in the tree, a node is visited once. Here the same nodes are visited over and over, and that is where all the running time in any program goes.

Call a function, and watch the frames stack up

A call has to remember two things: the values of its own parameters, and where to carry on once it finishes. Both of them live in a frame, and frames stack up.

Calling the same function twice makes two frames with two separate copies of everything, which is what makes a function reusable, and what makes it possible for a function to call itself without the two calls treading on each other.

Compile it once instead of walking the tree every time

Walking the tree works. It also asks the same questions over and over: what kind of node is this, where does this name live, which child comes first. Every one of those answers was already fixed when the tree was built, and none of them changes between one run and the next.

A compiler answers them once and writes down what to do. What it writes is a flat list of tiny instructions, and running that list needs a machine far simpler than a tree walker. The list has a name you will see everywhere: bytecode. A byte is the small fixed-size lump that computers count memory in. The name stuck because in the early systems each instruction was written down as exactly one byte: one number standing for ADD, a different number standing for PUSH. Sprout does not bother squeezing its instructions down to numbers, and the word is used anyway, for any list of instructions meant to be run by a machine that is itself a program rather than a chip.

Sprout's machine has about twenty instructions and two piles. The first is the value stack: a pile of values where the only place you may add one or take one is the top. PUSH 3 drops a three on the top. ADD lifts the top two off, adds them, and drops the single answer back. No instruction ever says where its inputs are, because the answer is always "the top", and a machine built that way is called a stack machine. The second pile is the frames from Step 12, unchanged. And the instructions themselves are kept in chunks: one chunk per function, plus one called main for everything outside any function. That is why some of the labs below have a row of chunk buttons above the listing.

Run the language you built, end to end

All of it is here now. Characters in at one end, an answer out at the other, and five places along the way where you can stop and look at what is being carried.

What follows is the whole pipeline in one view, and then a piece of the language that was left unfinished on purpose, waiting for you.

Checkpoint: what the core language can do

• Turn text into tokens, and say why keeping positions matters more than it looks.
• Read a grammar, and tell a syntax error from an error about meaning.
• Write a recursive-descent parser, and place an operator at the right precedence by choosing which function calls which.
• Walk a tree to work out what a program means, with variables, scopes, conditions, loops and functions.
• Say what a call frame holds, and why recursion needs a fresh one every call.
• Compile a tree into bytecode and run it on a stack machine, one instruction at a time.
• Add an operator to a language, and know which stages you have to touch to do it.

Connections from the core pipeline

• Reading the Machine's Mind. The last stage again, on a real processor: numbered registers instead of a value stack, and instructions that a chip carries out rather than a loop in JavaScript. The bytecode you just emitted is the halfway house between the two.
• Build a Query Engine. A database takes text, tokenises it, parses it into a tree and runs the tree. Same four stages, and then a fifth one that is unique to databases: choosing between several correct ways to answer the same question.
• Computability and Complexity. The halting problem from Step 11, properly: why no program can look at another program and say whether it stops, and what else follows from that once you accept it.

Write down what every program is allowed to mean

The evaluator gives Sprout a meaning, but its JavaScript body is not a specification. A language specification describes observable behaviour: results, printed output, errors and effects. Two implementations conform when every accepted program has the same required observations.

Small-step semantics writes one legal machine step at a time. Big-step semantics relates a program and starting state directly to a result. Either style must settle details such as evaluation order, numeric overflow, short-circuit conditions and whether an error happens before or after an effect.

Resolve each name, then check each operation

Name resolution connects every use such as score to one declaration. Do this before type checking. Text equality is not enough: two declarations can have the same spelling in different scopes, while an imported name may be renamed locally.

A type checker assigns a type to each expression and verifies operations. The rule for addition may accept two numbers and produce a number. A conditional needs a Boolean condition and compatible branch results. Inference fills types only when the constraints determine one answer.

Keep captured values without keeping the whole call stack

A closure is executable code plus the environment needed by its free variables. If a function returned from makeCounter uses count, that binding must outlive the call that created it. Capture the needed binding, not an accidental copy of every local variable.

Records group named fields. Modules group declarations behind an exported interface. The compiler can check each module separately when an interface records the types and identities that other modules may use.

Trace which heap objects are still reachable

Call frames usually live on a stack because they leave in reverse order. Closures, records and growing collections can outlive one call, so their storage lives on a heap. A value representation must distinguish numbers, Booleans and references, often with a tag beside the stored bits.

A tracing collector starts from roots such as globals and live frames, follows references, marks every reachable object and reclaims the rest. Reference counting reclaims promptly but needs help with cycles. Ownership systems try to prove lifetimes before running. Each choice changes pauses, throughput and complexity.

Lower structured code into blocks and explicit edges

An intermediate representation sits between the language and its targets. A control-flow graph divides instructions into basic blocks: execution enters at the top, leaves at the bottom and does not branch in the middle. Edges show every possible next block.

Static single assignment form gives each temporary value one definition. Where control-flow paths join, a phi operation selects the value that arrived on the executed edge. Dominators and use-definition links make questions such as “which definition can reach this use?” mechanical.

Change the program without changing its promised behaviour

Constant folding replaces a known expression such as 3 * 4 with 12. Dead-code elimination removes an instruction whose result and effects are unused. Common-subexpression elimination reuses a prior result only when intervening operations cannot change what it reads.

An optimisation is correct when the transformed program refines the original semantics. Integer overflow, floating-point NaN, exceptions, volatile access and aliases can make an algebraic rewrite invalid. Measure real workloads too: larger code can lose instruction-cache time even when it executes fewer operations.

Keep one language while changing the machine underneath

A backend lowers IR into a target's instructions. Ahead-of-time compilation writes an object before the program runs. A just-in-time compiler produces code during execution and can specialise from measurements. WebAssembly provides a portable validated instruction format; native code exposes more target detail.

A calling convention says where arguments, return values and saved registers go. Object files carry code, data, symbols and relocations. A linker resolves symbols and lays out the result. The application binary interface also fixes sizes, alignment and ownership rules across a compiled boundary.

Keep useful answers while the program is half typed

An editor sees incomplete text most of the time. Error recovery inserts or skips a bounded piece so the parser can continue and produce a partial tree. Incremental parsing reuses unaffected parts after an edit. Incremental name and type analysis should invalidate facts that depend on the changed declaration, not everything.

A language server separates language knowledge from one editor. It publishes diagnostics and answers completion, hover, definition, references and rename requests. A correct rename follows symbol identities; a text replacement can alter comments, unrelated scopes or a different exported symbol.

Specify what concurrent programs may observe

Concurrency adds more than a task API. The language must say which operations are atomic, when writes become visible and which orderings a program may rely on. Without those rules, a compiler optimisation and a processor can each reorder operations in ways that surprise source-level reasoning.

A happens-before relation orders synchronization events. If two conflicting accesses have no required order and at least one writes, the program has a data race under many memory models. Languages may forbid that case, define limited outcomes or provide atomics with explicit ordering.

Give untrusted programs specific powers and firm budgets

A sandbox starts with no ambient authority. The host supplies explicit capabilities such as reading one directory or calling one service. Validate arguments at that boundary. A safe bytecode verifier also checks instruction targets, stack effects and types before execution.

Time is not the only resource. Limit instructions, call depth, heap bytes, output, open handles and host-call rates. Cancellation must reach long host operations. Isolation in another process or WebAssembly instance adds a boundary when one runtime bug must not expose the host.

Evolve packages without changing what old code means

A package needs an identity, version and dependency graph. A module name inside a package is not globally unique. Locking exact versions makes a build repeatable; a compatibility policy tells maintainers what an update may change. Public syntax, types, effects and data formats all form part of a contract.

A foreign-function interface crosses representation and ownership rules. Both sides must agree on calling convention, string encoding, layout, error transfer and who frees memory. Wrap that boundary in a small adapter and test it from both languages.

Constrain generated code, then run the ordinary gates

In 2026, a model can draft a grammar rule, compiler pass, test or migration, but plausible text is not a language implementation. Grammar-constrained decoding can restrict the token sequences it emits. Structured output schemas can require fields. Neither proves that names resolve, types check, effects are permitted or the transformation preserves behaviour.

Use compiler stages as a verification pipeline: parse the output, resolve and type it, check requested capabilities, run focused tests, compare transformed programs and review the diff. Feed precise diagnostics back for another attempt. Keep the model outside release authority and record the accepted evidence. The Software Construction patch-review lesson supplies the repository scope and authority checks around these language-specific gates.