--- title: 'Compilation Stages' source: 'https://academia.sh/en/courses/how-computers-work/compilation-stages' course: 'How Computers Work' language: en updated: '2026-08-17T18:08:06+00:00' license: 'CC BY-SA 4.0' --- # Compilation Stages The stages of lexical analysis, parsing, semantic checking, intermediate representation, and code generation. The previous lesson defined three models based on when translation happens. This lesson opens up the translation itself: what steps does source text pass through on its way to becoming instructions? The steps are nearly the same across almost every implementation. An interpreter and a compiler do the same work in the early stages; the paths diverge at the final generation step. ## Lexical Analysis The first stage splits the character sequence into the smallest meaningful units. These units are called **tokens**. The line `total = 3 + 4 * 2` splits into the following tokens: | Token | Type | |---|---| | `total` | name | | `=` | assignment operator | | `3` | number literal | | `+` | addition operator | | `4` | number literal | | `*` | multiplication operator | | `2` | number literal | At this stage, whitespace and comments are discarded, and number literals are converted from character sequences into numeric values. The lexical analyzer does not concern itself with structure: `3 + * 4` also tokenizes without a problem, because each token is valid on its own. Errors produced at this stage are cases such as characters that do not belong to the language's alphabet, or unterminated string literals. ## Parsing The second stage checks whether the tokens conform to the language's grammar and, if they do, builds the structure as a tree. This tree is called an **abstract syntax tree**. The tree for the expression `3 + 4 * 2` embeds operator precedence in its structure: ``` + / \ 3 * / \ 4 2 ``` That multiplication happens before addition is encoded by its node sitting deeper in the tree: a node above cannot be evaluated until the node below it has been. Precedence rules are enforced through how the grammar is written; there is no separate "precedence check" step. Errors from the parsing stage relate to the order of tokens: an unclosed parenthesis, a missing operand, an unexpected keyword. ## Semantic Checking Not every syntactically correct program is meaningful. The line `total = undefined_name + 1` conforms to the grammar, but it cannot execute if it is unknown what the name refers to. At this stage the compiler builds a **symbol table**: it records where each name is defined, its type, and its scope. The tree is checked against this table: - Are the names used defined? - Are the operand types of the operators compatible? - Is the type conversion in assignments valid? - Are the argument count and types correct in function calls? In statically typed languages, most of these checks happen during compilation. In dynamically typed languages, type information is carried on values at run time; the same errors surface when the corresponding line executes. The two approaches differ in **when** the error is seen. ## Intermediate Representation and Optimization The tree can be translated directly into machine code, but most compilers insert a layer in between: an **intermediate representation** that is not tied to any specific processor. The intermediate representation has two benefits. Optimizations are written here independently of the target machine; and for $m$ languages and $n$ target architectures, it is enough to write $m + n$ components, not $m \times n$. Typical optimizations at this level: - **Constant folding:** The expression `3 + 4 * 2` is computed during compilation rather than at run time, and `11` is put in its place. - **Dead code elimination:** Computations whose results are used nowhere are removed. - **Common subexpression elimination:** A repeated occurrence of the same computation is performed once and cached. - **Loop-invariant code motion:** A computation that does not change across a loop is moved before the loop. The limit of optimization is leaving the program's **observable behavior** unchanged. This explains why floating-point arithmetic cannot be freely reordered: addition lacks the associative property, so changing the order can change the result. ## Code Generation The final stage translates the intermediate representation into the target instruction set. Architecture-specific decisions are made here: - **Instruction selection:** The same operation can be carried out with more than one instruction sequence; the cheapest is chosen. - **Register allocation:** Which values are kept in registers and which are moved to memory. Because the number of registers is limited, this is one of the compiler's most difficult tasks. - **Instruction scheduling:** Instructions can be reordered so that the pipeline does not sit idle. One more external rule applies at this stage: the **calling convention**. It specifies which registers or stack locations hold arguments, where the return value is carried, and which registers the callee must preserve. Separately compiled files can call one another only if all of them follow the same convention; the convention is a definition of the target platform, not of the compiler. Interpreters skip this stage: they execute the tree or the bytecode directly. In the virtual machine model, the target is the virtual machine's instruction set, not a real processor. ## Error Reporting and Recovery A compiler can stop and exit at the first error. This behavior is inefficient for the developer: every error would require a separate compilation run. For this reason, parsers apply **error recovery** — they report the error, skip tokens up to a consistent point, and continue parsing. The cost of recovery is cascading errors: a single unclosed parenthesis can make the following constructs appear in the wrong position and produce dozens of additional error messages. The practical rule: the first message is the most reliable one; the ones after it may be derivatives of the first. The quality of an error message is also a design matter. A good message says three things: what the problem is, where it occurred, and what was expected. To this end, the parser carries the source location (line and column) on every node it produces; this information is preserved throughout the tree and used again during semantic checking. ## Seeing the Stages in Code The following program implements the first two stages on a small expression language and demonstrates the third stage using the standard library: ```python import re, ast PATTERN = re.compile(r"\s*(?:(\d+)|([A-Za-z_]\w*)|(.))") def tokenize(text: str) -> list[tuple[str, str]]: """Splits source text into (type, value) pairs.""" tokens = [] for number, name, symbol in PATTERN.findall(text): if number: tokens.append(("number", number)) elif name: tokens.append(("name", name)) elif symbol.strip(): tokens.append(("symbol", symbol)) return tokens print(tokenize("total = 3 + 4 * 2")) # [('name', 'total'), ('symbol', '='), ('number', '3'), ('symbol', '+'), # ('number', '4'), ('symbol', '*'), ('number', '2')] tree = ast.parse("3 + 4 * 2", mode="eval") print(ast.dump(tree.body, annotate_fields=False)) # BinOp(Constant(3), Add(), BinOp(Constant(4), Mult(), Constant(2))) ``` The `ast.dump` output is the text form of the tree from the parsing section: the outer node is addition, and its right operand is the multiplication node. Precedence is built into the shape of the tree. In the same program, the lexical analyzer can be shown to tokenize `3 + * 4` without any problem, while `ast.parse` raises a syntax error on the same input; this directly demonstrates that the two stages ask different questions. ## Summary - Lexical analysis splits the character sequence into tokens and discards whitespace. - Parsing checks whether the tokens conform to the grammar and builds the abstract syntax tree; operator precedence is encoded in the shape of the tree. - Semantic checking tests name and type compatibility against the symbol table; statically and dynamically typed languages perform this check at different times. - The intermediate representation makes optimizations independent of the target architecture and reduces the number of language-architecture combinations. - Code generation makes the decisions of instruction selection, register allocation, and instruction scheduling. - A compilation error is read more quickly when the stage that produced it is known. ## Next Step Code generation produces a separate output for each source file. But a program does not consist of a single file, and the libraries it uses have been compiled elsewhere. The next lesson takes up how these pieces are linked into a single executable whole and how they are loaded into memory at run time.