How Compilers Actually Work: Lexing, Parsing, and Code Generation

Quick Answer

A compiler turns source code into something executable through a fixed pipeline: a lexer breaks text into tokens, a parser assembles those tokens into an abstract syntax tree (AST) based on the language's grammar, semantic analysis checks the tree for meaning, and code generation walks the AST to emit lower-level instructions. Below, we build a real, tiny version of the lexer, parser, and code generator in Python and run it, so you can see the actual tokens, actual tree, and actual generated instructions for a real expression.

The Pipeline in One Picture

Every compiler, from a five-minute toy project to GCC or LLVM, breaks the job of "turn source code into something a machine can execute" into the same handful of stages, each with a narrow, well-defined job:

• Lexical analysis (lexing): turn a raw string of characters into a flat list of tokens — meaningful chunks like numbers, operators, and keywords — throwing away whitespace and comments.
• Parsing: take that flat list of tokens and assemble it into a tree structure (an abstract syntax tree, or AST) that reflects the grammar of the language — which operations apply to which operands, and in what order.
• Semantic analysis: walk the tree and check that it actually means something valid — do the types match, is every variable declared before use, does this function call have the right number of arguments.
• Code generation: walk the (now validated) tree one more time and emit lower-level instructions — machine code, bytecode, or an intermediate representation — that actually does what the tree describes.
• Optimization usually happens between semantic analysis and final code generation, sometimes as several passes, rewriting the intermediate representation to be faster or smaller without changing what it computes.

Reading about these stages is one thing; the rest of this post builds a real, deliberately tiny implementation of the lexer, parser, and code generator in Python, runs it on a real expression, and shows you the actual, unedited output at each step — not a diagram, actual printed data structures from actual executed code.

The toy language we're compiling is simple on purpose: arithmetic expressions with +, -, *, and parentheses, operating on whole numbers. The example expression we'll trace through every stage is:

3 + 4 * (2 - 1)

which should evaluate to 7, because * binds tighter than +, and the parenthesized 2 - 1 is evaluated first — and we'll prove our toy compiler agrees with Python's own arithmetic at the very end.

Stage 1: Lexing — Turning Text Into Tokens

A lexer's job is narrow: read the raw source text and produce a flat sequence of tokens, each tagged with what kind of thing it is. The simplest reasonably-correct way to build one is a single regular expression with named groups, one per token type, tried in order at each position in the string:

TOKEN_SPEC = [
    ("NUMBER",   r"\d+(\.\d+)?"),
    ("PLUS",     r"\+"),
    ("MINUS",    r"-"),
    ("STAR",     r"\*"),
    ("SLASH",    r"/"),
    ("LPAREN",   r"\("),
    ("RPAREN",   r"\)"),
    ("SKIP",     r"[ \t]+"),
]

MASTER_PATTERN = re.compile(
    "|".join(f"(?P<{name}>{pattern})" for name, pattern in TOKEN_SPEC)
)

def tokenize(source):
    tokens = []
    for match in MASTER_PATTERN.finditer(source):
        kind = match.lastgroup
        value = match.group()
        if kind == "SKIP":
            continue
        tokens.append(Token(kind, value, match.start()))
    tokens.append(Token("EOF", "", len(source)))
    return tokens

Each named group in the master pattern is tried at the current position, whichever one matches wins, and finditer walks through the whole string finding one match after another. Whitespace gets matched by the SKIP group and thrown away; everything else becomes a Token carrying its kind, its literal text, and its position in the source (useful later for error messages). Running this on our example string, "3 + 4 * (2 - 1)", produces this actual, unedited output:

TOKENS:
  Token('NUMBER', '3', pos=0)
  Token('PLUS', '+', pos=2)
  Token('NUMBER', '4', pos=4)
  Token('STAR', '*', pos=6)
  Token('LPAREN', '(', pos=8)
  Token('NUMBER', '2', pos=9)
  Token('MINUS', '-', pos=11)
  Token('NUMBER', '1', pos=13)
  Token('RPAREN', ')', pos=14)
  Token('EOF', '', pos=15)

