Compiler

A compiler translates a program from one representation to another while aiming to preserve its programming language semantics. Its input might be source code or an intermediate representation; its output might be another programming language, bytecode, an intermediate representation, or machine code. Producing machine code is therefore one possible destination, rather than the definition of compilation. For example, the LLVM 20.1.0 tutorial translates an abstract syntax tree into an intermediate representation before introducing execution.^[ref]

Compilation can use an abstract syntax tree for checking and transformations such as constant folding before producing machine code. These are useful possibilities, not a compulsory sequence of separate stages for every compiler. The central distinction is between translating a program and executing its operations: a compiler can translate x*(2+3)-4 without knowing the input value of x, whereas an interpreter needs that value to produce this program expression's result.

Different representations expose different questions. Source code preserves what a programmer wrote; an abstract syntax tree exposes grouping; a type system checks permitted combinations; a stack machine makes operand movement explicit. Retaining abstract syntax tree source locations across compilation helps an error message identify the original construct even after constant folding has changed its shape. A malformed x*(2+)-4 is a programming language syntax error; an unavailable x in the valid example is instead a missing input. Locating the failing rule is more helpful than treating both as an unexplained execution failure.

Choosing target-machine instructions to implement an intermediate representation. A memory operand using register-offset addressing can cover both an address addition and a load or store; computing the full address into a temporary variable can prevent that covering and add an unnecessary instruction.

Analysis of whether two accesses may designate the same storage location. Common subexpression elimination must not reuse a previously loaded value after a store that might change that location, unless an additional argument justifies it. A saved memory address can remain valid even though a value previously loaded at that address is invalidated.

A transformation that computes a repeated program expression once and reuses its saved result when the value is known not to have changed. A repeated load can be reused only when intervening stores, calls or other changes cannot alter the relevant location. Alias analysis helps establish that fact. Maximal address sharing can be counterproductive if instruction selection could otherwise fold an address addition into register-offset addressing.

Compilation is the translation process performed by a compiler, which may include checking and transforming an abstract syntax tree. Translation can finish before execution, or happen during execution through just-in-time compilation. Reusing the translated representation can avoid repeated parsing and repeated constant folding when only the inputs change. This does not guarantee a speedup: translation itself costs work, and the choice of representation and execution mechanism matters.

Consider the program expression x*(2+3)-4 in a deliberately small programming language. Its only program identifier is x, supplied as an integer input. Its literal values are nonnegative decimal numerals, interpreted as integers. Whitespace is ignored between lexical tokens. Its context-free grammar is:

expression ::= term (("+" | "-") term)*
term       ::= factor ("*" factor)*
factor     ::= numeral | "x" | "(" expression ")"
numeral    ::= digit digit*
digit      ::= "0" | "1" | "2" | "3" | "4"
             | "5" | "6" | "7" | "8" | "9"

Here * outside quotation marks means zero or more repetitions. Repeated operators are grouped to the left, specifying operator associativity; term gives multiplication higher operator precedence than addition and subtraction. Parentheses override that grouping. There is no unary minus, variable assignment, function call, or side effect in this language. Evaluation obtains each left operand before its right operand and uses exact integer arithmetic, with no fixed-width overflow.

Lexical analysis recognizes x, *, (, 2, +, 3, ), -, 4. Parsing constructs the concrete abstract syntax tree Sub(Mul(Name(x), Add(Int(2), Int(3))), Int(4)). Parentheses have done their work by making Add a child of Mul; they need not survive as nodes. Constant folding changes this to Sub(Mul(Name(x), Int(5)), Int(4)). It cannot replace Name(x) by a literal value because the input is supplied at execution. The resulting function of the input is $f(x)=5x-4$.

A compiler for our stack machine emits LOAD x; PUSH 5; MUL; PUSH 4; SUB. LOAD x pushes the current input; PUSH n pushes the integer literal value n. Each binary instruction removes the top item as its right operand, then the next item as its left operand, and pushes the result. The instruction sequence is an intermediate representation that an interpreter can execute; no machine code has been emitted. A compact binary encoding could make it bytecode, but these printed instruction names are only a readable notation.

Why does this compilation preserve the result? A structural induction supplies a short proof outline. Translating a literal value or x appends its value to any initial stack. For a binary abstract syntax tree node, first translating the left child and then the right child appends the two operand values; the matching instruction replaces them by exactly the original operation's result. Previously present stack items remain intact. Constant folding also preserves the result because $2+3=5$ in the specified integer arithmetic. Together these facts explain agreement for every integer input, rather than merely agreement for one trial.

Compilation performed during execution, often producing machine code for subsequent execution.

A program representation used between input and final output, convenient for analysis, transformation or execution. An abstract syntax tree and bytecode can each serve this role.

A fresh internal name introduced during compilation to hold an intermediate result. Its lifetime and uses can be exposed to instruction selection and allocation of processor registers; it need not correspond to a variable named in the source.

An encoded instruction representation for a software execution mechanism. Compilation can produce bytecode that an interpreter executes.

An infrastructure project providing reusable tools for compilation and intermediate representations.