A Practical Guide to Writing a Programming Language

This is the practical guide I wish I had when I started building a programming language.

I am not going to cover the history of compilers, every tool you could use, or every valid way to implement a language. Instead, I want to show one complete approach at a high level: how source text becomes a program your machine can execute, what each stage contributes, and where the important design decisions actually live.

The implementation will be a bytecode interpreter with explicit AST and IR stages, similar to the architecture used by elf. The examples use a small pseudo-C language, but the ideas are not tied to C. You should be able to follow along in whatever implementation language you prefer.

The goal is not to hand you a finished language. It is to give you a mental model strong enough to build one yourself.

Start with a small language

Before writing a lexer or designing bytecode, decide what the smallest useful version of the language looks like.

We will use a dynamically typed scripting language with familiar C-like control flow. A declaration looks like this:

i := 0

A function looks like this:

add := fun(a, b) {
	ret a + b
}

Conditionals and loops use ? before their body:

if i == 10 ? {
	print("ten")
}

while i < 10 ? {
	i += 1
}

That is enough syntax to begin. The language can grow later, but our first job is to make one small program travel through the entire implementation:

left := 20
right := 22
answer := left + right
print(answer)

This tiny program already requires literals, identifiers, declarations, addition, function calls, and a way for the language to call native code. More importantly, it gives every stage of the implementation something concrete to process.

Reduce the problem to a pipeline

At the broadest level, what we want is simple:

source text -> executable instructions -> behavior

For our language, the executable instructions will be bytecode. Everything in between exists to make the translation from source to bytecode understandable and manageable.

We will use this pipeline:

source
    -> tokens
    -> abstract syntax tree (AST)
    -> intermediate representation (IR)
    -> bytecode
    -> virtual machine (VM)

These stages are not laws. A tree-walk interpreter can execute the AST directly. A small bytecode compiler can generate bytecode from the AST without creating a separate IR. A native compiler may continue lowering until it reaches machine code for a real processor.

The value of explicit stages is that each one answers a different question:

The lexer asks: what pieces of text are present?
The parser asks: how are those pieces structured?
Lowering asks: what does that structure mean in simpler operational terms?
The bytecode generator asks: which instructions express those operations?
The VM asks: what happens when those instructions execute?

When a program behaves incorrectly, these boundaries give you places to look. You can print the tokens, inspect the AST, inspect the IR, disassemble the bytecode, and finally trace the VM. That is much easier than debugging one large function that tries to understand and execute source code at the same time.

Understand the destination: bytecode

Bytecode is an instruction set for a machine that exists in software. You design the instructions, and you write the virtual machine that executes them.

For example, this sequence:

left := 20
right := 22
answer := (left + right) * 10

might eventually become something resembling the following. Assume the compiler has assigned left, right, and answer to slots 0, 1, and 2, and uses slot 3 as temporary storage:

LOAD_CONSTANT   slot0, 20
LOAD_CONSTANT   slot1, 22
ADD             slot2, slot0, slot1
LOAD_CONSTANT   slot3, 10
MULTIPLY        slot2, slot2, slot3

The exact instructions depend on your execution model. A stack-based VM would push operands onto a stack and let ADD pop them. A slot-based VM, like elf's, names the input and output slots directly. Neither model is universally better; they organize the same work differently.

You are also free to choose how broad or specialized the instruction set is. You could theoretically invent one instruction for every source-level pattern, but that quickly couples the VM to the syntax of the language. A small set of general operations is usually easier to reason about at the beginning.

Some processors and VMs do provide compound operations. A multiply-add instruction, for example, represents a * b + c. That is a legitimate design choice when the operation is common or has useful semantics, but (a + b) * 10 is still an addition followed by a multiplication. The instruction set must preserve what the program actually means.

Where dynamic typing changes the work

In C, this program declares the types of its values:

int a = 20;
int b = 22;
int c = a + b;

The compiler knows that the addition is an integer addition and can emit an appropriate machine instruction.

In our language, values are dynamically typed:

a := 20
b := 22
c := a + b

The compiler can see that these particular literals are integers, but it cannot generally assume that every value reaching an ADD instruction will be one. Variables may be reassigned, values may arrive through function parameters, and different types may define different addition behavior.

The VM therefore needs to inspect the runtime tags of the operands and choose the correct operation. It may add two integers, combine an integer and a floating-point number, concatenate strings, or reject the operands with a runtime error.

More analysis or specialized bytecode can move some of that work back into the compiler. That is an optimization we can consider later. For now, a general ADD instruction keeps the compiler simple and makes the runtime semantics explicit.

This leads to a useful way of thinking about language implementation:

