Stages of compilation, linkers and loaders

Lexical analysis, syntax analysis, code generation and optimisation, then static and dynamic linking and the loader.

A10.8Operating systems, software and translatorsA level45 min

A compiler is not one step but a pipeline. Source code goes in as a long string of characters; object code comes out. In between, each stage turns one representation into a more useful one, and each can find a different kind of error. This lesson follows a line of Python through the stages, then looks at what happens after compiling: linking with libraries and loading into memory.

1. Lexical analysis

The lexical analyser (lexer) reads the source one character at a time and groups the characters into tokens: keywords, identifiers, numbers, operators and punctuation. On the way it:

• removes whitespace and comments, which the later stages do not need;
• builds the symbol table, with an entry for each identifier (variable, function or constant name). Later stages add to each entry: its data type, its scope, and eventually its memory address;
• reports lexical errors: sequences of characters that cannot be any token, such as an identifier starting with a digit or a character the language does not use.

The line speed = 20 + boost * 2 # set the speed becomes seven tokens: IDENTIFIER speed, OPERATOR =, NUMBER 20, OPERATOR +, IDENTIFIER boost, OPERATOR *, NUMBER 2. The comment has gone.

2. Syntax analysis

The syntax analyser (parser) checks that the sequence of tokens follows the grammar rules of the language. speed = 20 + is a valid list of tokens but breaks the rules, so it is a syntax error, reported with its line number. Grammar rules are often written in Backus-Naur form.

The parser builds an abstract syntax tree (AST), which shows the structure of each statement. Python will show you its own:

import ast

tree = ast.parse("speed = 20 + boost * 2")
print(ast.dump(tree.body[0], indent=2))

Run this in the simulator

Look at the shape: the multiplication boost * 2 is a branch inside the addition, because multiplication happens first. The tree has captured the precedence that was only implied in the text.

Alongside it comes semantic analysis, which many descriptions count as part of syntax analysis and some treat as a stage of its own: checks on meaning that the grammar alone cannot catch, using the symbol table. Is this variable declared before it is used? Are the types compatible, or is the program adding a string to an integer? Is a function called with the right number of parameters?

3. Code generation

The code generator walks the syntax tree and produces object code: machine code for the target processor, or bytecode for a virtual machine. The symbol table supplies the address of each variable. Here is a code generator that turns an expression's tree into the stack bytecode from lesson A10.6, children first, operator last:

import ast

OPS = {ast.Add: "ADD", ast.Sub: "SUB", ast.Mult: "MUL"}
DO = {ast.Add: lambda a, b: a + b, ast.Sub: lambda a, b: a - b, ast.Mult: lambda a, b: a * b}

def generate(node, code):
    if isinstance(node, ast.Constant):
        code.append(("PUSH", node.value))
    elif isinstance(node, ast.Name):
        code.append(("LOAD", node.id))
    elif isinstance(node, ast.BinOp):
        generate(node.left, code)          # code for the left branch
        generate(node.right, code)         # then the right branch
        code.append((OPS[type(node.op)],)) # then the operator
    return code

def fold(node):
    """Constant folding: calculate an operation on two constants now, at compile time."""
    if isinstance(node, ast.BinOp):
        node.left, node.right = fold(node.left), fold(node.right)
        if isinstance(node.left, ast.Constant) and isinstance(node.right, ast.Constant):
            return ast.Constant(DO[type(node.op)](node.left.value, node.right.value))
    return node

tree = ast.parse("boost * 2 + 60 * 60", mode="eval").body
print("generated:", generate(tree, []))
print("optimised:", generate(fold(tree), []))

Run this in the simulator

4. Optimisation

Optimisation changes the object code so that it does the same job faster, or in less memory, or both. Common optimisations:

• constant folding: calculating 60 * 60 once at compile time rather than every time the program runs, as in the cell above;
• removing dead code that can never run, and variables that are never used;
• replacing a slow operation with a faster one that gives the same result, such as multiplying by 2 with a shift;
• moving a calculation that gives the same answer every time out of a loop.

Optimisation makes compiling slower, and heavily optimised code can be harder to debug, because the object code no longer matches the source line by line. Some compilers optimise during code generation as well as after it. Python's own compiler folds constants:

import dis

dis.dis(compile("seconds = 60 * 60", "demo", "exec"))

Run this in the simulator

There is no multiplication in the bytecode. It just loads the constant 3600.

Libraries, linkers and loaders

Most programs use library routines: the maths functions, file handling, graphics. Libraries are already compiled, so the compiler produces object code with gaps where the library routines are called. Joining them up is the job of the linker, which combines the program's object code with the library modules into one executable, and makes each call point to the right address.

• Static linking copies the library code into the executable. The program is self-contained and will always use the version it was built with, but it is larger, and a fixed library means rebuilding every program that uses it.
• Dynamic linking puts only a reference to the library in the executable. The library (a DLL on Windows, a shared object on Linux) is joined to the program when it runs. Executables are smaller, many programs share one copy in memory, and a fixed library helps every program at once. But the program fails if the library is missing, and a new version of a library can break a program that relied on the old behaviour.

The loader is part of the operating system. It copies the executable from secondary storage into memory, loads any dynamically linked libraries it needs, and adjusts memory addresses in the code to match where the program was actually placed (relocation), then starts it running.

Task: a lexer

Write tokenise(text), the lexical analysis stage for a tiny language. text is a string that may contain several lines. It returns a list of (type, text) tuples in order, where type is one of:

• "KEYWORD": a word in KEYWORDS;
• "IDENTIFIER": any other word, made of letters, digits and underscores and not starting with a digit;
• "NUMBER": one or more digits;
• "OPERATOR": one character from OPERATORS;
• "PUNCTUATION": one character from PUNCTUATION.

Whitespace is skipped, and a # starts a comment that runs to the end of its line and produces no tokens. Do not use Python's own tokenize module or regular expressions: read the characters yourself.

Then print each token of source on its own line as <type> <text>, for example KEYWORD while. Finally print the symbol table: symbols: followed by each different identifier, in the order it first appears, separated by ,. The robot stays still.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

KEYWORDS = ["while", "if", "else", "def", "return"]
OPERATORS = "=+-*/<>"
PUNCTUATION = "():,"

source = "while gap > 20:  # keep going\n    gap = gap - step"

def tokenise(text):
    tokens = []
    return tokens

Challenges

1. Make the lexer report a lexical error, with the position, for a character it does not recognise, such as $.
2. Add two-character operators ==, <= and >=. How does the lexer know whether = is finished?
3. Add division to generate and fold, as a DIV instruction, and check that in speed + 60 / 4 the division is folded to PUSH 15.0.