Show understanding of the various stages in the compilation of a program

16.2 Translation Software

Objective

Show understanding of the various stages in the compilation of a program and the key artefacts produced at each stage.

What is Translation Software?

Translation software converts source code written in a high‑level language into a form that a computer can execute. The most common type is a compiler, which performs a series of well‑defined transformations, often preceded by a pre‑processor (e.g. macro expansion in C/C++).

Compilation Pipeline – Overview

The compilation process is a pipeline. Each stage receives an input, applies a specific transformation, and produces an output that becomes the input for the next stage.

Detailed Stages

1. Pre‑processor (optional)
   • Input: Raw source code.
   • Typical tasks: macro expansion, file inclusion (#include), conditional compilation (#ifdef).
   • Output: Modified source code passed to the lexical analyser.
2. Lexical Analysis (Scanning)
   • Input: Characters of the (pre‑processed) source code.
   • Output: Stream of tokens (identifiers, keywords, literals, operators, delimiters).
   • Implementation basis: regular expressions & deterministic finite automata (DFA).
   • Key data structure: Symbol table – records each identifier with attributes such as type, scope, and later storage location.
3. Syntax Analysis (Parsing)
   • Input: Token stream.
   • Output: Parse tree or Abstract Syntax Tree (AST) representing the grammatical structure.
   • Technique: Context‑free grammar (usually written in BNF/EBNF).
   • Example BNF rule for arithmetic expressions:

     <expr> ::= <term> { (“+” | “-”) <term> }

4. Semantic Analysis
   • Input: AST.
   • Output: Annotated AST enriched with type information, scope links and other semantic attributes.
   • Checks performed:
     • Type compatibility (e.g. cannot assign a float to an int without conversion).
     • Declaration before use.
     • Scope rules (e.g. variable shadowing).
     • Array‑bounds and function‑argument matching.
5. Intermediate Code Generation
   • Input: Annotated AST.
   • Output: Platform‑independent Intermediate Representation (IR), often three‑address code.
   • Example three‑address instruction: t1 = a + b
6. Optimization
   • Input: IR.
   • Output: Optimised IR.
   • Goals: Reduce execution time, memory usage or power consumption.
   • Typical techniques:
     • Constant folding – evaluate constant expressions at compile time.
       Before: t1 = 3 + 4
       After: t1 = 7
     • Dead‑code elimination.
     • Loop‑invariant code motion.
     • Peephole optimisation on generated machine instructions.
7. Code Generation
   • Input: Optimised IR.
   • Output: Target machine code or assembly language.
   • Key tasks: Register allocation, instruction selection, instruction scheduling.
8. Linking & Loading
   • Input: Object modules produced by the code generator.
   • Output: Executable program ready to run.
   • Linker role: Resolve external references, combine object files.
   • Loader role: Place the program in memory and start execution.
   • Static vs. dynamic linking:
     • Static linking: Library code is copied into the executable at compile time.
     • Dynamic linking: References to shared libraries are resolved at run‑time, reducing executable size and allowing library updates without recompilation.

Symbol Table – Definition & Example

A symbol table is a data structure maintained by the compiler that records information about each identifier encountered in the source program.

Typical Errors Detected at Each Stage

Summary of Compilation Stages

Key Points to Remember

• Each stage produces an intermediate form that becomes the input for the next stage.
• Early error detection (lexical → syntax) is easier to locate and fix than later errors (semantic, linking).
• Optimisation can be applied at source, intermediate, or machine‑code level; the most exam‑focused techniques are constant folding and dead‑code elimination.
• The front‑end (lexical, syntax, semantic) is language‑specific; the back‑end (IR, optimisation, code generation) is target‑machine specific – a design that promotes reuse.
• Understanding the role of the symbol table, grammar rules and IR examples is essential for answering typical exam questions.

Typical Exam Question

Question: Explain the role of the symbol table during compilation and indicate at which stages it is accessed.

Answer outline:

1. Created during lexical analysis when an identifier is first encountered; an entry records its name, type, scope and (later) storage location.
2. Consulted in syntax analysis to verify that identifiers used in expressions have been declared.
3. Used extensively in semantic analysis for type checking, scope resolution and ensuring correct use of functions/arrays.
4. May be referenced again in code generation to allocate registers or memory addresses for each identifier.

Action‑Oriented Review Checklist – How Your Lecture Notes Stack Up Against the 2026 Cambridge AS & A‑Level Computer Science (9618) Syllabus

Use this quick‑audit table to verify that your notes cover every required sub‑topic. Tick the “✔” column as you confirm coverage; if a box is empty, add the suggested material.

When you have a tick in every “✔” column, your notes are fully aligned with the 2026 Cambridge AS & A‑Level Computer Science syllabus.