language
    compilation
        understand and translate the program
    runtime
        represent values and execute the translation

Static analysis can settle more questions during compilation. Dynamic behavior leaves more questions for the runtime. The complexity does not disappear; your design determines where it lives.

Turn characters into tokens

The lexer is the first concrete stage. It walks through the source text and groups characters into meaningful units called tokens.

Given this source:

answer := left + 22

the lexer might produce:

IDENTIFIER("answer")
DECLARE
IDENTIFIER("left")
PLUS
INTEGER(22)
END_OF_FILE

A token normally records at least its kind and the part of the source it came from. It should also retain a source location. Line numbers, columns, or byte offsets may feel unnecessary while valid programs are your only concern, but they become essential as soon as you need to report a useful error.

The lexer does not have to build one large token array. elf produces tokens on demand, and its parser keeps the current token, the next token, and the previously consumed token. A token array is also perfectly reasonable. What matters is that tokenization has a clear interface and can be tested separately from parsing.

Before moving on, make the lexer print its output. If the token stream is wrong, the parser cannot repair it.

Turn tokens into structure

The parser consumes tokens and determines their grammatical structure. Its usual output is an abstract syntax tree, or AST.

Consider this expression:

left + right * 10

It is not merely a flat sequence of five tokens. Multiplication has higher precedence than addition, so the structure is:

Add
|- Identifier(left)
`- Multiply
   |- Identifier(right)
   `- Integer(10)

That hierarchy is what preserves the meaning of the expression.

For a small language, a hand-written recursive-descent parser is a good place to start. Statements, blocks, calls, and primary expressions can each have a dedicated parsing function. Binary operators can use precedence climbing or a Pratt parser so that precedence and associativity remain explicit.

Syntax must make one interpretation possible

Language design and parser design meet at ambiguity. Adding a convenient piece of syntax can create more than one plausible interpretation of the same token stream.

Suppose a language uses a leading . as shorthand for an implicit receiver:

.field = 1

Now consider:

value := object
.field = 1

If newlines are insignificant and . is also the postfix field-access operator, should this mean two statements, or should it continue the previous expression as object.field? The implementation cannot answer that from taste. The grammar needs a rule: perhaps newlines terminate statements, perhaps a leading dot is forbidden, or perhaps whitespace is significant in this one context.

Not every invalid program is grammatically ambiguous, and not every language rule belongs in the parser. Name lookup, scope, and type rules are usually handled later. The practical point is simply that syntax is not decoration. New syntax has to coexist with every syntax rule already in the language.

Represent the AST

An AST is a tree of syntactic elements. A simplified pseudo-C representation might look like this:

AstNode :: struct {
    site: SourceSite
    kind: AstKind

    union {
        identifier: Atom
        integer: Int
        number: Num

        declaration: struct {
            name: Ast
            expression: Ast
        }

        while_statement: struct {
            condition: Ast
            body: Ast
        }

        function: struct {
            parameters: Ast[]
            body: Ast
        }

        call: struct {
            expression: Ast
            arguments: Ast[]
        }

        binary: struct {
            left: Ast
            right: Ast
        }

        unary: Ast
    }
}

This uses a discriminated union. Every node has a kind, and that kind tells us which part of the union is valid. An AST_INTEGER node uses the integer field; an AST_BINARY node uses the left and right fields. In C, this gives every node one predictable representation without requiring a separate allocation shape or virtual interface for each kind.

It is an implementation choice, not a requirement of language design. In a language with algebraic data types or classes, a different representation may be more natural.

There is also a choice in how much syntax the AST preserves. A declaration could store its name as a string, but representing that identifier as its own AST node automatically preserves its source location and keeps syntax handling consistent. On the other hand, punctuation such as commas usually does not need to survive parsing at all. The tree is abstract because it records meaningful structure rather than every token in the source file.

A useful rule is to retain anything later stages need for meaning, diagnostics, or tooling. Discard the rest deliberately.

Lower the AST into IR

The AST describes the program largely as the programmer wrote it. The next step is to turn it into a smaller and more explicit representation that is easier to compile. This is the intermediate representation, or IR.

Our language is simple enough that we could generate bytecode directly from the AST. The separate IR is still useful because it gives semantic work a home. In elf, lowering resolves local and global names, tracks lexical scopes, discovers closure captures, validates assignments, and converts structured control flow into explicit labels and jumps.

For example, an AST might represent a loop like this:

