stages-of-compilation

Stages of Compilation

What is compilation?

• Compilation is a process that translates a program written in a high-level programming language into machine code

• Only machine code can be executed by a computer

• There are four stages involved in this process:

  • Lexical Analysis

  • Syntax Analysis

  • Code Generation

  • Optimisation

Lexical analysis

• In A Level Computer Science, lexical analysis means studying the words or vocabulary of a language

• This stage involves identifying lexical ‘tokens’ in the code

• Tokens represent small meaningful units in the programming language, such as:

  • Keywords

    • var, const, function, for, while, if

  • Identifiers

    • Variable names, function names

  • Operators

    • ‘+’, ‘++’, ‘-‘, ‘*’

  • Separators

    • ‘,’ ‘;’, ‘{‘, ‘}’, ‘(‘, ‘)’

• During this stage, unnecessary elements like comments and whitespace are ignored

• For example, if the following code is being compiled:

var x = function(x,y) {

if(x>2) {

return x*y;

}

return x+y;
}

• The result of lexical analysis is a token table

Syntax analysis

• Now that tokens have been identified, syntax analysis makes sure they all adhere to the syntax rules of the programming language

• A symbol, e.g. ‘$’ could be a valid token but not a valid character according to particular programming languages

• The dollar symbol would be flagged as breaking the syntax rules

• Other syntax errors programmers commonly make include mismatched parentheses or missing semicolons

• If the code passes the syntax analysis, the compiler can create an Abstract Syntax Tree (AST)

• An AST is a graph-based representation of the code being compiled

• An AST is an efficient way to represent the code for the next step

Example abstract syntax tree

• For the same code as above, the following abstract syntax tree can be created

Abstract syntax tree

Code generation

• This step takes the AST and traverses it to generate object code that can be executed by the computer

Optimisation

• This step modifies the code to make it more efficient without changing its functionality

• This is important to attempt because it reduces the memory required to run the code, which leads to faster execution

• A common optimisation action is removing duplicate code

• If an ‘add’ function is written twice in the source code, a sophisticated compiler will notice this and include it only once in the object code