Compilers, interpreters & automata

1 · Compiled vs interpreted vs bytecode VM essential

Start with a puzzle that trips up almost every new engineer. Someone tells you "Python is an interpreted language, C is compiled." You nod. Then you notice Python leaves little .pyc files lying around after you run a script, and you wonder — if it's just interpreted line by line, what are those? And why does a C program launch instantly while a Python one pauses to "warm up"? The tidy compiled-vs-interpreted split you were taught is a half-truth, and the missing piece explains startup time, portability, and half the "why is this slow?" questions you'll ever ask.

Here's the everyday analogy that makes it click. Imagine you've written a recipe in English and you need a French chef to cook it. You have three options. You could translate the whole recipe into French once, hand over the finished French document, and the chef cooks straight from it forever — fast every time, but you did all the translation up front and the French copy only works for French kitchens. That's compilation to native code. Or you could stand at the chef's shoulder and translate each line out loud as they cook — no up-front work, but you're re-translating every single time the dish is made. That's classic interpretation. Or — the clever middle path — you translate the recipe into a simple universal shorthand that any trained kitchen assistant can follow, then a local assistant reads that shorthand and cooks. That shorthand is bytecode, and the assistant is a virtual machine.

There are three broad ways to run source code. Compiled (C, Rust, Go): a compiler translates the whole program to native machine code ahead of time; you ship a binary. Interpreted (classic shell, early BASIC): a program reads and executes your source line by line. Bytecode VM (Python, Java, C#): the source is compiled to portable bytecode, then a virtual machine executes that bytecode.

The common mistake is to call Python "interpreted" and stop there — it makes people expect it to re-read the raw text of every line, which isn't what happens. Python compiles your .py to bytecode first (those .pyc files are the cached result), and only then does the CPython VM step through the bytecode. That's why the categories aren't a clean either/or but a spectrum of when translation happens: fully ahead of time (C), fully at run time (a pure interpreter), or a bit of both (bytecode plus a VM, sometimes with just-in-time compilation on top, as in the JVM and JavaScript). Why it matters to you as an engineer: the model decides the trade-offs you live with. Native compilation gives you fast startup and a self-contained binary but ties you to one CPU architecture. Interpretation gives you instant edit-run cycles but pays the translation cost on every execution. The bytecode-VM middle ground buys portability — the same .pyc runs anywhere CPython runs — at the price of shipping the interpreter alongside your code. Knowing which world you're in tells you why a Go binary drops into a container with nothing else, why a Python image needs the whole interpreter baked in, and why the JVM burns a few seconds "warming up" before it hits full speed.

Python is not purely interpreted: it compiles your .py to bytecode first. You can see the bytecode with the standard-library dis module:

show_bytecode.pyimport dis
def add(a, b):
    return a + b
dis.dis(add)

  2           RESUME                   0

  3           LOAD_FAST_LOAD_FAST      1 (a, b)
              BINARY_OP                0 (+)
              RETURN_VALUE

2 · The compiler pipeline essential

Think about how you read this very sentence. Your eyes don't take in the page as one undifferentiated smear of ink — you first pick out individual words, then you group those words into a structure (subject, verb, object), and only then do you extract the meaning. You do all three so fast it feels like one step, but they're distinct: recognise the words, figure out how they fit together, understand what they say. A compiler reads your source code in exactly these same three moves, and once you see the parallel the whole pipeline stops being mysterious.

Those three moves have names. Lexing (also called scanning or tokenising) is "pick out the words" — it walks the flat character stream and groups it into tokens, the atoms of the language: this run of digits is a number, this + is a plus operator, throw away the spaces. Parsing is "figure out the structure" — it takes that flat list of tokens and discovers the nesting hidden in it, building an AST (abstract syntax tree) where 4 * 2 sits inside the addition because multiplication binds tighter. Evaluation or code generation is "extract the meaning" — either run the tree directly (an interpreter) or emit machine code from it (a compiler). The reason we split the work into stages rather than doing it all at once is the same reason you don't wire a whole house with one giant cable: each stage has one clean job and a clean handoff, so you can test, swap, or reuse any stage independently — the same lexer can feed a syntax highlighter, a formatter, and a compiler.

The mistake to avoid is imagining the compiler "understands" the raw text directly, skipping straight from "3 + 4 * 2" to the answer. It never does. Every language processor you'll meet — from a JSON parser to a full C++ compiler to the thing that reads your Terraform files — funnels text through this same assembly line: characters → tokens → tree → behaviour. Whether it ends in machine code or an interpreter, a language processor's front end is the same assembly line: lexing chops text into tokens, parsing builds an AST (abstract syntax tree) that captures structure, and the back end does code generation or direct evaluation. The diagram below traces one tiny expression, 3 + 4 * 2, through every stage — and the next three sections build each stage in real, runnable Python so it's never a black box again.

3 · Build a lexer advanced

Here's the moment lexing suddenly feels real. The first time most people meet the word "tokenizer" is when they hit an LLM — you paste text into a model and it charges you "per token," and you learn that "tokenizer" might be three tokens while "the" is one. That token-splitting is the exact same idea you're about to build by hand: taking a stream of characters and chopping it into the meaningful units downstream code actually cares about. Build a lexer once, from scratch, and every "why did the model count my tokens that way?" question afterwards has an intuition behind it.

The analogy is scanning a printed page for words. You sweep left to right, and your brain silently does three things over and over: it skips the gaps (spaces don't carry meaning), it collects runs of letters into whole words (you don't stop after each letter), and it recognises punctuation as its own thing. A lexer does precisely that: skip whitespace, gather a run of digits into one number token, and treat each operator or parenthesis as its own token. The one subtlety — and it's the whole reason a lexer is a loop and not a one-liner — is that a single token can span several characters. The number 127 is one token made of three characters, so when the lexer sees a digit it has to keep reading ahead, gobbling digits until it hits a non-digit, before it knows the token is complete. That "look ahead and keep consuming" move is called maximal munch, and it's why the code below has an inner while loop.

The classic beginner mistake is to tokenise character by character — emitting a separate token for the 1, the 2, and the 7 of 127. Do that and the parser downstream has no idea those three belong together as one number; you've thrown away the very grouping the lexer exists to create. The other trap is forgetting the EOF token at the end: the parser needs an explicit "the input stops here" marker so it can tell "I finished cleanly" from "I ran off the edge expecting more." A lexer (tokenizer) turns a flat string into a list of meaningful tokens, discarding whitespace. For arithmetic we need numbers, the four operators, and parentheses:

lexer.pydef tokenize(src):
    tokens, i = [], 0
    while i < len(src):
        ch = src[i]
        if ch.isspace():
            i += 1
        elif ch.isdigit():
            j = i
            while j < len(src) and src[j].isdigit():
                j += 1
            tokens.append(("NUM", int(src[i:j])))
            i = j
        elif ch in "+-*/()":
            kind = {"+": "PLUS", "-": "MINUS", "*": "STAR",
                    "/": "SLASH", "(": "LP", ")": "RP"}[ch]
            tokens.append((kind, ch))
            i += 1
        else:
            raise SyntaxError(f"unexpected char {ch!r}")
    tokens.append(("EOF", None))
    return tokens

for t in tokenize("3 + 4 * 2"):
    print(t)

('NUM', 3)
('PLUS', '+')
('NUM', 4)
('STAR', '*')
('NUM', 2)
('EOF', None)

4 · A grammar in BNF intermediate

Ask yourself a question you already know the answer to but have never had to write down: why is 3 + 4 * 2 equal to 11 and not 14? "Because multiplication comes first," you say — but where is that rule written? It isn't in the lexer (which just spits out tokens in the order it reads them), and you'd rather not bury it in a tangle of if statements. The place that precedence lives — cleanly, provably, once — is the grammar. A grammar is the rulebook that says which sequences of tokens count as a valid sentence in your language, and how they're allowed to nest.

The friendliest analogy is the grammar of English you absorbed as a child: a sentence is a noun phrase followed by a verb phrase; a noun phrase is an article plus a noun; and so on. Each rule can refer to other rules, and that referring-to-each-other is what lets a finite rulebook describe infinitely many sentences. Programming-language grammars work identically, and we write them in a compact notation called BNF (Backus–Naur Form). Each line is a rule of the form name ::= what it's made of. The magic trick — the thing worth slowing down for — is that precedence is encoded purely by how the rules are layered. You define expr in terms of term, and term in terms of factor. Because the tighter-binding operators (*, /) live in the rule that sits lower in the stack (term), they get resolved before the looser ones (+, -) up in expr. You never write "multiply first" anywhere — the shape of the rules says it for you.

The mistake people make is treating a grammar as mere documentation — a comment describing the language after the fact. It's the opposite: the grammar is the source of truth, and the parser is a faithful transcription of it. Get the layering wrong and your calculator will cheerfully compute 3 + 4 * 2 as 14, not because of a bug in your loop but because you encoded the wrong precedence in the rules. That direct grammar-to-code correspondence is exactly why the next section's parser has one function per grammar rule, no more and no less. A grammar defines which token sequences are valid. Written in BNF (Backus–Naur Form), our arithmetic grammar encodes precedence — *// bind tighter than +/- — by layering the rules:

grammar.bnfexpr   ::= term  (("+" | "-") term)*
term   ::= factor (("*" | "/") factor)*
factor ::= NUMBER | "(" expr ")"

# "expr is made of terms joined by + or -"
# "term is made of factors joined by * or /"   <- tighter binding
# "factor is a number or a parenthesised expr" <- recursion / grouping

5 · A recursive-descent parser & evaluator advanced

This is the section where the magic stops being magic. You've probably used eval(), or watched a calculator app get precedence right, and quietly assumed there's some deep clever algorithm behind it. There isn't. A working expression parser is astonishingly small — a handful of short functions — and once you've written one you'll never again be intimidated by the phrase "I wrote a parser." The technique is called recursive descent, and its whole secret is: transcribe the grammar into functions, one function per rule, and let them call each other exactly the way the rules refer to each other.

The analogy that makes recursion feel natural here: think of a set of Russian nesting dolls, where opening one doll reveals another inside. The expr function opens up and finds a term inside it; the term function opens up and finds a factor; and a factor might be a plain number — or it might be a parenthesised expression, which sends you all the way back out to expr again. That "back out to the top" step is the recursion, and it's what lets a fixed handful of functions handle expressions nested arbitrarily deep, like ((1 + 2) * (3 + 4)). Each function has exactly one responsibility, matching exactly one grammar line, so you can read the parser and the grammar side by side and see they're the same thing written twice.

We're going to take a shortcut that's worth naming out loud: instead of building a tree and then walking it, we'll fold evaluation into the parse — each function returns the value of what it just parsed, so by the time expr finishes, you have the answer. This is a legitimate design called a one-pass interpreter, and it's the leanest way to see the whole idea work. The mistake to watch for: a real production compiler does not do this — it builds an explicit AST first and evaluates in a separate pass, precisely so it can run optimisation, type-checking, and code generation over the same tree (Exercise 5 in the ladder walks you through that refactor). For learning, evaluating in place keeps the code short enough to hold in your head. A recursive-descent parser is one function per grammar rule, calling each other exactly as the grammar nests. Here we fold evaluation into the parse (a one-pass interpreter): each rule returns the numeric value of what it parsed, so the calculator is complete.

parser.pyclass Parser:
    def __init__(self, tokens):
        self.toks, self.pos = tokens, 0
    def peek(self):  return self.toks[self.pos]
    def eat(self, kind):
        tok = self.toks[self.pos]
        if tok[0] != kind:
            raise SyntaxError(f"expected {kind}, got {tok[0]}")
        self.pos += 1
        return tok

    def parse(self):
        v = self.expr()
        self.eat("EOF")
        return v
    def expr(self):                      # expr ::= term (("+"|"-") term)*
        v = self.term()
        while self.peek()[0] in ("PLUS", "MINUS"):
            op = self.eat(self.peek()[0])[0]
            v = v + self.term() if op == "PLUS" else v - self.term()
        return v
    def term(self):                      # term ::= factor (("*"|"/") factor)*
        v = self.factor()
        while self.peek()[0] in ("STAR", "SLASH"):
            op = self.eat(self.peek()[0])[0]
            v = v * self.factor() if op == "STAR" else v // self.factor()
        return v
    def factor(self):                    # factor ::= NUM | "(" expr ")"
        tok = self.peek()
        if tok[0] == "NUM":
            self.eat("NUM"); return tok[1]
        self.eat("LP"); v = self.expr(); self.eat("RP")
        return v

def calc(src):
    return Parser(tokenize(src)).parse()

print("3 + 4 * 2      =", calc("3 + 4 * 2"))      # * binds tighter
print("(3 + 4) * 2    =", calc("(3 + 4) * 2"))    # parens override
print("20 / 4 - 1     =", calc("20 / 4 - 1"))

3 + 4 * 2      = 11
(3 + 4) * 2    = 14
20 / 4 - 1     = 4

6 · Regular languages & finite automata advanced

You already run a finite automaton in your head every day and never call it that. A traffic light is one: it's in a state (green), an input arrives (the timer fires), and it moves to the next state (yellow, then red, then green again). A turnstile is one: locked until you insert a coin, then unlocked until you push through. There's no notebook, no memory of how many people came before — just "what state am I in, and what does this input do to it?" That stripped-down model of computation is the finite automaton, and it turns out to be the theoretical machine hiding inside every regular expression and every lexer you've ever used.

The lexer above recognised numbers with a loop — that loop is really a finite automaton. A DFA (deterministic finite automaton) is the simplest machine: a set of states, a transition for each input symbol, a start state, and some accepting states. It has no memory beyond its current state, so it recognises exactly the regular languages — the same class that regular expressions describe. The word "deterministic" just means there's no guessing: in any state, a given input symbol leads to exactly one next state, so running the machine is a boring, mechanical walk — which is precisely why it's blindingly fast and why regex engines are built on it.

The part that genuinely surprises people is the "no memory beyond its current state" constraint, because it sounds crippling and yet a DFA can do real work. The example below accepts binary strings that represent numbers divisible by 3 — and the elegant trick is that the state itself carries all the information you need: it's the running remainder mod 3. You don't store the digits you've seen; you just track "the number so far leaves remainder 0, 1, or 2," and each new bit nudges you to a new remainder via r = (r*2 + b) % 3. Three states are enough for an input of any length. The mistake to internalise here — and it's the whole punchline that Section 7 pays off — is assuming a DFA can therefore do anything. It can't: because it has no counter and no stack, it fundamentally cannot match n opening parentheses against n closing ones for arbitrary n. That limitation isn't a flaw to engineer around; it's the exact boundary line between "regular" languages and the more powerful ones above them. Let's build a DFA that accepts binary strings representing numbers divisible by 3. The trick: the state is the running remainder mod 3. Reading a bit b updates r = (r*2 + b) % 3; accept if we end in remainder 0.

dfa.py# states 0,1,2 = value-so-far mod 3;  start = 0;  accept = {0}
TRANSITION = {
    (0, "0"): 0, (0, "1"): 1,
    (1, "0"): 2, (1, "1"): 0,
    (2, "0"): 1, (2, "1"): 2,
}
ACCEPT = {0}

def accepts(s):
    state = 0                             # start state
    for ch in s:
        state = TRANSITION[(state, ch)]   # deterministic step
    return state in ACCEPT

for s in ["0", "11", "110", "1001", "1010", "111"]:
    print(f"{s:>5}  (={int(s, 2):>2})  accepted={accepts(s)}")

    0  (= 0)  accepted=True
   11  (= 3)  accepted=True
  110  (= 6)  accepted=True
 1001  (= 9)  accepted=True
 1010  (=10)  accepted=False
  111  (= 7)  accepted=False

7 · The Chomsky hierarchy & the limits of computation professional

Section 6 left you with a nagging fact: a DFA cannot match nested parentheses. That should bother you, because parentheses are trivial for a human and trivial for the parser you wrote — so what did the parser have that the DFA didn't? The answer is a single, specific superpower: memory that can grow. And that one difference turns out to be the first rung of a ladder that organises every language and every machine, from a regex all the way up to the theoretical limit of what any computer can ever do. That ladder is the Chomsky hierarchy, and it's one of the most quietly profound ideas in all of computer science.

Here's the analogy to hold onto: it's a ladder where each rung buys the machine a bigger kind of scratch paper. At the bottom, a finite automaton has no scratch paper — only its current state, a fixed set of sticky notes it can point at. Climb one rung and you hand the machine a stack (a pushdown automaton) — now it can jot down "I owe a closing paren" and cross it off later, which is exactly enough to match nested brackets and parse arithmetic; that's why your parser, which used the call stack, could do what the lexer's DFA couldn't. Climb higher and the scratch paper gets roomier and more flexible, until at the top the machine gets an unbounded tape it can read and rewrite freely — that's the Turing machine, and it's the model of everything a computer can compute, full stop. More power, in other words, is literally more memory structure. Languages form a hierarchy by the power of machine needed to recognise them (Chomsky, 1956). More power = more memory structure:

Why should a working engineer care about a 1956 hierarchy of abstract machines? Because it tells you when you're reaching for the wrong tool — and this is the single most common mistake the hierarchy warns against. People habitually try to parse deeply nested things (HTML, source code, matched brackets) with a regular expression, and it fails in maddening, subtly-broken ways. The hierarchy explains why it can never fully work: regexes are Type-3 machines with no stack, and nested structure is a Type-2, context-free problem that fundamentally requires one. That's not a bug in your regex; it's a law of the ladder. The flip side is the humbling top of the hierarchy — the point where even a Turing machine, the most powerful model we have, hits a wall. Some questions have no algorithm at all, and knowing that boundary exists keeps you from burning weeks chasing a program that provably cannot be written.

A DFA can't count unbounded nesting — matching (( )) to arbitrary depth needs a stack, i.e. a context-free grammar (which is why our parser, not the lexer, handles parentheses). At the top sits the Turing machine, the model of everything computable.

Knowledge check check yourself

answer = {
  'C':      'compiled to native machine code  -> executable binary',
  'Python': 'compiled to bytecode -> run by CPython VM (.pyc)',
  'Java':   'compiled to bytecode -> run by JVM, often JIT (.class)',
}
for k, v in answer.items():
    print(k, '->', v)

def tokenize(src):
    toks, i = [], 0
    ops = {'+':'PLUS','-':'MINUS','*':'STAR','/':'SLASH',
           '%':'PERCENT','(':'LP',')':'RP'}
    while i < len(src):
        c = src[i]
        if c.isspace(): i += 1
        elif c.isdigit():
            j = i
            while j < len(src) and src[j].isdigit(): j += 1
            toks.append(('NUM', int(src[i:j]))); i = j
        elif c in ops:
            toks.append((ops[c], c)); i += 1
        else: raise SyntaxError(c)
    toks.append(('EOF', None)); return toks

print(tokenize('10 % 3'))
# [('NUM', 10), ('PERCENT', '%'), ('NUM', 3), ('EOF', None)]

def factor(self):
    tok = self.peek()
    if tok[0] == 'MINUS':          # unary minus
        self.eat('MINUS')
        return -self.factor()
    if tok[0] == 'NUM':
        self.eat('NUM'); return tok[1]
    self.eat('LP'); v = self.expr(); self.eat('RP')
    return v

# with this factor(): calc('-5 + 2') == -3 ; calc('-(3 + 4)') == -7

# states: 0 = start/other, 1 = ends in 'a', 2 = ends in 'ab' (accept)
T = {
    (0,'a'):1, (0,'b'):0,
    (1,'a'):1, (1,'b'):2,
    (2,'a'):1, (2,'b'):0,
}
def accepts(s):
    st = 0
    for c in s: st = T[(st, c)]
    return st == 2

for s in ['ab','aab','abab','ba','a']:
    print(s, accepts(s))
# ab True / aab True / abab True / ba False / a False

# parser builds nodes; evaluation is a separate pass
def ev(node):
    if node[0] == 'num': return node[1]
    op, l, r = node
    a, b = ev(l), ev(r)
    return {'+':a+b, '-':a-b, '*':a*b, '/':a//b}[op]

# AST for 3 + 4 * 2  (built by the parser, precedence preserved):
ast = ('+', ('num', 3), ('*', ('num', 4), ('num', 2)))
print('AST  :', ast)
print('value:', ev(ast))   # 11

# DANGER: eval runs ANY Python -- never on untrusted input
#   eval("__import__('os').system('rm -rf /')")   # catastrophic

# SAFE: our grammar can only ever describe arithmetic.
def safe_calc(src):
    try:
        return Parser(tokenize(src)).parse()
    except SyntaxError as e:
        return f'rejected: {e}'

print(safe_calc('2 + 3 * 4'))            # 14
print(safe_calc("__import__('os')"))     # rejected: unexpected char '_'
print(safe_calc('2 +'))                   # rejected: expected LP, got EOF