Skip to content
Tutorials Center
My learning

Topics

Lesson 3 of 61 ยท Getting Started

The Phases of a Compiler

Walk through every compiler phase, from lexical analysis to code generation, and run a toy pipeline that prints the output of each stage.

A compiler is too large to write as one big function, so engineers split it into phases. Each phase takes one representation of the program, transforms it, and hands a new representation to the next phase. Text becomes tokens, tokens become a tree, the tree becomes simple instructions, and the instructions become machine code. Because every phase has one clear job, you can build, test and improve them one at a time.

This lesson is a guided tour. You will meet each phase, see what goes in and what comes out, and then run a miniature compiler that prints the result of every stage. Later chapters take one phase at a time and build it properly. If the term is new, first read what a compiler is.

The big picture

The phases fall into three groups. The front end understands the source language. The middle end improves a language-independent form of the program. The back end knows the target machine.

flowchart TD
    A["Source text"] --> B["Lexical analysis<br/>(tokens)"]
    B --> C["Syntax analysis<br/>(parse tree / AST)"]
    C --> D["Semantic analysis<br/>(checked AST)"]
    D --> E["Intermediate code<br/>(three-address code)"]
    E --> F["Optimization<br/>(better IR)"]
    F --> G["Code generation<br/>(target code)"]
    ST["Symbol table"] -.-> D
    ST -.-> E
    ER["Error handler"] -.-> B
    ER -.-> C
    ER -.-> D

The pipeline from text to target code. The symbol table and the error handler serve many phases at once.

Why split the work this way? Because the parts are interchangeable. A Rust front end and a C front end can feed the same optimizer, and one optimizer can feed code generators for Intel, ARM and WebAssembly. With L languages and M machines you write L + M pieces instead of L x M complete compilers.

Phase 1: lexical analysis

The lexer (or scanner) reads characters and groups them into tokens, the words of the language. It discards spaces and comments. For let a = 2 * 3 + 4 it produces tokens like LET, ID(a), =, NUM(2), *, NUM(3), +, NUM(4). You will write lexers in Lexical Analysis.

Phase 2: syntax analysis

The parser checks that the tokens follow the grammar and builds a tree that shows how they nest. The tree for 2 * 3 + 4 must put 2 * 3 below the +, because multiplication binds tighter. The result is usually an abstract syntax tree (AST) that keeps only the meaningful structure. Grammars and parsers fill two whole chapters, starting with context-free grammars.

Phase 3: semantic analysis

A program can follow the grammar perfectly and still be meaningless. print zebra is grammatical, but zebra was never declared. The semantic analyzer checks rules that a grammar cannot express: names must be declared, types must fit ("a" * "b" is nonsense in most languages), a function gets the right number of arguments. It also decorates the tree with information such as types, using the symbol table.

Phase 4: intermediate code generation

The compiler now rewrites the tree into a simple, uniform form called an intermediate representation (IR). A popular choice is three-address code, where each instruction has at most one operator and uses at most three names:

TEXT
t1 = 2 * 3
t2 = t1 + 4
a  = t2

Complicated nested expressions become flat sequences. This form belongs to neither the source language nor the machine, which makes it a perfect place to optimize. See intermediate representations.

Phase 5: optimization

An optimizer rewrites the IR so that the program does the same thing with less work. It can fold 2 * 3 into 6 at compile time, delete a multiplication by 1, or remove code whose result is never used. Optimization must never change what the program means. That rule is what makes it hard. The chapter on intermediate code and optimization goes deep.

Phase 6: code generation

The code generator maps IR instructions to instructions of the target machine, chooses which values live in which registers, and lays out memory. Different back ends produce different output from the same IR: x86-64 assembly, ARM assembly, JVM bytecode or WebAssembly.

The two helpers

Two components are not phases but are used by many of them:

  • Symbol table. A data structure that records every name in the program (variables, functions, types) with its type, scope and other attributes. The parser or semantic analyzer fills it, and later phases read it.
  • Error handler. Each phase can find problems. A lexer meets a character such as # that belongs to no token; a parser meets a missing operand; the semantic analyzer meets an undeclared name. A good compiler reports the problem clearly, with a position, and keeps going to find more errors instead of stopping at the first one.

Analysis and synthesis

Another useful way to split the pipeline is in two halves. The analysis half (lexing, parsing, semantic analysis) breaks the source into pieces and builds an understanding of it. The synthesis half (IR, optimization, code generation) builds the target program from that understanding. Front end corresponds roughly to analysis, back end to synthesis.

Real compilers also combine phases. A single-pass compiler may parse and generate code in one sweep without ever building a tree, and a modern parser often calls the lexer on demand rather than lexing the whole file first. The phases describe responsibilities, not necessarily separate programs.

A toy pipeline you can run

The code below is a complete (very small) compiler for a language with let, print, numbers, variables and the operators +, -, *. It prints the output of every phase for a three-line program. Read it from top to bottom: the comments number the phases to match this lesson. Do not worry about the details of each function yet, because later lessons rebuild every part carefully.

