Dishon Oketch

Posted on Aug 31

Interpreters and Compilers: How Your Code Actually Becomes a Running Program

#programming #tutorial #beginners #computerscience

Every developer writes code that "just works" thousands of times without thinking about what happens between hitting save and seeing output on screen. This article pulls back that curtain. We're going to walk through, in real depth, how source code — plain text you typed — becomes a running program, covering lexing, parsing, abstract syntax trees, semantic analysis, and the actual difference between interpretation and compilation (including why that difference is far blurrier than most explanations make it sound).

This is one of those topics where understanding the fundamentals pays off across your entire career — it changes how you read error messages, how you reason about performance, and how you evaluate new languages and tools.

1. The Big Picture: Two Broad Strategies

At the highest level, there are two strategies for running code:

Compilation — translate the entire source program into another form (often machine code, but not always) before running it. The translation and the execution are separate steps.
Interpretation — read and execute the source program directly, translating and running it (roughly) simultaneously, statement by statement.

In practice, almost no real system is purely one or the other. Python "compiles" your source to bytecode before interpreting the bytecode. Java compiles to bytecode, then a JIT (Just-In-Time) compiler compiles hot paths of that bytecode to native machine code while the program runs. JavaScript engines like V8 do something similar. The clean binary of "compiled vs. interpreted" that gets taught early on is really a spectrum, and most production language runtimes today live somewhere in the middle.

But to understand any point on that spectrum, you need to understand the pipeline every one of these systems shares. Let's build it up stage by stage.

2. Stage One: Lexical Analysis (Lexing / Tokenizing)

The first thing that has to happen to your source code is the least glamorous: it gets chopped into pieces.

Source code, to a computer, starts as nothing more than a raw stream of characters:

let x = 5 + 3;

The lexer (also called a "tokenizer" or "scanner") reads this character stream and groups characters into meaningful chunks called tokens, discarding things that don't matter for meaning (whitespace, usually comments) along the way.

For the line above, a lexer would typically produce something like:

KEYWORD("let")
IDENTIFIER("x")
OPERATOR("=")
NUMBER(5)
OPERATOR("+")
NUMBER(3)
SEMICOLON

How Lexers Actually Work

Under the hood, a lexer is essentially a finite state machine. It reads character by character, and depending on the current character and its current "state," decides whether to keep accumulating characters into the current token, emit the current token and start a new one, or throw an error.

Here's a simplified conceptual lexer loop:

def tokenize(source):
    tokens = []
    i = 0
    while i < len(source):
        char = source[i]

        if char.isspace():
            i += 1
            continue

        if char.isdigit():
            start = i
            while i < len(source) and source[i].isdigit():
                i += 1
            tokens.append(("NUMBER", source[start:i]))
            continue

        if char.isalpha():
            start = i
            while i < len(source) and source[i].isalnum():
                i += 1
            word = source[start:i]
            if word in KEYWORDS:
                tokens.append(("KEYWORD", word))
            else:
                tokens.append(("IDENTIFIER", word))
            continue

        if char in OPERATORS:
            tokens.append(("OPERATOR", char))
            i += 1
            continue

        raise SyntaxError(f"Unexpected character: {char}")
    return tokens

This is deliberately simplified (real lexers handle multi-character operators like ==, string escape sequences, numeric literals with decimals/exponents, and more), but the core loop — "look at current character, decide what kind of token this is starting, consume characters until the token ends" — is genuinely how production lexers work, just with far more edge cases handled.

Regular Languages and Why Lexers Use Them

There's a deep theoretical reason lexers are structured this way: the set of valid tokens in most languages forms what's called a regular language — the same class of language that regular expressions can describe. This is why lexer-generator tools like lex/flex let you define tokens using regex-like patterns. Tokenizing doesn't require understanding nested structure (like matching parentheses) — that's the parser's job, which brings us to stage two.

3. Stage Two: Syntactic Analysis (Parsing)

Once you have a flat stream of tokens, the next job is to understand their structure — how they relate to each other grammatically. This is the parser's job, and its output is almost always an Abstract Syntax Tree (AST).

Why Tokens Alone Aren't Enough

Consider: 5 + 3 * 2. As a flat token stream, this doesn't tell you which operation happens first. You need to know that * binds tighter than + — that's grammatical/structural information, not something a lexer (which just identifies tokens) captures.