Notice what's already gone: the spaces between tokens don't exist anymore. The lexer's whole job was to throw away everything that doesn't carry meaning and hand the parser a clean, flat list to work with. Ten tokens for a 15-character string — that ratio is completely normal; lexing is a lot of narrow, repetitive decisions made very fast.

Stage 2: Parsing — Building the AST

The parser's job is harder: it has to take that flat list and recover the structure the lexer threw away — specifically, which operations happen in which order. This matters because 3 + 4 * (2 - 1) isn't computed left to right; multiplication binds tighter than addition, so the 4 * (2 - 1) part has to become one unit before the + 3 applies to it.

The standard technique for this without needing a parser-generator tool is called recursive descent with precedence climbing: you write one function per precedence level, and each level's function calls the next-tighter level's function before deciding whether an operator at its own level applies. For our four operators, that's two levels — expr (handles +/-) built on top of term (handles *//), which is built on top of factor (handles numbers and parenthesized sub-expressions):

def parse_expr(self):
    node = self.parse_term()
    while self.peek().kind in ("PLUS", "MINUS"):
        op_tok = self.advance()
        right = self.parse_term()
        op = "+" if op_tok.kind == "PLUS" else "-"
        node = ("binop", op, node, right)
    return node

def parse_term(self):
    node = self.parse_factor()
    while self.peek().kind in ("STAR", "SLASH"):
        op_tok = self.advance()
        right = self.parse_factor()
        op = "*" if op_tok.kind == "STAR" else "/"
        node = ("binop", op, node, right)
    return node

def parse_factor(self):
    tok = self.peek()
    if tok.kind == "NUMBER":
        self.advance()
        return ("num", int(tok.value))
    if tok.kind == "LPAREN":
        self.advance()
        node = self.parse_expr()
        self.expect("RPAREN")
        return node
    raise SyntaxError(f"Unexpected token {tok.kind}")

Because parse_term calls parse_factor before parse_expr ever gets to combine things with +/-, every multiplication and division is fully resolved into a single node before an addition or subtraction can wrap around it. That's the entire mechanism by which operator precedence gets encoded — not a table of precedence numbers consulted at runtime, but the actual call structure of the parser. AST nodes here are just plain tuples: ("num", 3) for a literal, and ("binop", op, left, right) for a binary operation. Running this parser on the same token list produces this actual, unedited AST:

AST (nested tuples):
  ('binop', '+', ('num', 3), ('binop', '*', ('num', 4), ('binop', '-', ('num', 2), ('num', 1))))

Read from the outside in: the root operation is +, with 3 on the left and an entire * sub-expression on the right. That * sub-expression has 4 on its left and an entire - sub-expression — the parenthesized part — on its right. The parentheses in the original source don't appear anywhere in the tree; they did their job during parsing (forcing parse_expr to be called again inside parse_factor) and then disappeared, because the tree's shape itself now encodes the grouping. This is the key insight of parsing: the output isn't text with structure implied by punctuation, it's a data structure with the structure made explicit.

Stage 3: What Semantic Analysis Would Check

Our toy language is small enough to skip semantic analysis almost entirely — every token is either a number or an arithmetic operator, there are no variables to declare, no types other than numbers, and no functions to call with the wrong number of arguments. But it's worth being explicit about what this stage does in a real compiler, because it's where most of the error messages you actually read as a developer come from.

Semantic analysis walks the AST after parsing and checks things the grammar alone can't express. A grammar can guarantee that x = y + 1 is structurally valid — an assignment of a binary expression to a variable — but it can't tell you whether y was ever declared, whether it's a number or a string, or whether it's in scope at that point in the program. That's semantic analysis's job:

• Symbol resolution: building a symbol table that tracks every declared name and where it's valid (its scope), and rejecting references to names that were never declared or have already gone out of scope.
• Type checking: confirming that operations are applied to compatible types — you can't multiply a string by a boolean in most languages, and this is the stage that catches it, not the parser.
• Other static checks: things like verifying a function is called with the right number and type of arguments, that a return statement's type matches the function's declared return type, or that a variable marked const is never reassigned.

