Programs are written as text for humans but must ultimately run as instructions a machine executes. The translation happens in stages. A lexer (tokenizer) scans raw source text and groups characters into tokens — numbers, operators, identifiers — discarding irrelevant whitespace. A parser takes that token stream and builds an abstract syntax tree (AST), a structured representation that captures grouping and precedence according to the language's grammar (a formal, typically context-free, description of legal sentence structure).

A compiler translates the AST all the way down to machine code (or another lower-level language) ahead of time, producing a standalone executable. An interpreter walks the AST directly (or a simplified bytecode form of it) and executes it on the fly, redoing the translation work every run. Many modern languages blend both: a just-in-time (JIT) compiler interprets at first, then compiles the "hot" parts that run repeatedly into fast machine code mid-execution.

Why not skip straight from text to execution? Because each stage solves one clean problem. The lexer's only job is "what are the words?" The parser's only job is "how do the words nest, given the grammar's precedence rules?" — this is exactly why 2 + 3 * 4 parses as 2 + (3 * 4): multiplication binds tighter, so it sits deeper in the tree. Only once structure is unambiguous does evaluation or code generation even make sense. Separating these concerns is the same abstraction principle from every earlier chapter, applied to language itself.

We build a real, working interpreter for arithmetic expressions with + - * / and parentheses, respecting standard precedence — the same three-stage pipeline (lex, parse, evaluate) that real language implementations use, just for a tiny language.

import re

def tokenize(text):
    tokens = re.findall(r"\d+\.?\d*|[()+\-*/]", text)     # numbers, or one symbol
    return [t for t in tokens]

class Parser:
    """Recursive-descent parser: each grammar rule becomes one method.
       Precedence is expressed structurally: expr calls term calls factor."""
    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0

    def peek(self):
        return self.tokens[self.pos] if self.pos < len(self.tokens) else None

    def eat(self):
        tok = self.tokens[self.pos]
        self.pos += 1
        return tok

    def parse_expr(self):                        # expr := term (('+'|'-') term)*
        node = self.parse_term()
        while self.peek() in ("+", "-"):
            op = self.eat()
            node = (op, node, self.parse_term())  # AST node: (operator, left, right)
        return node

    def parse_term(self):                         # term := factor (('*'|'/') factor)*
        node = self.parse_factor()
        while self.peek() in ("*", "/"):
            op = self.eat()
            node = (op, node, self.parse_factor())
        return node

    def parse_factor(self):                       # factor := NUMBER | '(' expr ')'
        tok = self.eat()
        if tok == "(":
            node = self.parse_expr()
            self.eat()                             # consume ')'
            return node
        return float(tok)                          # a leaf of the AST

def evaluate(node):
    if isinstance(node, float):
        return node                                 # leaf: just a number
    op, left, right = node
    l, r = evaluate(left), evaluate(right)          # recursively evaluate children first
    return {"+": l + r, "-": l - r, "*": l * r, "/": l / r}[op]

def run(text):
    ast = Parser(tokenize(text)).parse_expr()
    return evaluate(ast)

print(run("2 + 3 * 4"))         # 14.0  -- * binds tighter, per the grammar's structure
print(run("(2 + 3) * 4"))       # 20.0  -- parentheses override precedence
print(run("10 - 2 - 3"))        # 5.0   -- left-associative: (10 - 2) - 3

Because parse_expr calls parse_term which calls parse_factor, multiplication always ends up nested deeper in the tree than addition — precedence emerges purely from which method calls which, with no special-casing needed. evaluate then walks that tree bottom-up, exactly like the recursion in Chapter 12.