The parser's job is to take the flat token stream and build a tree that captures this structure:

This tree makes the order of operations explicit: to evaluate it, you'd evaluate the * subtree first (3 * 2 = 6), then the + (5 + 6 = 11). The shape of the tree encodes precedence and associativity — information that was implicit in the source text's grammar but needs to become explicit structure for anything downstream to use.

Grammars: The Rules Parsers Follow

Parsers are built around formal grammars, usually written in a notation like Backus-Naur Form (BNF). A tiny grammar for arithmetic expressions might look like:

expression → term (("+" | "-") term)*
term       → factor (("*" | "/") factor)*
factor     → NUMBER | "(" expression ")"

Read this as: "an expression is one or more terms separated by +/-; a term is one or more factors separated by *//; a factor is either a raw number or a parenthesized expression." Notice how this grammar encodes precedence structurally — because term is defined in terms of factor, and expression is defined in terms of term, multiplication naturally ends up "deeper" in the resulting tree than addition, which is exactly the nesting we want.

Recursive Descent Parsing

One of the most common (and most intuitive) parsing techniques is recursive descent — where you write one function per grammar rule, and those functions call each other following the grammar's structure.

def parse_expression(tokens):
    left = parse_term(tokens)
    while peek(tokens) in ('+', '-'):
        op = consume(tokens)
        right = parse_term(tokens)
        left = BinaryOp(op, left, right)
    return left

def parse_term(tokens):
    left = parse_factor(tokens)
    while peek(tokens) in ('*', '/'):
        op = consume(tokens)
        right = parse_factor(tokens)
        left = BinaryOp(op, left, right)
    return left

def parse_factor(tokens):
    if peek(tokens) == 'NUMBER':
        return Literal(consume(tokens))
    elif peek(tokens) == '(':
        consume(tokens)  # consume '('
        expr = parse_expression(tokens)
        consume(tokens)  # consume ')'
        return expr
    else:
        raise SyntaxError("Expected number or '('")

