A compiler does not translate a program in one leap. It breaks the source code into tokens, checks them against the grammar of the language, generates object code and then improves that code. Learn what happens at each stage, what the symbol table is for, and how an interpreter can run a program without ever producing a translated version.
Compilation has four main stages. Lexical analysis removes white space and comments and converts the source code into tokens, adding identifiers and constants to the symbol table. Syntax analysis (parsing) checks that the sequence of tokens obeys the grammar of the language, builds a parse tree and reports syntax errors. Code generation produces object code from the parse tree. Optimisation makes the object code run faster or use less memory without changing what it does. An interpreter analyses each statement in turn and executes it by calling its own pre-written machine code routines, so no translated version of the program is produced.
Fig. 1: the four stages of compilation, all sharing the symbol table
Section 01
Running code without translating it.
At AS Level you compared compilers and interpreters. At A Level you must explain how an interpreter can execute a program without producing object code.
Statement by statement: the interpreter reads one statement of source code, then carries out lexical and syntax analysis on just that statement.
Execute, do not store: the interpreter itself is a machine code program that contains ready-made routines for every kind of statement (assignment, OUTPUT, arithmetic, loops). Having analysed a statement, it calls the matching routine with the values from the statement, so the action is carried out directly.
Nothing is kept: no object code or executable file is written. The next time the statement is reached, for example on the next pass of a loop, it is analysed again.
Errors: the program runs until the interpreter reaches a statement it cannot analyse or execute, then stops and reports that error.
Examiner trap
Saying an interpreter "translates line by line into machine code" loses the mark at A Level. The point is that it executes each statement using its own routines without producing a translated version.
Section 02
Lexical and syntax analysis.
The front end of the compiler checks the source code and turns it into a form the code generator can use.
Stage
What happens
Errors found
Lexical analysis
reads the source code character by character; removes white space and comments; groups characters into tokens (keywords, identifiers, operators, constants); looks up keywords in a keyword table and replaces them with short tokens; enters identifiers and constants into the symbol table with their details
illegal characters, badly formed identifiers or numbers (e.g. 3.4.5)
Syntax analysis
checks the order of tokens against the grammar rules of the language (often defined in BNF); builds a parse tree for each statement; adds information such as data types to the symbol table; may also check that types are compatible (semantic checks)
syntax errors, e.g. a missing ENDIF, two operators together, an unmatched bracket; a list of all errors is reported
Worked example Tokenise a statement
Show what lexical analysis produces from this line of source code:
Total ← Total + Price * 2 // add this item
Remove the comment // add this item and the extra spaces: they are not needed to execute the program.
Split the remaining characters into tokens: Total, ←, Total, +, Price, *, 2. That is 7 tokens.
Classify each token: Total and Price are identifiers, ← + and * are operators, 2 is a numeric constant.
Add Total, Price and the constant 2 to the symbol table (once each) so later stages can record their data type and address, and replace each identifier with a reference to its symbol table entry.
Answer: A token stream: identifier(Total) assign identifier(Total) plus identifier(Price) multiply constant(2), with Total, Price and 2 in the symbol table.
Examiner trap
Lexical analysis does not check the order of the tokens. Total + ← Price passes lexical analysis (every token is valid) and is rejected at syntax analysis.
Stage 1 · Learn
Check what the sim just showed you
Four quick checks. Each correct answer earns XP and records this skill on your profile.
Quick check+10 XP
Which compilation stage removes comments and white space?
Quick check+10 XP
What is checked during syntax analysis?
Quick check+10 XP
What is held in the symbol table?
Quick check+10 XP
How does an interpreter carry out a statement?
Section 03
Code generation and optimisation.
Once the program is known to be valid, the back end of the compiler produces and improves the object code.
Code generation: the parse tree is converted into object code (machine code, or an intermediate code), with the symbol table used to allocate a memory address to each variable.
Optimisation changes the code so that it executes in less time and/or uses less memory, without changing the result. Typical techniques:
remove redundant instructions (e.g. a load of a value that is already in the accumulator);
work out constant expressions at compile time (e.g. 60 * 60 becomes 3600);
move a calculation whose value does not change out of a loop, so it is done once;
remove code that can never be executed.
// before optimisation // after optimisation
FOR Index ← 1 TO 100 Area ← Width * Height
Area ← Width * Height FOR Index ← 1 TO 100
Total ← Total + Area * Index Total ← Total + Area * Index
NEXT Index NEXT Index
Worked example Remove a redundant instruction
A code generator produced this assembly code for X ← A + B and Y ← A + B + C, where A, B, C, X and Y are at addresses 200 to 204. Optimise it.
LDD 200
ADD 201
STO 203
LDD 200
ADD 201
ADD 202
STO 204
Lines 1-3 load A, add B and store A + B at 203 (X).
STO does not change the accumulator, so after line 3 ACC still holds A + B.
Lines 4-5 load A and add B again: they recalculate a value already in ACC, so they are redundant.
Delete them: LDD 200, ADD 201, STO 203, ADD 202, STO 204. ACC now holds A + B + C when it is stored at 204 (Y).
Answer: 7 instructions become 5, with exactly the same results stored in X and Y.
Your turn
In the loop above, how many multiplications are carried out before and after optimisation?
Before: 2 per pass × 100 passes = 200. After: 1 before the loop + 1 per pass × 100 = 101.
Stage 2 · Exam
Exam-style questions
Unlocks once the four checks above are done. Worth more XP, written to A Level Paper 3 and Paper 4 standard.
Finish the four checks above to unlock the exam questions
Exam style+20 XP
At which stage would the error IF X > THEN be detected?
Exam style+20 XP
Which is an example of code optimisation?
Exam style+20 XP
What is the output of the code generation stage?
Exam style+20 XP
Why does a statement in a loop slow an interpreted program?
Skill unlocked
The stages of compilation, compiled.
This skill is now recorded on your profile. Keep the chain going.