Computer Science - Stages of Compilatio

All stages of compilation details

What is “compilation”?

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

What are all the stages of compilation?

• Lexical analysis

• Syntax analysis

• Code generation

• Optimisation

What is lexical analysis and what does it identify?

Studying the words or vocabulary of a language and it includes identifying lexical tokens

What do tokens represent?

• Keywords

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

• identifiers

  • Variable names, function names

• Operators

  • '+', '++', '-', '*'

• Separators

  • ',' ';', '{', '}', '(', ')'

During lexical analysis, what is ignored?

Unnecessary elements like comments and white space

What is the result of a lexical analysis?

A token table, which is a collection of tokens that the lexical analyser has identified from the source code. It’s a list where each token is categorised into its type and contains its value

What does a syntax analysis do?

After tokens have been identified, syntax analysis makes sure they all adhere to the syntax rules of the programming language.

what happens if tokens don’t adhere to the syntax rules?

The character(s) that break the syntax rules will be flagged

what happens if the code passes the syntax analysis?

The compiler can then create an Abstract Syntax Tree (AST)

What is an abstract syntax tree?

A graph-based representation of the code being compiled, it’s an efficient way to represent the code for the next step

What does the code generation step do?

The code generation step takes the abstract syntax tree and converts it into low-level machine instructions (object code), which can then be linked to form an executable program that runs on the CPU

What is object code?

A compiler turns source code into object code. Object code can be executed by a computer.

What does the optimisation step do?

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

What is the advantage of the optimisation step?

It reduces the memory required to run the code, which leads to faster execution

Give examples of common optimisation actions

• Constant folding

  • Example: int x = 2 + 3; turns into int x = 5;

• constant propagation

  • Replaces variables with their constant values wherever possible

  • Example: int a =5; int b = a + 2; turns into int b = 7;

• Dead code elimination

  • Remove code that will never be executed or code that does not affect the program’s outcome

  • Example: removing an if statement that has a condition that’s never met

• Loop unrolling

  • Increases the size of the loop’s body to reduce the overhead of loop control.

  • Example: A loop that multiplies numbers together will expand out to every line by line multiplication that happens

• Common subexpression elimination

  • Identify expressions that are computed multiple times and calculate them once, storing the result.