How Compilers and Interpreters Work, An Animated Lesson

Lesson by Adnan, computer science lecturer  ·  aitrendblend editorial team  ·  Computer Science Education  ·  November 2026  ·  Reading time about 25 minutes

Compilers Interpreters Tokens and Parsing Bytecode JIT Compilation Python Grades 9 to 12
Animated lesson illustration of a line of code split into colored tokens, a parse tree for 2 plus 3 times 4, and stack machine instructions
How Compilers and Interpreters Work
An Animated Lesson
A processor has never read a line of Python. This lesson follows one line of code through every stage of translation, from characters to tokens to a tree to the instructions a machine can run.
Two students in the same computer lab press Run at the same moment. Sana’s Python program prints her quiz average almost instantly. Across the room, Hamza’s robotics team is programming an Arduino in C++, and his screen says Compiling sketch for several seconds before the robot moves. Neither processor has ever heard of Python or C++. A processor understands only short numeric instructions, the same kind of load, add and store steps students met in How a Computer Works. Something has to translate every readable line into those instructions, and the two students are watching two different ways of doing it. In this lesson students become the translator. They break a line of code into tokens, build the tree that gives multiplication its priority, compile that tree into instructions for a small machine, and race an interpreter against a compiler.

Key points of this lesson

  • A processor runs only machine code. Every program written in a readable language has to be translated before it runs or while it runs.
  • A compiler translates the whole program ahead of time. An interpreter translates and runs it as it goes. Most modern languages mix the two.
  • Translation happens in stages. The lexer makes tokens, the parser builds a tree, and the code generator turns the tree into instructions.
  • The parse tree is where rules such as multiplication before addition are enforced, and where syntax errors are caught.
  • Python compiles each file to bytecode and then interprets that bytecode, which is why a syntax error stops the whole file before a single line runs.
  • A just in time compiler starts like an interpreter and compiles the parts of a program that run most often.

Who this lesson is for and how to use it

This is the thirteenth lesson in our Computer Science Education series. The previous lesson, How an Operating System Works, ended by asking how programming languages are translated into the instructions a processor runs. This lesson answers that question.

It suits grades nine to twelve and first year college students, and it covers the translator and language topics found in most school computing syllabuses. Students who have written a few programs in Your First Program, Variables, Loops and Conditions will recognize every example. The parser in Lab 2 is recursive, just like the functions in Functions and Recursion, and Lab 3 runs on a stack, the data structure from Data Structures Explained. The toy processor from How a Computer Works returns at the end, when the instructions finally run. The companion Python code builds a complete tiny compiler and then shows students the real bytecode inside Python itself.

Learning objectives

After three periods, a student should be able to do the following five things without notes.

  1. Explain why a processor cannot run Python or C++ directly, and say what machine code and assembly language are.
  2. Describe a compiler, an interpreter, a bytecode virtual machine and a just in time compiler, and name a language that uses each.
  3. Split a line of code into tokens and name the kind of each token.
  4. Draw the parse tree for an arithmetic expression and use it to explain why multiplication happens before addition.
  5. Translate an expression into stack machine instructions, trace them by hand, and say at which stage a syntax error, a runtime error or a logic error is found.
PeriodFocusActivity on this pageTime
1From code to machine code, the lexerThe two students story, the human compiler game, Lab 1 lexer40 minutes
2Parsing and code generationLab 2 parse trees, drawing trees on paper, Lab 3 stack machine40 minutes
3Compilers, interpreters and errorsLab 4 race, the Python bytecode demo, quiz40 minutes

Why a processor needs a translator

A processor runs machine code. Each machine instruction is a pattern of bits that tells the processor to do one small thing, such as load a number from memory, add two numbers or jump to another instruction. The toy processor in How a Computer Works ran four of them to add 7 and 5. Real processors understand a few hundred, and different families of processors understand different sets. Most laptops use the x86 family, while phones, tablets and newer Macs use the ARM family, so machine code built for one will not run on the other.

Nobody enjoys writing bit patterns, so the first improvement was assembly language, which gives each machine instruction a short readable name such as ADD or LOAD. A small program called an assembler turns those names back into bits, one for one. High level languages such as Python, Java and C++ go much further. A single line can describe work that takes dozens of machine instructions, and the same line can run on any family of processor, as long as something translates it for that processor.

LevelThe same line of workWho reads it
High level languagetotal = price * 3 + taxPeople
Stack machine code, as in Lab 3LOAD price, PUSH 3, MUL, LOAD tax, ADD, STORE totalA virtual machine
Python bytecodeLOAD_FAST, LOAD_CONST, BINARY_OP, LOAD_FAST, BINARY_OP, STORE_FASTThe Python virtual machine
Machine codeBit patterns for one processor family, such as x86 or ARMThe processor

