Stages of Compilation

Overview

Compilation is the process of converting high-level programming code (like Python or Java) into machine code that a computer's processor can execute. This process involves multiple stages, each transforming the source code closer to the executable code while checking for errors and optimising performance. The main stages of compilation are Lexical Analysis, Syntax Analysis, Code Generation, and Optimisation. Understanding these stages is crucial, as they ensure the code is accurate, efficient, and executable.

Lexical Analysis

• Purpose: Break down the source code into meaningful units (tokens) and remove unnecessary elements.
• Process:
  • Tokenisation: The source code is divided into tokens, which represent atomic units like keywords, identifiers, operators, and symbols.
  • Removing Unnecessary Elements: This includes eliminating whitespace and comments, which don't affect the program logic but make it readable for humans.
  • Symbol Table Creation: During lexical analysis, identifiers (like variable and function names) are stored in a symbol table to keep track of each unique identifier and its information.
• Output: A list of tokens is generated and passed to the next stage, Syntax Analysis.

for i in range(5):  # This is a loop
    print(i)

Syntax Analysis (Parsing)

• Purpose: Check that the sequence of tokens follows the correct syntax (rules) of the programming language.
• Process:
  • Syntax Rules Check: The compiler ensures the token sequence conforms to the language's grammar, reporting errors if syntax rules are broken.
  • Abstract Syntax Tree (AST): If the code passes syntax analysis, the compiler constructs an Abstract Syntax Tree (AST), a tree-like structure that represents the hierarchical relationship of elements in the code.
• Error Handling: Syntax errors are identified and reported here. These could include missing semicolons, unbalanced parentheses, or incorrect usage of keywords.
• Output: If no errors are found, the AST is passed to the Code Generation stage.

Code Generation

• Purpose: Converts the AST into machine code or object code, which is a lower-level representation that the machine can execute.
• Process:
  • The AST is translated into machine code instructions that correspond to the operations in the high-level code.
  • This code is platform-dependent and may vary based on the target machine's architecture.
• Output: A preliminary version of the object code is produced. This code may still be improved in the next stage, Optimisation.

Optimisation

• Purpose: Refines the object code to make it more efficient in terms of execution time and memory usage.
• Process:
  • Redundant Code Removal: Any unnecessary instructions or repeated calculations are eliminated.
  • Loop Optimisation: Common within loops, where repeated operations may be condensed to reduce processing time.
  • Minimising Memory Access: Reduces the number of times memory needs to be accessed, which speeds up execution.
• Importance: Optimisation ensures that the program runs as efficiently as possible, which is crucial for performance, especially in large applications.
• Output: The optimised object code is ready to be executed on the target machine.

How Each Stage Feeds into the Next

• Lexical Analysis to Syntax Analysis: Tokens produced in lexical analysis are used in syntax analysis to check if they form valid statements in the language.
• Syntax Analysis to Code Generation: The AST produced in syntax analysis serves as the blueprint for code generation, allowing the compiler to translate logical structures into machine instructions.
• Code Generation to Optimisation: Initial object code is optimised for efficiency, reducing execution time and resource use.

Note Summary