Python Every phase on one program

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Follow a = 2 * 3 + 4 down the page. It appears as tokens, then as a nested tree, then as the instructions t1 = 2 * 3, t2 = t1 + 4, a = t2. After optimization it is just a = 10, because the optimizer did the arithmetic during compilation. The line let b = n * 1 shrinks to a copy of n. The generated machine code loads and stores through an imaginary one-register machine.

The two run lines at the bottom check the compiler's contract: the original and the optimized program print the same thing (15 when n is 5). If an optimization ever changed that answer, it would be a miscompilation, the worst kind of compiler bug.

Notice also the last line, where a program that mentions zebra is rejected by the semantic phase before any code is generated. The program never reaches the later phases.

Errors belong to phases

Each phase detects its own kind of mistake. The next example feeds four inputs to a miniature front end and shows which phase complains.

Python Which phase reports which error?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The text price + # 3 fails first, in the lexer, because # is not part of any token. price + + 3 has only valid tokens but breaks the grammar, so the parser objects. price + tax is grammatical, yet the semantic phase knows tax was never declared. Errors found earlier are cheaper to report and easier to explain, which is one reason compilers check as much as they can before running anything.

Passes and kinds of compilers

A phase is a logical job (lexing, parsing, optimizing). A pass is one physical sweep of the compiler over the program or over one of its representations. The two do not have to match: several phases can share a pass, and one phase can need several passes.

Single-pass (one-pass) compilers read the source once from top to bottom and generate code as they go, often without building a full tree. They are small, fast and use little memory, which mattered a great deal on early computers; classic Pascal compilers and many small embedded-language compilers work this way. The price is that nothing can be known before it is read. A name must be declared before use, which is why C needs forward declarations and header files, and why jumps to labels that appear later need backpatching. A one-pass compiler also cannot do whole-function optimization, because it has already emitted the code.

Multi-pass compilers build one or more intermediate representations and sweep over them repeatedly: one pass collects declarations, another checks types, others optimize and generate code. They accept more flexible languages (use before declaration, mutually recursive functions) and produce better code, at the cost of more time and memory. Almost every optimizing compiler is multi-pass; the intermediate representation is what lets the passes cooperate.

One pass Multi-pass
Speed of compiling fast slower
Memory little (no whole-program tree) more
Language rules declare before use flexible ordering
Optimization almost none extensive
Typical use small languages, assemblers, quick tools production compilers

The program below shows the main practical difference on a tiny language with func and call lines. The one-pass compiler fails on calls to functions defined later, the two-pass compiler first collects all declarations and succeeds, and a C-style forward declaration rescues the one-pass compiler. The last part is an incremental build that recompiles only what changed.

Python One pass, two passes, incremental builds

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The incremental part uses a content hash per source unit, a cousin of the timestamps that make uses. Real incremental compilers track dependencies as well, so that changing a function's signature also recompiles its callers.

Other kinds of compilers

The words below describe a compiler by what it takes in, what it produces, or when it runs. They are not mutually exclusive: one tool can be a multi-pass, optimizing, cross compiler.

  • Native compiler: produces code for the machine it runs on. A cross compiler produces code for a different machine (see bootstrapping and cross compilers).
  • Source-to-source compiler (transpiler): translates one high-level language into another, as in the transpiler project.
  • Ahead-of-time (AOT) compiler versus just-in-time (JIT) compiler: compile before the program runs, or while it runs. See JIT and interpreters.
  • Self-hosting compiler: a compiler written in the language it compiles, which needs a bootstrap step.
  • Incremental compiler: recompiles only the parts that changed, for fast edit-and-run cycles.
  • Decompiler and disassembler: go in the opposite direction, from machine code back to a higher-level form.
  • Optimizing compiler: spends compile time on better code; a debugging compiler prefers fast builds and good debug information.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which phase turns a stream of characters into tokens?

    The lexer (scanner) groups characters into tokens such as identifiers, numbers and operators, and discards whitespace and comments.
  2. 2. A program uses a variable that was never declared, but every line follows the grammar. Which phase should report the error?

    Declaration rules cannot be expressed by a context-free grammar. The semantic analyzer uses the symbol table to find undeclared names.
  3. 3. Why do compilers use an intermediate representation?

    An IR is independent of both the source language and the machine, so front ends, the optimizer and back ends can be mixed and matched.
  4. 4. What is the rule every optimization must follow?

    An optimization may change how the work is done but never what the program means. Breaking that rule is a miscompilation.

Summary

  • Phases are logical, passes are physical sweeps: one-pass compilers are small and fast but need declare-before-use, multi-pass compilers optimize; incremental, cross, AOT, JIT and source-to-source compilers differ in when and what they translate.
  • A compiler is a pipeline of phases; each phase consumes one program representation and produces the next.
  • Front end: lexing, parsing, semantic analysis. Middle end: IR and optimization. Back end: code generation for a specific machine.
  • Lexing produces tokens, parsing produces a tree, semantic analysis checks names and types, the IR is a flat machine-independent form, and code generation maps it to the target.
  • The symbol table and the error handler are shared by several phases.
  • Splitting the work lets you reuse parts: L languages plus M machines need L + M components rather than L x M compilers.
  • Optimizations must preserve the meaning of the program.

Next: Meet Our Toy Language