There are two basic ways to do the translation. A compiler translates the whole program before it runs and saves the result, usually as a file of machine code, such as an app or an .exe file on Windows. An interpreter reads the program and carries it out as it goes, translating each piece at the moment it is needed. Think of a novel translated from Urdu into English. A compiler is the translator who works on the whole book for months and publishes the English edition. An interpreter is the person standing beside a visiting speaker, translating each sentence as it is spoken. The published book is quick to read but slow to produce, and the live interpreter starts at once but has to work every time the speech is given.

A short history

In the early 1950s programmers wrote machine code by hand, number by number. In 1952 Grace Hopper finished the A-0 system for the UNIVAC I. It worked more like what we now call a linker, stitching together prewritten routines from short codes, but Hopper used the word compiler for it and spent the next decade arguing that people should program in words rather than numbers, work that fed into the COBOL language of 1959. In April 1957 John Backus’s team at IBM delivered the first FORTRAN compiler for the IBM 704. Many programmers doubted that a machine could write code as well as they could, so the team worked hard on optimization, and the code their compiler produced was efficient enough to win the doubters over.

In 1958 John McCarthy began designing the language Lisp at MIT. He wrote a function called eval as a mathematical description of how Lisp programs behave, and Steve Russell, a programmer working with him, surprised McCarthy by coding eval for the IBM 704. That made it the first Lisp interpreter. In 1962 Tim Hart and Mike Levin wrote a Lisp compiler in Lisp itself, and its code ran about forty times faster than the interpreter. Interpreted BASIC brought programming to the home computers of the 1970s and 1980s. Java arrived in 1995 with bytecode that runs on any machine with a Java virtual machine, and Sun’s HotSpot virtual machine of 1999 compiled the busiest parts of a program to machine code while it ran. Google’s V8 engine, launched with the Chrome browser in 2008, brought the same idea to JavaScript, and it is a large part of why web apps feel as quick as they do.

Teacher note, the human compiler

Give four students a role each, the lexer, the parser, the code generator and the processor. Write total = price * 3 + tax on the board. The lexer writes each token on its own card. The parser arranges the cards on a desk as a tree, with the operator that happens last at the top. The code generator reads the tree and writes one instruction per sticky note. The processor carries out the notes with a pile of scrap paper as its stack. Run the game twice, once with a missing bracket, and ask the class which student should have raised a hand first.

Step one, the lexer turns characters into tokens

To the computer, a line of code begins as nothing more than a row of characters. The first stage of every compiler and interpreter, called the lexer or tokenizer, groups those characters into meaningful words called tokens. A run of digits becomes one number token. A run of letters becomes one name token. Symbols such as the plus sign and the equals sign become operator tokens. Spaces are thrown away, because in most languages they only separate words, and comments are thrown away too, because they are written for people.

The lexer follows fixed rules that come from the definition of the language. A name must start with a letter or an underscore. A number may contain one decimal point. Any character that fits no rule at all, such as a dollar sign in Python, is a lexical error, and the translation stops there. The word token also appears in How Large Language Models Work, but the meaning is different. A language model splits text into pieces chosen from a vocabulary learned from data, while a lexer uses a short list of exact rules that never change.

Lab 1. The lexercharacters in, tokens out

name number operator assign bracket

0characters read
0tokens made
0spaces skipped

The first example turns 23 characters into 7 tokens and skips 6 spaces. Now try x=(a+b)*2, which has no spaces at all. It produces 9 tokens from 9 characters, and the token list means exactly the same as it would with spaces, which is why the spaces never reach the next stage. The circle example shows that 3.14 is a single number token, not three separate pieces. The last example stops at the dollar sign with a lexical error, and notice that nothing has run. Then type 3price into the box. The lexer happily makes two tokens, the number 3 and the name price. It is not the lexer’s job to decide whether that order makes sense. That job belongs to the parser.

Key takeaway

The lexer turns a row of characters into a list of tokens, throwing away spaces and comments. It catches characters that do not belong to the language, but it knows nothing about whether the tokens are in a sensible order.

Step two, the parser builds a tree

A list of tokens still does not say what to do first. In 2 + 3 * 4, should the processor add first or multiply first? Mathematics has a convention, and the language has the same rule written into its grammar. The parser reads the tokens and checks them against that grammar, and as it goes it builds a parse tree, sometimes called a syntax tree. Each operator becomes a node with its two inputs hanging below it, and numbers and names become leaves at the bottom.

$$2 + 3 \times 4 = 2 + 12 = 14 \qquad (2 + 3) \times 4 = 5 \times 4 = 20$$