While
|- Condition
`- Body

The lowered form can make its control flow explicit:

loop_start:
    jump_if_false condition, loop_end
    body
    jump loop_start
loop_end:

The bytecode generator no longer needs to understand the full meaning of a while statement. It only needs to emit labels, conditional jumps, and unconditional jumps. Other source constructs can lower to the same small set of operations.

Different IRs are useful for different jobs. An optimizing native compiler may use several of them, each exposing a property needed by a particular analysis. For this language, we only need a representation that makes name resolution, control flow, and bytecode generation straightforward.

The important lesson is not that every language must have an IR. It is that a new representation should earn its place by simplifying the stages around it. If direct AST-to-bytecode generation remains clear, use it. When semantic work starts leaking into the parser and backend, an explicit lowering stage gives that work a boundary.

What we have built so far

We now have a path from text to a representation close to executable code:

source -> tokens -> AST -> IR

Each boundary has a concrete test:

Print the token stream and compare it with the source.
Print the AST and verify precedence and statement structure.
Print the IR and verify name resolution and control flow.
Feed invalid programs into each stage and verify that errors point back to the correct source location.

The next half of the implementation takes that IR and turns it into something the runtime can execute. That is where the language stops being a collection of representations and becomes a running system.

Generate a bytecode module

The bytecode generator walks the IR and emits instructions. A literal becomes a constant load. An arithmetic expression becomes an arithmetic instruction. A local reference becomes a slot reference. A label becomes a bytecode position, and a jump becomes a relative offset to that position.

The output needs more than one flat instruction array. A practical bytecode module will normally contain:

the instruction stream;
constant pools for numbers and strings;
metadata for every function;
the number of slots required by each function; and
source maps connecting instructions to the original program.

Constant pools keep larger values out of the instruction itself. An instruction can say "load integer constant 3," and the module owns the actual 64-bit value stored at index 3. Function metadata tells the VM where the function's instructions begin, how many arguments it expects, how many values it captures, and how much frame storage it needs.

Control flow requires a small complication. When you emit a forward jump, its destination may not exist yet. Emit a placeholder, remember which label it targets, and patch the instruction after the complete function has been generated. This is simpler than trying to predict instruction positions while the function is still changing.

The slot allocator can also remain simple. Give parameters and locals stable slots. Allocate temporary slots while generating an expression, then release those temporaries when the expression is complete. Record the highest slot ever used; that number becomes the function's required frame size.

Before writing the VM, build a disassembler. If you cannot read the output of your compiler, every runtime failure becomes harder to separate from a code generation failure.

Execute the bytecode

The virtual machine is a loop around an instruction pointer:

while running:
    instruction = code[instruction_pointer]
    instruction_pointer += 1

    switch instruction.opcode:
        case LOAD_CONSTANT:
            slots[x] = constants[y]

        case ADD:
            slots[x] = add(slots[y], slots[z])

        case JUMP:
            instruction_pointer += instruction.offset

        case RETURN:
            leave_current_frame()

That loop is the heart of a bytecode interpreter. Most of the runtime consists of making each operation obey the language's rules.

A slot-based VM gives every active function an array of values. The operands in an instruction are indices relative to the current function frame. An ADD instruction therefore reads two values from the frame, performs the dynamic addition, and writes the result into another slot.

Do not optimize dispatch first. A large switch is easy to inspect in a debugger and is entirely adequate while the semantics are still changing. The first goal is not to make dispatch clever. It is to make every instruction correct and to make failures point back to the source that produced them.

Represent values at runtime

The VM needs one value representation that can hold every value visible to the language. A straightforward implementation uses a tagged union:

Value:
    type: integer | number | string | table | function | closure | nil
    payload:
        integer
        number
        object pointer
        native function pointer

The tag tells the runtime which part of the payload is valid. Two integer values can be added directly. An integer and a floating-point number may be promoted to a common representation. A string may trigger concatenation. Other combinations should produce a clear runtime error.

This is where the semantics discussed earlier become real. Dynamic typing does not mean that values have no types. It means those types are carried by runtime values rather than proven for every expression before execution.

Keep the first representation boring. A tagged union is larger than the most compressed alternatives, but it is easy to inspect and difficult to misunderstand. NaN boxing, pointer tagging, and specialized instructions can come later if measurements show that value size or dispatch is an actual problem.

Add calls and closures

Function calls introduce a second piece of state: the call frame. A frame needs to identify the function being executed, its current instruction, its slot storage, and any values captured from an enclosing function.

Calling a bytecode function roughly means:

Find the function metadata.
Create a frame large enough for its parameters, locals, and temporaries.
Copy or place arguments into the parameter slots.
Begin executing at the function's first instruction.
Copy return values back to the caller and restore the previous frame.

A closure is a function paired with values from the scope where that function was created. Name resolution during lowering should already have discovered which values must be captured. The runtime's job is to store those values on the closure and make them available to the frame when the closure is called.

Native functions should fit through the same language-level calling model. The callee may be bytecode or a C function, but the script should still pass arguments and receive results in one predictable way. This is the beginning of the embedding boundary.

Design the host boundary deliberately

An embedded language becomes useful when the host application can exchange data and behavior with it. At minimum, a native API should let the host:

create and destroy a language state;
compile or load source;
publish native functions and data;
call script functions;
inspect returned values; and
retrieve useful diagnostics when something fails.

elf uses a stack API for this boundary. The host pushes values, reads values by index, creates tables, installs globals, and calls either native functions or bytecode closures. The stack also gives the garbage collector a visible set of host-owned roots without exposing internal object pointers.

The exact API matters less than its ownership rules. If a string pointer is returned, how long is it valid? If the host keeps a table after popping it from the stack, what prevents collection? If compilation fails, where does the error live and how long does its message remain valid? These questions are part of the language design because every embedding application will depend on their answers.

Decide what owns memory

Language implementations create objects with very different lifetimes. Tokens, AST nodes, and IR nodes are needed only while compiling. Bytecode modules must survive as long as their functions can execute. Runtime strings, tables, and closures may outlive the call that created them.

You do not need one allocation strategy for all three groups.

elf builds its parser, AST, IR, and bytecode-generation scratch data in temporary arenas that are discarded after compilation. The finalized module and its source live with the owning language state. Dynamic strings, tables, and closures use a synchronous mark-and-sweep garbage collector whose roots include the VM stack, host references, modules, and built-in tables.

That is not the only valid arrangement. Reference counting or explicit handles may fit another language better. The important part is to divide objects by lifetime before choosing the mechanism. Memory management becomes much easier when temporary compiler data is not forced through the same collector as live script objects.

Test every boundary

End-to-end programs prove that the stages cooperate, but small tests tell you which stage failed. Keep tests for each transformation:

source -> expected tokens
source -> expected AST
AST -> expected IR or resolution error
IR -> expected bytecode
bytecode -> expected runtime result
invalid source -> expected diagnostic and location

Every representation should have a printable form. Token dumps, AST printers, IR printers, bytecode disassembly, and instruction tracing are not cosmetic debug tools. They let you ask where the program first became different from what you intended.

When a bug appears, preserve the smallest program that reproduces it. Language features interact in ways that are easy to reintroduce later: closures inside loops, deferred work during returns, assignments through nested scopes, or a runtime error after several calls. The regression suite becomes the most precise record of the semantics your implementation actually supports.

Grow through complete programs

Once the 42 program works, add features in vertical slices. A useful order is:

comparisons and conditionals;
loops and assignment;
functions and returns;
strings and tables;
native functions and embedding;
lexical scope and closures; and
modules, diagnostics, and development tools.

The order should follow the job of your language. A configuration language may need tables before loops. A numerical language may need vectors before strings. The rule is to add one feature that enables a more representative program, then carry that feature through every affected stage before starting the next one.

Keep a real consumer beside the focused tests. Bob became that consumer for elf. Bob's scheduler and dependency engine are written in C, while its build descriptions are elf programs. That use exposed problems that isolated examples did not: nested data moving through the C API, module lifetime, native error boundaries, filesystem behavior, and whether the language remained pleasant once scripts became larger.

The consumer does not need to be ambitious. A configuration file, small game, build description, or command-line automation script is enough. Its purpose is to force individually working features to compose into something useful.

A practical build order

If you are starting today, this is enough of a plan:

Write three example programs and define their expected behavior.
Tokenize the smallest one and print the token stream.
Parse expressions and print the AST.
Lower names and control flow into an inspectable IR.
Generate obvious, unoptimized bytecode and disassemble it.
Execute constants and arithmetic in a switch-based VM.
Add variables, calls, and one native print function.
Preserve every failure as a focused regression test.

At that point the language will be tiny, but it will be real. Source text enters one end, defined behavior comes out the other, and every stage between them can be inspected independently.

Closing perspective

Building a language is not one mysterious compiler problem. It is a sequence of representations and transformations:

source -> tokens -> AST -> IR -> bytecode -> runtime behavior

Start with one complete program. Keep each stage explicit. Make every boundary printable and testable. Then let real usage decide what the next feature should be.

Your first language does not need a novel syntax, an optimizer, a JIT, or an ecosystem. It needs a small set of semantics that you understand from source text all the way to execution. Once that path works, everything else is an extension of the same process.

elf took this route and eventually grew into the scripting frontend for a real build system. The implementation is still evolving, but its central lesson has remained stable: simplicity does not come from skipping stages. It comes from giving every necessary piece one clear job.