Compilation and interpretation
Introduced| English | Meaning |
|---|---|
| compiler/kəmˈpaɪlə/ | Software that translates a program from a source language into another form, commonly machine or intermediate code. |
| interpreter/ɪnˈtɜːprɪtə/ | Software that executes a program by processing its instructions at runtime rather than requiring a separate complete native executable first. |
| lexical analysis/ˈleksɪkl əˈnæləsɪs/ | lexical analysis |
| tokens/ˈtəʊkənz/ | The meaningful units identified during lexical analysis, such as identifiers, keywords, operators and literals. |
| syntax analysis/ˈsɪntæks əˈnæləsɪs/ | syntax analysis |
| abstract syntax tree/ˈæbstrækt ˈsɪntæks triː/ | A tree representation of a program's grammatical structure that omits unnecessary surface details such as grouping punctuation. |
| syntax error/ˈsɪntæks ˈerə/ | A mistake that breaks the grammatical rules of a programming language. |
| semantic analysis/səˈmæntɪk əˈnæləsɪs/ | A compilation stage that checks whether a syntactically valid program obeys meaning-related rules, such as type and declaration requirements. |
| code generation/kəʊd ˌdʒenəˈreɪʃn/ | Producing target instructions or code from an intermediate or analysed representation of a program. |
| code optimisation/kəʊd ˌɒptɪmaɪˈzeɪʃn/ | Transforming code to improve properties such as speed or memory use while preserving its required behaviour. |
The bug that cost a spacecraft, found by a comma
- NASA's Mariner 1 was destroyed 293 seconds after launch in 1962. The failure is often blamed on a single wrong character in the guidance software.
- The story is retold so often because it is the fear every programmer knows: a compiler happily translating a program that says something you did not mean.
- A compiler is not one process but five, and each one catches a different class of mistake. Knowing which stage catches what tells you where any given error comes from.
- This lesson is how an interpreter 解释器 runs a program without producing anything, and the five stages a compiler 编译器 goes through.
How an interpreter runs a program
- An interpreter translates and runs the source at the same time, one statement at a time.
- For each statement it reads the line, analyses it, checks the types, then executes the action immediately, and moves to the next.
- It produces no executable file: the translation exists only in memory and is thrown away. That is the syllabus's exact point, that it can execute a program without producing a translated version.
- It reports an error the moment it reaches the offending line and usually stops, which gives quick feedback while developing. Every run re-translates, so it is slower, and both the source and the interpreter must be present.
Translate once and keep it, or translate and run and forget
An interpreter:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
It works line by line, reporting errors as it reaches them; nothing is saved as an executable, and it is generally slower.
An interpreter can execute a program without producing a translated version of it.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The translation exists only in memory, statement by statement, and is discarded. That is why the interpreter must be present every time the program runs.
Stage 1: lexical analysis
- Lexical analysis 词法分析 groups the individual characters of the source into tokens 词法单元: keywords, identifiers, operators and literals.
- Whitespace and comments are discarded, since they have no meaning to the compiler, and identifiers are entered into a symbol table.
- So
total ← count * 2becomes the token sequence identifier, assignment, identifier, operator, literal. The lexer does not know or care whether that makes sense.
Lexical analysis (the lexer) turns:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The lexer groups characters into tokens and discards whitespace/comments; parsing then builds the tree.
Lexical analysis groups the source characters into ____ and discards whitespace and comments.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Keywords, identifiers, operators and literals. The lexer makes no judgement about whether the sequence is a valid program.
Stage 2: syntax analysis
- Syntax analysis 语法分析, or parsing, checks that the sequence of tokens fits the language's grammar, and builds an abstract syntax tree 抽象语法树 representing the structure.
- A missing bracket, a missing
ENDIFor a keyword in the wrong place is caught here: that is what a syntax error 语法错误 is, and it is why the compiler can report one without ever running the program.
The grammar the parser checks against
Stage 3: semantic analysis
- Semantic analysis 语义分析 checks that a syntactically valid program actually makes sense: every variable is declared before use, the types on each side of an assignment are compatible, a function is called with the right number of arguments.
total ← "seven" * 2is perfectly good syntax and complete nonsense. Only this stage catches it.- This is the distinction the exam tests: syntax is form, semantics is meaning.
Which of these is checked by semantic analysis rather than syntax analysis?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Brackets are grammar, so syntax; whitespace is the lexer; registers are code generation. Declarations and types are meaning.
Stages 4 and 5: code generation and optimisation
- Code generation 代码生成 walks the tree and emits the target machine code, choosing registers and laying out the data.
- Code optimisation 代码优化 improves that code without changing what it does: removing redundant work, computing constant expressions at compile time, and reordering instructions to suit the pipeline.
- The output is a stand-alone executable that runs without the compiler present.
Five stages, and each one catches something the last could not
The phases of compilation
Step through what a compiler does to your source. Each phase hands its output to the next — characters become tokens, tokens become a tree, the tree becomes optimised machine code.
Match each compiler phase to what it does.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Each phase transforms the program a step further: tokens, then a tree, then checked, then optimised code.
Put the compiler stages in order.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
Lexical → syntax → semantic → code generation → optimisation.
Code optimisation aims to:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Optimisation improves the generated code (constant folding, removing redundancy, reordering for the pipeline).
Worked example: which stage catches which error
x ← 5 +: the tokens do not fit the grammar, an operator with no right operand, so syntax analysis.x ← y + 1whereywas never declared: the form is fine but the meaning is not, so semantic analysis.IF a > b THEN OUTPUT awith noENDIF: syntax analysis again.- A program that runs and prints the wrong average: no stage catches it. That is a logic error, and only testing finds it. Name the stage and why the earlier ones let it through.
Match each faulty line to the compiler stage that catches it.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Syntax is form, semantics is meaning, and a logic error is valid in both but wrong in intent.
Worked example: compare the two translators
- Give two differences between how a compiler and an interpreter handle a program. [4]
- A compiler translates the whole program before it runs and produces an executable, which then runs without the compiler; an interpreter translates and executes one statement at a time and produces no executable, so the interpreter must be present every run.
- A compiler reports all the errors together after translation; an interpreter reports the first error when it reaches that line and then stops.
- Each mark is a pairing: say what one does and what the other does instead.
Marks that slip away
- An interpreter produces no translated version. That is the phrase the syllabus uses and the mark it awards.
- The lexer produces tokens and discards whitespace and comments; it does not check whether the program is valid.
- Syntax is form, semantics is meaning. An undeclared variable is a semantic error, not a syntax error.
- Optimisation must not change what the program does, only how quickly or compactly it does it.
You've got it
- an interpreter translates and executes one statement at a time, producing no executable, reporting the first error at its line, and re-translating on every run
- lexical analysis makes tokens and discards whitespace and comments; syntax analysis checks the grammar and builds an abstract syntax tree, catching syntax errors
- semantic analysis checks meaning: declarations, types, argument counts
- code generation emits machine code and optimisation improves it without changing behaviour, giving a stand-alone executable