The grammar for arithmetic can be written as three rules. An expression is one or more terms joined by plus or minus. A term is one or more factors joined by times or divide. A factor is a number, a name, or a whole expression inside brackets. Because multiplication lives one rule deeper than addition, it always ends up lower in the tree, and lower nodes are worked out first. Brackets work because the factor rule starts the expression rule again from the top, a function calling itself, which is exactly the recursion from the functions lesson. A parser written this way, with one function for each rule, is called a recursive descent parser, and the one in Lab 2 and in the companion code is about twenty lines long.

The rules also settle a quieter question. Does 10 - 4 - 3 mean 10 minus 1, or 6 minus 3? The expression rule joins terms from left to right, so the first subtraction goes lower in the tree and the answer is 3. When the tokens break the grammar, as in 2 + * 3, the parser cannot build any tree at all, and it reports a syntax error. That is the most common error beginners see, usually from a missing bracket or a missing operator.

Lab 2. Build the parse treethen let values flow upward

Swipe sideways if a large tree does not fit.

Names have these values in Labs 2 and 3. price is 20, tax is 5, x is 7, a is 6, b is 2 and r is 10.

0nodes
0levels
?result

Press the first example and watch the order in which the parser creates nodes. The leaves 2, 3 and 4 appear first, then the multiplication node joins 3 and 4, and only then does the addition node become the root. The tree has 5 nodes on 3 levels, and evaluating it gives 14. Now press the bracketed version. The same five tokens, plus two brackets, produce a tree with the addition at the bottom and the answer 20. The brackets themselves never appear in the tree, because the shape of the tree already says everything they meant.

The 10 - 4 - 3 example gives 3, with the first subtraction lower down. The example with 2 + * 3 fails at the parser, so no tree is drawn and nothing runs. Finally, type y * 2. The tree builds perfectly, because the grammar is satisfied, but evaluation stops with a runtime error, because y has no value. That difference between an error found while translating and an error found while running is one of the main ideas of this lesson.

Pressing Evaluate is exactly what the simplest interpreters do. They keep the tree and walk it every time the program runs, working out the leaves first and passing values up to the root. The earliest Lisp interpreter worked this way, and so do many teaching languages. It is easy to write, but walking a tree again and again is slow, which is why most languages go one step further.

A processor has never run a line of Python. Every program you have written was translated first, by software someone else wrote.From this lesson, period one

Step three, turning the tree into instructions

A compiler does not walk the tree each time the program runs. It walks the tree once and writes down instructions. The part of the compiler that does this is the code generator. For arithmetic it follows one simple rule at every node. Write the instructions for the left side, then the instructions for the right side, then the instruction for the operator itself. The result is code for a stack machine, a machine that keeps its working values on a stack. A number or a name is pushed onto the top, and an operator such as MUL pops the top two values and pushes their product.

Stack machines are not just a classroom trick. Python bytecode, Java bytecode, the bytecode of C# and WebAssembly in the browser are all designed for stack machines, because their instructions are short and easy to generate from a tree. A useful fact links the two labs. The stack never needs more slots than the tree has levels, because each level waiting for an answer holds at most one value.

$$\text{deepest stack} \;\le\; \text{levels in the parse tree}$$

Before writing instructions, a real compiler also runs an optimizer, which rewrites the tree or the code so the program runs faster without changing what it does. The simplest optimization is constant folding. If part of the tree uses only numbers, the compiler can work it out once, during translation, so the finished program never has to. Lab 3 lets students switch folding on and off.

Lab 3. Compile and run on a stack machineone instruction at a time