Notice the direct correspondence: parse_expression calls parse_term, which calls parse_factor, which can call back into parse_expression (for parenthesized sub-expressions) — this recursive structure directly mirrors the recursive grammar rules above. This is genuinely how many real, production parsers work (including, historically, parts of CPython's own parser and many hand-written language front-ends), because it's readable, debuggable, and maps almost line-for-line onto the grammar it implements.

Parser Generators: The Alternative Approach

Rather than hand-writing a recursive descent parser, many projects use parser generator tools (Yacc/Bison, ANTLR, tree-sitter) that take a formal grammar specification and generate parsing code automatically — often using different underlying algorithms like LALR or LL parsing, which use explicit state tables and stacks rather than recursive function calls. These are more mechanical and often faster to generate for complex grammars, but the resulting code is much less human-readable than a hand-written recursive descent parser.

4. Stage Three: The Abstract Syntax Tree (AST)

We've mentioned the AST already, but it's worth pausing on why it's called "abstract."

A concrete syntax tree would represent literally every token from the source, including things like parentheses and semicolons that only exist to guide parsing, not to convey meaning. An abstract syntax tree strips this away, keeping only the structure that actually matters for the program's meaning.

For example, (5 + 3) and 5 + 3 should produce the exact same AST — the parentheses were only there to influence parsing/precedence, and once the tree is built, that influence is already baked into the tree's shape. There's no need to remember "there were parentheses here" in the AST itself.

A typical AST node structure (using a simplified Python-like representation) might look like:

class BinaryOp:
    def __init__(self, operator, left, right):
        self.operator = operator
        self.left = left
        self.right = right

class Literal:
    def __init__(self, value):
        self.value = value

class Identifier:
    def __init__(self, name):
        self.name = name

class Assignment:
    def __init__(self, target, value):
        self.target = target
        self.value = value

The AST is the central data structure that essentially everything downstream — semantic analysis, optimization, code generation, or direct interpretation — operates on. It's the program, represented as data your own code can inspect and manipulate, rather than as text.

5. Stage Four: Semantic Analysis

Syntax tells you the code is structurally valid — 5 + "hello" parses just fine grammatically, it's a BinaryOp with a Literal on each side. But it might not be meaningful. That's what semantic analysis checks.

This stage typically handles:

Type Checking

Verifying that operations are applied to compatible types. In statically typed languages (Java, Go, Rust, TypeScript), this happens entirely before execution, and type errors are caught at compile time. In dynamically typed languages (Python, JavaScript, Ruby), most type checking is deferred until runtime — which is exactly why 5 + "hello" is a SyntaxError in Python at parse time (it doesn't even get this far) but something like 5 + user_input might pass parsing and then blow up at runtime if user_input turns out to be a string.

Scope Resolution

Determining which declaration a given identifier actually refers to. Consider:

let x = 10;
function foo() {
  let x = 20;
  console.log(x); // which x?
}

The semantic analysis phase builds a symbol table — essentially a structured map from names to their declarations, respecting nested scopes — to resolve this correctly. This is also where "undefined variable" errors get caught: if an identifier can't be resolved against any symbol table entry in any enclosing scope, that's a semantic error, even though console.log(undeclaredVar) is perfectly valid syntax.

Other Static Checks

Depending on the language, this stage might also check: are all code paths through a function returning a value (if the function's signature promises one)? Is this variable being used before it's assigned? Are these function call arguments the right number and type? Is this break statement actually inside a loop?

6. Now the Real Fork: Interpretation vs. Compilation

With a validated AST (and often an accompanying symbol table) in hand, we reach the point where interpreters and compilers genuinely diverge.

Tree-Walking Interpretation

The most straightforward approach: write a function that recursively walks the AST and directly executes it as it goes.

def evaluate(node, environment):
    if isinstance(node, Literal):
        return node.value
    elif isinstance(node, Identifier):
        return environment.lookup(node.name)
    elif isinstance(node, BinaryOp):
        left_val = evaluate(node.left, environment)
        right_val = evaluate(node.right, environment)
        if node.operator == '+':
            return left_val + right_val
        elif node.operator == '*':
            return left_val * right_val
        # ... etc
    elif isinstance(node, Assignment):
        value = evaluate(node.value, environment)
        environment.define(node.target.name, value)
        return value

This is genuinely how many early/simple interpreters work — and it's how you'd build a first interpreter as a learning exercise (the classic example is the "Monkey" language from Thorsten Ball's Writing An Interpreter In Go, or the tree-walking interpreter built in Bob Nystrom's Crafting Interpreters). It's simple to write and reason about, but it's slow — every single time you execute a loop body, you're re-traversing tree nodes and re-dispatching on node type, which involves a lot of repeated overhead compared to running pre-translated instructions.

Compilation to Bytecode

A faster approach, used by CPython, the JVM, and many others: instead of walking the AST every time you execute it, compile the AST once into a flatter, simpler instruction format — bytecode — and then run a much simpler, faster loop that executes those instructions.

For 5 + 3, bytecode might look like:

LOAD_CONST 5
LOAD_CONST 3
BINARY_ADD

This is executed by a virtual machine (VM) — not a hardware VM like VirtualBox, but a software program that simulates a simple CPU-like machine: it typically has a stack (for pushing/popping intermediate values) and a loop that reads one bytecode instruction at a time and executes it.

def run_bytecode(instructions):
    stack = []
    for instr in instructions:
        if instr.op == 'LOAD_CONST':
            stack.append(instr.value)
        elif instr.op == 'BINARY_ADD':
            b = stack.pop()
            a = stack.pop()
            stack.append(a + b)
        # ... etc
    return stack[-1]

This is faster than tree-walking for a subtle but important reason: bytecode is flat and linear, so the interpretation loop is simple, tight, and predictable — much friendlier to CPU branch prediction and instruction caching than recursively walking a tree structure with polymorphic dispatch at every node.

This is exactly what Python does: when you run a .py file, CPython first compiles your source into bytecode (you might have seen the resulting .pyc files in a __pycache__ folder — that's the compiled bytecode, cached so it doesn't need recompiling on every run), and then CPython's interpreter — itself a C program — runs that bytecode in a loop very similar to the one above, just far more sophisticated.

Compilation to Native Machine Code

The other end of the spectrum: instead of compiling to an intermediate bytecode that still needs a VM to run it, compile all the way down to the actual machine code your CPU can execute directly. This is what C, C++, Rust, and Go compilers do. There's no VM, no bytecode interpretation loop at runtime — your compiled program is a sequence of native CPU instructions, executed directly by the hardware.

This requires a much more sophisticated compiler backend — handling register allocation (deciding which values live in the CPU's limited registers vs. memory), instruction selection (translating abstract operations into the specific instructions your target CPU architecture supports), and often multiple layers of optimization passes — but it eliminates the interpretation overhead entirely. This is the fundamental reason C and Rust programs typically run faster than equivalent Python programs: there's no interpreter loop involved at all at runtime, just direct hardware execution.

7. The Middle Ground: Just-In-Time (JIT) Compilation

Here's where the clean "compiled vs. interpreted" story really breaks down, because most high-performance dynamic language runtimes today do both, dynamically, at runtime.

JIT compilation works like this: start by interpreting bytecode normally (as described above). But monitor which parts of the code are running frequently — "hot" loops or functions. When some piece of code crosses a "this is being run a lot" threshold, the runtime pauses, compiles that specific piece down to native machine code on the fly, and swaps future executions of that code to use the fast native version instead of the slow bytecode interpretation loop.

This is exactly what:

V8 (Chrome/Node.js's JavaScript engine) does — it starts interpreting via an interpreter called Ignition, and JIT-compiles hot functions via an optimizing compiler called TurboFan.
The JVM does via its HotSpot JIT compiler — the name "HotSpot" literally refers to this "find the hot spots and compile them" strategy.
PyPy (an alternative Python implementation) does, which is why PyPy is often dramatically faster than standard CPython for long-running, loop-heavy programs — CPython has no JIT at all in its standard form; it's purely bytecode-interpreted, start to finish.

JIT compilation is genuinely one of the more elegant engineering solutions in this whole space: it gets you the fast startup time of an interpreter (no need to wait for a full compilation pass before running anything) and the near-native performance of compiled code for the parts of your program that actually matter for performance (the hot loops), without paying compilation cost upfront for code that only runs once or rarely.

8. Putting the Whole Pipeline Together

Here's the full picture, stage by stage, with where different real-world systems fall:

Source Code (text)
      ↓
  [ LEXER ]  →  Tokens
      ↓
  [ PARSER ]  →  Abstract Syntax Tree (AST)
      ↓
  [ SEMANTIC ANALYSIS ]  →  Validated AST + Symbol Table
      ↓
      ├─→ [ TREE-WALKING INTERPRETER ] → Direct execution (simple, slow)
      │
      ├─→ [ BYTECODE COMPILER ] → Bytecode
      │         ↓
      │     [ VM / BYTECODE INTERPRETER ] → Execution (CPython, standard Ruby)
      │         ↓
      │     [ JIT COMPILER, if present ] → Native code for hot paths (V8, JVM HotSpot, PyPy)
      │
      └─→ [ NATIVE CODE COMPILER ] → Machine code (C, Rust, Go) → Direct hardware execution

Every arrow in this diagram represents real, substantial engineering — lexer generators, parser theory, type systems, register allocators, optimizing compiler passes, garbage collectors interacting with all of the above. But the shape of the pipeline — text → tokens → tree → (validated tree) → execution in some form — is remarkably consistent across essentially every programming language runtime that exists.

9. Why This Matters in Practice

Understanding this pipeline isn't just academic — it changes how you work day to day:

Error messages make more sense. A SyntaxError happens during parsing — before your code has run at all, which is why syntax errors can appear even in code paths that would never execute. A NameError/ReferenceError for an undefined variable is a semantic analysis or (in dynamic languages) a runtime scope-resolution failure. A TypeError on 5 + "hello" is a semantic/type-checking failure. Knowing which stage an error comes from tells you a lot about when in the pipeline it was caught, and therefore what kind of mistake you actually made.
Performance intuition improves. Once you know Python is interpreting bytecode in a loop with no JIT (in its standard implementation) while a JS engine JIT-compiles hot paths to native code, the performance gap between "equivalent" Python and JavaScript loops stops being mysterious — it's a direct consequence of architectural choices in each runtime, not some vague notion that "JS is just faster."
You can actually build one. This whole pipeline, for a small toy language, is genuinely approachable to build yourself — hundreds of tutorials and books (Crafting Interpreters being probably the most beloved) walk through building exactly this: a lexer, a recursive descent parser, an AST, and a tree-walking interpreter, in a few hundred to a couple thousand lines of code. Doing this once is one of the highest-leverage learning exercises in all of software engineering, because it demystifies every language you'll ever use afterward.

DEV Community