Definition
Compilation is the process of translating all of a program's source code into object code before it is run. It takes place in four stages: lexical analysis, syntax analysis, code generation and optimisation.
Lexical Analysis
Definition
Lexical analysis is the first stage of compilation. Comments and whitespace are removed, and the rest of the source code is converted into a series of tokens.
Key Point
What happens in lexical analysis:
• Comments and unnecessary whitespace are removed
• Keywords, operators and other symbols are replaced with tokens
• Identifiers, such as the names of variables and subroutines, are entered into a symbol table
• The series of tokens and the symbol table are passed on to the next stage
• Comments and unnecessary whitespace are removed
• Keywords, operators and other symbols are replaced with tokens
• Identifiers, such as the names of variables and subroutines, are entered into a symbol table
• The series of tokens and the symbol table are passed on to the next stage
Syntax Analysis
Definition
Syntax analysis is the second stage of compilation. The tokens are checked against the grammar rules of the language, and an abstract syntax tree is built from them.
Key Point
What happens in syntax analysis:
• The series of tokens is checked against the rules (the syntax) of the language
• An error is reported wherever a rule is broken, such as a missing bracket
• If no rules are broken, an abstract syntax tree is built to represent the structure of the program
• The series of tokens is checked against the rules (the syntax) of the language
• An error is reported wherever a rule is broken, such as a missing bracket
• If no rules are broken, an abstract syntax tree is built to represent the structure of the program
Code Generation
Definition
Code generation is the third stage of compilation. The abstract syntax tree is converted into object code: the machine code instructions that the processor can execute.
Optimisation
Definition
Optimisation examines the generated code and makes it more efficient without changing what it does, so that the program runs faster and uses less memory.
Example
Examples of optimisation:
• Removing instructions that have no effect on the result
• Removing variables and subroutines that are never used
• Replacing a group of instructions with a shorter or faster group that does the same job
• Removing instructions that have no effect on the result
• Removing variables and subroutines that are never used
• Replacing a group of instructions with a shorter or faster group that does the same job
Worked Example
Worked Example: Compiling One Line
pseudocode
total = price + 5 // add the delivery charge
| Stage | What happens to this line |
|---|---|
| Lexical analysis | The comment and the spaces are removed. total and price are entered into the symbol table, and the line becomes a series of tokens: identifier, assignment operator, identifier, addition operator, number |
| Syntax analysis | The tokens are checked against the rule for an assignment statement. The rule is met, so the statement is added to the abstract syntax tree |
| Code generation | The tree is converted into object code: instructions that load price, add 5 and store the result in total |
| Optimisation | The object code is examined and any unnecessary instructions are removed |
Exam Tip
Keep each action with its stage. Removing comments, creating tokens and filling the symbol table belong to lexical analysis. Reporting syntax errors and building the abstract syntax tree belong to syntax analysis. Object code is produced in code generation.