This is also the stage where an AST is often annotated or rewritten into a slightly different tree — one where every node now carries a resolved type — before code generation, so the next stage doesn't have to re-derive information semantic analysis already figured out.

Stage 4: Code Generation — From Tree to Instructions

Code generation's job is to walk the AST one more time and emit a sequence of lower-level instructions that, when executed, compute the same thing the tree describes. Real compilers target real machine instruction sets or a well-defined intermediate representation (LLVM IR, JVM bytecode, WebAssembly); our toy targets an even simpler imaginary machine: a stack machine with four instructions, PUSH, ADD, SUB, and MUL, that operate by pushing and popping values off a single stack.

The code generator is a straightforward post-order tree walk: to generate code for a binary operation, first generate the code for its left child, then its right child, then emit the operator — because a stack machine needs both operands pushed before it can pop them and combine them:

def generate(node):
    code = []
    def walk(n):
        if n[0] == "num":
            code.append(("PUSH", n[1]))
        elif n[0] == "binop":
            _, op, left, right = n
            walk(left)
            walk(right)
            opcode = {"+": "ADD", "-": "SUB", "*": "MUL"}[op]
            code.append((opcode,))
    walk(node)
    return code

Run against the AST from the previous section, this actually produces:

GENERATED BYTECODE:
  ('PUSH', 3)
  ('PUSH', 4)
  ('PUSH', 2)
  ('PUSH', 1)
  ('SUB',)
  ('MUL',)
  ('ADD',)

Read top to bottom against a stack: push 3, push 4, push 2, push 1, then SUB pops 2 and 1 and pushes their difference (1), then MUL pops 4 and that 1 and pushes their product (4), then ADD pops 3 and that 4 and pushes their sum — 7. To prove this isn't just plausible-looking output, we wrote a five-line interpreter for exactly these four instructions, ran the generated bytecode through it, and compared the result against Python's own eval() of the original source string:

EXECUTING BYTECODE -> 7
PYTHON eval() OF SAME SOURCE -> 7
MATCH: bytecode result equals Python's own eval() of the source.

Both agree: 7. That's the entire pipeline, start to finish, on real (if tiny) code: characters in, tokens out; tokens in, a tree out; tree in, instructions out; instructions in, the right answer out.

How Real Compilers Go Further

Everything above is a genuine, working compiler pipeline, just an intentionally small one. Production compilers do the same things but with a lot more machinery around each stage:

• Lexers in real compilers are usually hand-written or generated from a formal specification (tools like flex) rather than a single regex, mainly for better performance and error recovery on malformed input, but the underlying idea — turn characters into typed tokens — is identical.
• Parsers for real languages handle far more grammar than arithmetic: statements, function definitions, classes, pattern matching. Many production parsers use parser-generator tools (Yacc/Bison, ANTLR) that take a grammar specification and generate the recursive-descent-equivalent code automatically, though hand-written recursive descent parsers, like ours but much bigger, are still extremely common — Clang and V8 both use them.
• Optimization sits between semantic analysis and final code generation as one or many passes over an intermediate representation: constant folding (computing 2 - 1 at compile time instead of at runtime, something our toy compiler doesn't do but easily could), dead code elimination, inlining small functions, and dozens of other rewrites, each one required to prove it doesn't change what the program computes.
• Code generation targets real hardware instruction sets (x86-64, ARM) or a portable intermediate form, and has to deal with real machine constraints our toy stack machine doesn't: a limited number of physical registers, instruction scheduling for pipeline efficiency, and calling conventions for functions.

The honest summary is that the four-stage shape you just watched run on 15 characters of arithmetic is not a simplification of what real compilers do — it's structurally the same pipeline GCC, Clang, and the CPython interpreter itself all use. What changes at production scale is the size of the grammar, the sophistication of the optimizations, and the realism of the target machine, not the fundamental shape of the pipeline.

Frequently Asked Questions