1.2.2 - The stages of compilation

Lexical analysis recognises tokens

Lexical analysis reads source characters and groups them into tokens, the meaningful units of the language. Token categories include identifiers, keywords, literals, operators and punctuation. An identifier names something, such as a variable; a literal writes a value directly, such as 12 or "Ready".

For a small teaching language using = for assignment, consider:

total = price + 12

The token sequence is identifier total, assignment operator =, identifier price, addition operator +, integer literal 12. The lexer recognises each identifier as a whole rather than treating its letters as separate program instructions. It can record identifiers and associated information in a symbol table, which later stages use and extend to track properties such as type, scope or storage information.

Comments and insignificant spacing can be removed from the representation because they do not affect execution. This does not mean every space is disposable: spaces inside "New York" are part of the string value, and indentation is significant in languages such as Python. The lexer follows the actual language's rules. An illegal character outside a valid token, or an unterminated string, can be a lexical error.

Syntax analysis checks grammatical structure

Syntax analysis, or parsing, checks whether the token sequence follows the language's grammar. Recognising individual tokens is not enough: all the tokens in total = + * 12 can be recognised, but their arrangement cannot form a valid expression in this teaching language.

For total = price + 12, the parser can build an abstract syntax tree. Its assignment node has total as the destination and an addition expression as the value. The addition has price and 12 as its two operands. The tree represents relationships, rather than preserving every original space or punctuation mark.

Precedence changes those relationships. In total = price + 2 * 3, multiplication binds more tightly, so the addition's right operand is the multiplication of 2 and 3. With (price + 2) * 3, the outer operation is multiplication. These different trees give different answers when price is 5: 11 and 21 respectively.

Missing brackets, misplaced operators or a missing required terminator can cause syntax errors. The compiler reports errors so the programmer can repair the source before generating a valid target program. A compiler may collect several errors, but one early mistake can also produce later misleading messages. Semantic checks, such as whether an identifier has been declared or operands have compatible types, examine meaning beyond grammar; they are often performed alongside later parsing stages. A syntactically valid program can still use the wrong formula.

Code generation turns structure into target operations

Code generation uses the checked program structure to produce target instructions, commonly object code. It chooses operations and locations that implement the source behaviour. Variable and type information helps it choose appropriate instructions and storage. The abstract syntax tree is input to this process; it is not itself an executable machine program.

For total = price + 12, a conceptual target sequence could be:

LOAD price
ADD 12
STORE total

This is an illustrative instruction sequence, not the Little Man Computer instruction set or a runnable program. The sequence reads price, computes the sum and stores it in total. A real generator must use its target's actual instruction set and address rules. One source statement can need several instructions.

The resulting object module may still need a linker to connect references to other modules and libraries. The loader later places the executable in memory. Code generation is therefore not the same as linking, loading or executing. Target instructions that faithfully implement a wrong source formula still give the wrong result.

Optimisation improves code while preserving behaviour

Optimisation transforms a program representation to improve a property such as execution time or code size while preserving the required observable behaviour. It can happen to an intermediate representation before target generation and to target code afterwards. The four named stages describe useful responsibilities, rather than a rule that every compiler has exactly four single passes.

Constant folding replaces a calculation whose operands are known constants with its result. In bonus = 4 * 5, the compiler can use 20 instead of performing the multiplication at runtime. A repeated expression can sometimes be calculated once and reused if its inputs cannot change between uses. Unreachable code can sometimes be removed. Each transformation needs evidence that the behaviour is unchanged.

For example, these two assignments have the same final value if multiplication has the stated ordinary integer meaning:

allowance = 6 * 4
allowance = 24

They are alternatives, not two consecutive lines required in one program. By contrast, deleting print("Saved") changes visible output even if its return value is unused. Reusing read_sensor() instead of calling it twice can also change behaviour: the input value or a side effect may differ between calls. Optimisation does not grant permission to erase meaningful actions.

Smaller or faster target code can help deployment and repeated execution, but an optimisation may increase compilation time or trade size against speed. There is no universal best transformation. A compiler also cannot infer every intended requirement: if the programmer wrote addition when multiplication was required, an efficient addition remains the wrong algorithm.