Program

    Stack, top at the top

    0instructions
    0deepest stack
    ?result

    Compile 2 + 3 * 4 and press Play. The program is five instructions, PUSH 2, PUSH 3, PUSH 4, MUL and ADD. The stack climbs to three values before MUL turns 3 and 4 into 12 and ADD turns 2 and 12 into 14. Compare the order with the tree in Lab 2, and students will see the instructions are the tree read from the bottom up. Now tick Fold constants. The whole program shrinks to a single instruction, PUSH 14, because every value was known while compiling.

    Folding is cleverer than it looks, and also more limited. x * (2 + 3) folds to LOAD x, PUSH 5 and MUL, saving two instructions, but price * 3 + tax cannot be folded at all, because every operation involves a name whose value is only known when the program runs. The program for (a + b) * (a - b) needs seven instructions and a stack three values deep, and it gives 32. Real compilers run dozens of optimizations like this one, and they finish by turning stack style code into the register based machine code of a real processor, the LOAD, ADD and STORE steps from the toy processor, only many more of them.

    Key takeaway

    The code generator walks the parse tree once and writes instructions, left side, right side, then the operator. An optimizer can do work early, such as folding number only arithmetic, so the finished program has less to do.

    Compilers, interpreters and the ground between

    Real languages rarely sit at one extreme. Between a pure compiler and a pure interpreter there is a range of strategies, and most popular languages use something in the middle.

    StrategyWhat happensExamplesTradeoff
    Ahead of time compilerThe whole program is translated to machine code before it runsC, C++, Rust, Go, SwiftVery fast to run, but there is a wait to build, and a separate build for each processor family
    Line by line or tree walking interpreterThe program is translated piece by piece while it runs, every time it runsBASIC on early home computers, shell scripts, the Evaluate button in Lab 2Starts instantly, but loops are slow because the same lines are translated again and again
    Bytecode compiler with a virtual machineThe program is compiled to bytecode, then a virtual machine interprets the bytecodePython, Lua, the first versions of JavaBytecode runs on any computer that has the virtual machine, at a middle speed
    Just in time compilerBytecode is interpreted at first, and the parts that run often are compiled to machine code while the program runsJava today, C#, JavaScript in every major browser, PyPy for PythonFast for long running programs, but it uses extra memory and takes time to warm up

    Notice that a language is not really compiled or interpreted. Those words describe a particular implementation of the language. The standard version of Python, called CPython, compiles to bytecode and interprets it, while PyPy runs the same Python code with a just in time compiler. Interpreters exist for C, and compilers exist for languages usually thought of as interpreted. Python 3.13, released in 2024, even added an experimental just in time compiler to CPython, though it is switched off in the standard build. Compilers matter in artificial intelligence too. PyTorch, the library behind many AI models, has its own compiler that turns Python model code into faster code, and our analysis of depyf, a tool for looking inside the PyTorch compiler, shows researchers reading the bytecode that compiler produces.

    Lab 4 compares three strategies on the same five line loop. The time units are invented to keep the arithmetic easy. A plain interpreter spends 4 units translating each line and 1 unit running it, every single pass. A compiler spends 6 units per line translating, once, and then 1 unit per line per pass. The JIT interprets for the first three passes, decides the loop is hot, compiles it, and from then on runs at compiled speed.

    $$\text{interpreter} = 25n \qquad \text{compiler} = 30 + 5n \qquad \text{compiler wins when } 30 + 5n < 25n \text{, that is } n > 1.5$$
    Lab 4. The racethree ways to run the same loop
    
      

    translating running error found

    0interpreter, units
    0compiler, units
    0JIT, units

    Run the loop once and the interpreter wins, 25 units against 35, because the compiler spent 30 units translating before a single line ran. The JIT ties with the interpreter, since it never ran the loop often enough to compile it. Run it twice and the compiler already wins, 40 against 50, exactly as the formula predicts. At ten passes the gap is large, 250 for the interpreter, 80 for the compiler and 140 for the JIT, and at fifty passes the JIT finishes at 340, close to the compiler’s 280, while the interpreter needs 1250.

    Two results deserve a second look. With four passes the JIT comes last, at 110 units, because it paid to compile code that then ran only once more. Real JITs face the same gamble and use counters to guess which code will keep running. And look at when each lane finishes its first line. The interpreter and the JIT produce a result at 5 units, while the compiler makes the user wait until 31. That quick start is why a JIT begins by interpreting. People notice a slow start much more than they notice a slightly slower finish.

    Now tick the typo on line 4. The line by line interpreter runs lines 1, 2 and 3, changing the running total and count, before it reaches the mistake and stops, leaving the data half updated. The compiler finds the error while translating and refuses to run anything at all. The JIT lane behaves like the compiler, because Java and JavaScript, like Python, check a whole file for syntax errors before any of it runs. The companion code proves this for Python with a file whose first line would print a message. The message never appears.

    Teacher note, timing it for real

    The race uses invented units, so finish the period with real numbers. The companion code asks Python to translate and run the same expression 20,000 times, once by translating it from text every time and once by translating it a single time and reusing the result. On an ordinary laptop the second approach is dozens of times faster. Ask students which lane of Lab 4 each approach resembles, and why.

    Errors, and when each kind is found

    The stages of translation explain the three kinds of error every programmer meets. A syntax error breaks the grammar of the language, so the lexer or parser finds it before the program runs, as long as the language checks the whole file first. A runtime error happens while the program is running, when an instruction cannot be carried out, such as dividing by zero or using a name that has no value. A logic error is a program that runs without complaint and gives the wrong answer, and no translator can ever find it, because the program says exactly what the programmer wrote.

    Kind of errorExampleWho finds itWhen
    Syntax errortotal = (price * 3 with a missing bracketThe parserWhile translating, before Python runs any line of the file
    Runtime errory * 2 when y has no value, or dividing by zeroThe interpreter or the running programOnly when that line is reached
    Logic errora + b / 2 written for the average of a and bOnly a person, through testingWhen someone notices the wrong answer

    The logic error in the table connects straight back to the parse tree. With a as 6 and b as 2, a + b / 2 gives 7, because division sits lower in the tree, while the intended (a + b) / 2 gives 4. Students can type both into Lab 2 and see two different trees. The parser did its job perfectly both times. It simply cannot know what the programmer meant.

    Key takeaway

    Syntax errors are caught while translating, runtime errors only when the bad line runs, and logic errors never by the computer at all. Knowing which stage catches which mistake makes error messages far less mysterious.

    Misconceptions students bring to class

    • Python is not compiled at all. CPython compiles every file to bytecode before running it, and often saves that bytecode in a folder called __pycache__ so the next run can skip the work.
    • A language is either compiled or interpreted. These are properties of an implementation, not of the language. The same Python program can run on CPython or on PyPy, which uses a JIT.
    • The computer understands my code. The processor only ever runs machine code. Everything else is translated first by programs other people wrote.
    • If a program compiles, it is correct. Compiling only proves the grammar is right. Logic errors, such as the average example, pass through every stage untouched.
    • Interpreted programs are always slow. JIT compilers make JavaScript and Java fast, and Python programs often hand heavy work to libraries such as NumPy that are written in compiled languages.
    • Tokens in a compiler are the same as tokens in a chatbot. Both split text into pieces, but a lexer uses exact rules from the language definition, while a language model uses a vocabulary learned from huge amounts of text.

    Where this lesson simplifies the truth

    The tiny language in the labs has only numbers, names and four operators. A real language adds statements, loops, functions, types and much more, and its grammar runs to many pages. Real compilers also have a stage this lesson skips, called semantic analysis, which checks things the grammar cannot, such as whether a name has been declared or whether two values have types that can be added. Most real parsers are produced by careful hand writing or by tools that generate parsers from a grammar, and they work hard to give helpful error messages and to keep going after the first mistake.

    The stack machine in Lab 3 ignores memory, jumps and function calls, which real bytecode needs. Real code generators target registers on the processor and spend a great deal of effort on deciding which value lives in which register. The race in Lab 4 uses invented time units and a fixed rule for when code becomes hot, while real JITs measure behavior as the program runs and can even undo a compilation when their guesses turn out wrong. Finally, the exact bytecode names in the companion code depend on the version of Python, and the printed listing will look slightly different on older or newer versions.

    Bringing it all together

    The main achievement of this lesson is that students can now follow a line of code all the way down. They can split it into tokens, draw the tree that decides the order of operations, turn the tree into instructions for a stack machine, and explain where those instructions go next. The word compile is no longer a button in an editor. It is a chain of stages they have carried out by hand.

    The conceptual shift is from seeing code as something the computer simply understands to seeing it as text that other programs must translate. Translation can happen all at once, piece by piece, or in a clever mixture, and each choice trades the time spent waiting to start against the time spent running. The race in Lab 4 puts numbers on that tradeoff, and the typo version shows the other benefit of translating first, which is that mistakes are found before they can damage any data.

    The ideas connect the whole series. The tokens, tree and stack are the strings, recursion and data structures of earlier lessons doing real work. The instructions at the end are the fetch and execute steps from How a Computer Works, and the program that runs them is a process scheduled by the operating system from the previous lesson. Even Databases, SQL and Your Data fits, since every SQL query is parsed into a tree and turned into a plan before the database runs it.

    The lesson has honest limits. It does not show how a compiler handles loops, functions or types, or how a real code generator allocates registers. Those topics fill university courses, and the free book in the links below builds a complete language from nothing for anyone who wants to keep going.

    A natural next lesson is how programmers find and fix the logic errors no translator can catch, through testing and debugging. For now, when Sana’s Python program answers instantly and Hamza’s robot waits for its compiler, students can explain exactly what each machine is doing behind the screen.

    Companion Python code for the classroom

    The program below builds a complete tiny language in about two hundred lines, using only modules that come with Python. It contains a lexer, a recursive descent parser, a tree walking interpreter, a constant folding optimizer, a code generator and a stack virtual machine. It then turns to Python itself, prints the real bytecode for a small function, shows that a syntax error stops a file before its first line runs, and times translating once against translating every time.

    cc_lesson_code.py  ·  Python 3  ·  no extra libraries
    # How Compilers and Interpreters Work, companion code for the aitrendblend lesson
    # Runs on any Python 3 installation. No extra libraries needed.
    # We build a tiny language for arithmetic with variables, then compare it with Python itself.
    import dis
    import re
    import time
    
    # ---------------------------------------------------------------------------
    # Part 1. The lexer turns characters into tokens
    # ---------------------------------------------------------------------------
    TOKEN_SPEC = [
        ("NUMBER", r"\d+(?:\.\d+)?"),
        ("NAME", r"[A-Za-z_]\w*"),
        ("OP", r"[+\-*/]"),
        ("ASSIGN", r"="),
        ("LPAREN", r"\("),
        ("RPAREN", r"\)"),
        ("SPACE", r"[ \t]+"),
        ("ERROR", r"."),
    ]
    LEXER = re.compile("|".join(f"(?P<{name}>{pattern})" for name, pattern in TOKEN_SPEC))
    
    
    def tokenize(text):
        tokens = []
        for m in LEXER.finditer(text):
            kind, value = m.lastgroup, m.group()
            if kind == "SPACE":
                continue
            if kind == "ERROR":
                raise SyntaxError(f"lexical error, the character {value!r} is not part of this language")
            tokens.append((kind, value))
        return tokens
    
    
    line = "total = price * 3 + tax"
    toks = tokenize(line)
    print("Tokens:", toks)
    try:
        tokenize("cost = $5")
    except SyntaxError as err:
        print("Tokenizing 'cost = $5' fails:", err)
    print()
    
    # ---------------------------------------------------------------------------
    # Part 2. The parser builds a tree that respects precedence
    # ---------------------------------------------------------------------------
    class Parser:
        """Recursive descent. expr = term (('+'|'-') term)*, term = factor (('*'|'/') factor)*"""
    
        def __init__(self, tokens):
            self.toks, self.i = tokens, 0
    
        def peek(self):
            return self.toks[self.i] if self.i < len(self.toks) else ("END", "")
    
        def take(self, kind=None, value=None):
            tok = self.peek()
            if (kind and tok[0] != kind) or (value and tok[1] != value):
                raise SyntaxError(f"syntax error at {tok[1] or 'end of line'!r}")
            self.i += 1
            return tok
    
        def expr(self):
            node = self.term()
            while self.peek()[1] in ("+", "-"):
                op = self.take()[1]
                node = (op, node, self.term())          # left associative
            return node
    
        def term(self):
            node = self.factor()
            while self.peek()[1] in ("*", "/"):
                op = self.take()[1]
                node = (op, node, self.factor())
            return node
    
        def factor(self):
            kind, value = self.peek()
            if kind == "NUMBER":
                self.take()
                return ("num", float(value) if "." in value else int(value))
            if kind == "NAME":
                self.take()
                return ("var", value)
            if kind == "LPAREN":
                self.take()
                node = self.expr()
                self.take("RPAREN")
                return node
            raise SyntaxError(f"syntax error at {value or 'end of line'!r}, expected a number, a name or (")
    
        def parse(self):
            node = self.expr()
            if self.peek()[0] != "END":
                raise SyntaxError(f"syntax error at {self.peek()[1]!r}")
            return node
    
    
    def parse(text):
        return Parser(tokenize(text)).parse()
    
    
    def show_tree(node, indent=""):
        if node[0] == "num" or node[0] == "var":
            return indent + str(node[1]) + "\n"
        return indent + node[0] + "\n" + show_tree(node[1], indent + "   ") + show_tree(node[2], indent + "   ")
    
    
    print("Parse tree for 2 + 3 * 4")
    print(show_tree(parse("2 + 3 * 4")))
    
    # ---------------------------------------------------------------------------
    # Part 3. An interpreter walks the tree directly
    # ---------------------------------------------------------------------------
    OPS = {"+": lambda a, b: a + b, "-": lambda a, b: a - b, "*": lambda a, b: a * b, "/": lambda a, b: a / b}
    
    
    def evaluate(node, env):
        if node[0] == "num":
            return node[1]
        if node[0] == "var":
            if node[1] not in env:
                raise NameError(f"runtime error, {node[1]} has no value")
            return env[node[1]]
        return OPS[node[0]](evaluate(node[1], env), evaluate(node[2], env))
    
    
    ENV = {"price": 20, "tax": 5, "x": 7, "a": 6, "b": 2}
    for src in ["2 + 3 * 4", "(2 + 3) * 4", "10 - 4 - 3", "price * 3 + tax"]:
        print(f"{src:<18} = {evaluate(parse(src), ENV)}")
    print()
    
    # ---------------------------------------------------------------------------
    # Part 4. A compiler turns the tree into stack machine instructions
    # ---------------------------------------------------------------------------
    NAMES = {"+": "ADD", "-": "SUB", "*": "MUL", "/": "DIV"}
    
    
    def fold(node):
        """Optimizer. Work out any part of the tree that uses only numbers."""
        if node[0] in ("num", "var"):
            return node
        left, right = fold(node[1]), fold(node[2])
        if left[0] == "num" and right[0] == "num":
            return ("num", OPS[node[0]](left[1], right[1]))
        return (node[0], left, right)
    
    
    def compile_tree(node, optimize=False):
        if optimize:
            node = fold(node)
        code = []
    
        def gen(n):
            if n[0] == "num":
                code.append(f"PUSH {n[1]}")
            elif n[0] == "var":
                code.append(f"LOAD {n[1]}")
            else:
                gen(n[1])
                gen(n[2])
                code.append(NAMES[n[0]])
        gen(node)
        return code
    
    
    def run_vm(code, env):
        stack, deepest = [], 0
        for ins in code:
            parts = ins.split()
            if parts[0] == "PUSH":
                stack.append(float(parts[1]) if "." in parts[1] else int(parts[1]))
            elif parts[0] == "LOAD":
                stack.append(env[parts[1]])
            else:
                b, a = stack.pop(), stack.pop()
                stack.append(OPS[{v: k for k, v in NAMES.items()}[parts[0]]](a, b))
            deepest = max(deepest, len(stack))
        return stack.pop(), deepest
    
    
    for src in ["2 + 3 * 4", "price * 3 + tax", "x * (2 + 3)", "(a + b) * (a - b)"]:
        plain = compile_tree(parse(src))
        opt = compile_tree(parse(src), optimize=True)
        result, depth = run_vm(plain, ENV)
        print(f"{src:<18} -> {', '.join(plain)}")
        if opt != plain:
            print(f"{'optimized':<18} -> {', '.join(opt)}")
        print(f"{'':<18}    result {result}, deepest stack {depth}")
    print()
    
    # ---------------------------------------------------------------------------
    # Part 5. Python does the same thing. Look at its real bytecode.
    # ---------------------------------------------------------------------------
    def bill(price, tax):
        total = price * 3 + tax
        return total
    
    
    print("Python's own bytecode for total = price * 3 + tax")
    dis.dis(bill)
    print()
    
    # A syntax error anywhere stops the whole file before a single line runs,
    # because Python compiles the file first.
    program = "print('this line never runs')\ntotal = (price * 3\n"
    try:
        compile(program, "lesson.py", "exec")
    except SyntaxError as err:
        print("Python refused to start:", err.msg, "on line", err.lineno)
    print()
    
    # Translating once and running many times beats translating every time.
    src = "price * 3 + tax"
    N = 20000
    t0 = time.perf_counter()
    for _ in range(N):
        eval(src, {}, ENV)                      # translate and run, every single time
    t_every = time.perf_counter() - t0
    code_obj = compile(src, "<lesson>", "eval")
    t0 = time.perf_counter()
    for _ in range(N):
        eval(code_obj, {}, ENV)                 # translated once, now only run
    t_once = time.perf_counter() - t0
    print(f"{N:,} runs, translating every time {t_every * 1000:.0f} ms, "
          f"translating once {t_once * 1000:.0f} ms, about {t_every / t_once:.0f} times faster")
    print()
    
    # ---------------------------------------------------------------------------
    # Part 6. The race from Lab 4, as a formula (time units are made up)
    # ---------------------------------------------------------------------------
    LINES, TRANSLATE_I, RUN, TRANSLATE_C, HOT = 5, 4, 1, 6, 3
    
    
    def race(n):
        interpreter = LINES * (TRANSLATE_I + RUN) * n
        compiler = LINES * TRANSLATE_C + LINES * RUN * n
        jit = interpreter if n <= HOT else LINES * (TRANSLATE_I + RUN) * HOT + LINES * TRANSLATE_C + LINES * RUN * (n - HOT)
        return interpreter, compiler, jit
    
    
    for n in (1, 2, 4, 10, 50):
        i, c, j = race(n)
        print(f"loop runs {n:>2} times | interpreter {i:>4} | compiler {c:>4} | JIT {j:>4}")
    first = {"interpreter": TRANSLATE_I + RUN, "compiler": LINES * TRANSLATE_C + RUN, "JIT": TRANSLATE_I + RUN}
    print("first line finishes at", ", ".join(f"{k} {v}" for k, v in first.items()))
    print()
    
    # ---------------------------------------------------------------------------
    # Self checks. If these pass, the lesson numbers are reproduced.
    # ---------------------------------------------------------------------------
    assert len(toks) == 7
    assert evaluate(parse("2 + 3 * 4"), ENV) == 14
    assert evaluate(parse("(2 + 3) * 4"), ENV) == 20
    assert evaluate(parse("10 - 4 - 3"), ENV) == 3
    assert evaluate(parse("price * 3 + tax"), ENV) == 65
    assert compile_tree(parse("2 + 3 * 4")) == ["PUSH 2", "PUSH 3", "PUSH 4", "MUL", "ADD"]
    assert compile_tree(parse("x * (2 + 3)"), optimize=True) == ["LOAD x", "PUSH 5", "MUL"]
    assert run_vm(compile_tree(parse("(a + b) * (a - b)")), ENV)[0] == 32
    assert race(1) == (25, 35, 25) and race(10) == (250, 80, 140)
    try:
        parse("2 + * 3")
        raise AssertionError("should have failed")
    except SyntaxError:
        pass
    print("All checks passed.")
    

    When you run it, the first line lists the 7 tokens of total = price * 3 + tax, and the dollar sign example fails with a lexical error. The interpreter prints 14, 20, 3 and 65, matching Lab 2. The compiler prints PUSH 2, PUSH 3, PUSH 4, MUL and ADD for the first expression, folded to PUSH 14, and the deepest stack of 3 matches Lab 3. On Python 3.13 the bytecode listing shows LOAD_FAST, LOAD_CONST and BINARY_OP in the same order as our stack code, ending with STORE_FAST total. The syntax error demo prints that a bracket was never closed on line 2, so the print on line 1 never ran. The timing line will differ on every computer, and on our test machine translating once was about 35 times faster. The race table reproduces Lab 4, and the last line should read All checks passed. Ask students to add a power operator to the lexer, parser and virtual machine, and to decide where it belongs in the grammar.

    Check your understanding

    Six questions cover the whole lesson. Choose an answer for each and press Check answers to see your score and a short explanation for each.

    Lab 5. Quick quizsix questions

    Frequently asked questions

    What is the difference between a compiler and an interpreter?

    A compiler translates a whole program into machine code before it runs, and the result can then run many times without translating again. An interpreter translates and carries out the program piece by piece while it runs. Compiled programs usually run faster, while interpreted programs start at once and are easier to change and test.

    Is Python a compiled or an interpreted language?

    Both, in a sense. The standard version, CPython, first compiles each file into bytecode, a list of simple instructions, and then a virtual machine interprets that bytecode. That is why a syntax error anywhere in a file stops it before the first line runs. PyPy runs the same Python code with a just in time compiler.

    What is a JIT compiler?

    A just in time compiler starts by interpreting a program, watches which parts run most often, and compiles those hot parts to machine code while the program is running. Java, C# and JavaScript in web browsers all use JIT compilers, which is how they start quickly and still run long programs fast.

    What does a lexer do in a compiler?

    The lexer, also called a tokenizer, is the first stage. It reads the characters of the source code and groups them into tokens such as names, numbers, operators and brackets, throwing away spaces and comments. It reports an error if it meets a character that is not part of the language.

    What is a parse tree and why does it matter?

    A parse tree shows the structure of a piece of code, with each operator as a node and its inputs below it. The parser builds it by checking the tokens against the grammar of the language. Operations lower in the tree happen first, so the tree is what makes 2 + 3 * 4 equal 14 rather than 20.

    What is bytecode?

    Bytecode is a compact list of simple instructions for a virtual machine rather than for a real processor. Python, Java and C# all compile to bytecode. Because the virtual machine is the same on every computer, the same bytecode can run on Windows, macOS, Linux or a phone.

    Take the lesson further

    Read Crafting Interpreters, a complete book its author gives away free online, which builds a real programming language step by step. Then open Python’s guide to the dis module and look at the bytecode of your own programs.

    Free book, Crafting Interpreters Python dis module guide

    Sources. Grace M. Hopper, The Education of a Computer, Proceedings of the ACM National Meeting, 1952. John Backus and colleagues, The FORTRAN Automatic Coding System, Western Joint Computer Conference, 1957. John McCarthy, Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, Communications of the ACM, 1960. John Aycock, A Brief History of Just in Time, ACM Computing Surveys, 2003. Python Enhancement Proposal 744, JIT Compilation, 2024. Alfred V. Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman, Compilers, Principles, Techniques and Tools. Robert Nystrom, Crafting Interpreters.

    This lesson is based on standard compiler and programming languages teaching material and the classroom experience of the author. The expressions, variable values, time units and programs in the labs and code are invented for practice.

    Related reading on aitrendblend

    Leave a Comment

    Your email address will not be published. Required fields are marked *