Chapter 02 of 33

Language Processors: Interpreter, Assembler, Linker & Loader

When you type gcc main.c add.c -o prog and press Enter, it feels like one program, the compiler, did all the work. In reality a whole team of programs ran one after another: a preprocessor, the compiler proper, an assembler and a linker. Later, when you type ./prog, a loader brings the program into memory. And languages such as Python and Java add yet another player, the interpreter or virtual machine.

All of these are called language processors. In this chapter we follow a small two-file C program through every stage, look at the real files each stage produces (using GCC 15.2 and GNU binutils on x86-64 Linux), and then compare compilers with interpreters. This is a favourite area for university short-answer questions and interview basics.


The Language Processing System

A language processor is any program that takes a program written in some language as input and translates, prepares or executes it. Preprocessors, compilers, assemblers, linkers, loaders and interpreters are all language processors.

For a compiled language such as C, the classic pipeline is:

   source program (main.c, add.c)
            |
            v
   +------------------+
   |   PREPROCESSOR   |   expands #include, #define, #if
   +------------------+
            |   modified source (main.i)
            v
   +------------------+
   |     COMPILER     |   translates to assembly
   +------------------+
            |   target assembly program (main.s)
            v
   +------------------+
   |    ASSEMBLER     |   translates to machine code
   +------------------+
            |   relocatable object file (main.o)
            v
   +------------------+     library files (libc),
   |      LINKER      |<--  other object files (add.o)
   +------------------+
            |   executable file (prog)
            v
   +------------------+
   |      LOADER      |   copies it into memory and starts it
   +------------------+
            |
            v
     running process

The gcc command is really a driver that runs these tools for you. Asking it to print the commands it would run (gcc -### main.c add.c -o prog) shows, in shortened form:

/usr/libexec/gcc/x86_64-linux-gnu/15/cc1 ... main.c ... -o /tmp/ccPU4pHf.s    (preprocess + compile)
/usr/bin/x86_64-linux-gnu-as --64 -o /tmp/ccW6zBNJ.o /tmp/ccPU4pHf.s         (assemble)
/usr/libexec/gcc/x86_64-linux-gnu/15/cc1 ... add.c ... -o /tmp/....s          (same two steps for add.c)
/usr/bin/x86_64-linux-gnu-as --64 -o /tmp/....o /tmp/....s
/usr/libexec/gcc/x86_64-linux-gnu/15/collect2 ... /tmp/ccW6zBNJ.o ... -lc ... (link: collect2 runs ld)

In modern GCC the preprocessor is built into cc1, but you can still stop after each stage using flags:

Flag

Stop after

Output file

gcc -E main.c

Preprocessing

Preprocessed C (conventionally main.i)

gcc -S main.c

Compilation

Assembly main.s

gcc -c main.c

Assembly

Object file main.o

gcc main.o add.o -o prog

Linking

Executable prog

Our running example has two files:

/* main.c */
#include <stdio.h>
#define SQUARE(x) ((x) * (x))

int add(int a, int b);   /* defined in add.c */

int main(void) {
    int r = add(SQUARE(3), 4);
    printf("result = %d\n", r);
    return 0;
}
/* add.c */
int add(int a, int b) {
    return a + b;
}

1. Preprocessor

The preprocessor works on the source text before the real compiler sees it. It does not understand C types or statements; it performs text-level operations driven by lines starting with #.

  • File inclusion: #include <stdio.h> is replaced by the whole contents of that header.

  • Macro expansion: #define SQUARE(x) ((x) * (x)) makes every SQUARE(3) become ((3) * (3)).

  • Conditional compilation: #if, #ifdef, #endif keep or drop blocks of code (for example, debug-only code).

  • Comment removal: each comment is replaced by a single space.

Running gcc -E -P main.c on our file produces 313 lines (our file has 11), because the declarations from stdio.h are pasted in. The end of that output is:

extern int __uflow (FILE *);
extern int __overflow (FILE *, int);

int add(int a, int b);
int main(void) {
    int r = add(((3) * (3)), 4);
    printf("result = %d\n", r);
    return 0;
}

Notice that the macro has been expanded and the comment has disappeared. The compiler proper never sees SQUARE or #include.


2. Compiler

The compiler translates the preprocessed C into assembly language for the target machine. gcc -O0 -S -masm=intel main.c gives (directives trimmed):

main:
        push    rbp
        mov     rbp, rsp
        sub     rsp, 16
        mov     esi, 4                  ; second argument: 4
        mov     edi, 9                  ; first argument: SQUARE(3), folded to 9
        call    add@PLT                 ; add is not defined in this file
        mov     DWORD PTR -4[rbp], eax  ; r = return value
        mov     eax, DWORD PTR -4[rbp]
        lea     rdx, .LC0[rip]          ; address of "result = %d\n"
        mov     esi, eax
        mov     rdi, rdx
        mov     eax, 0
        call    printf@PLT
        mov     eax, 0
        leave
        ret

Even at -O0 the compiler evaluated ((3) * (3)) to 9 at compile time (constant folding). Also notice that the compiler happily emits call add although add is defined somewhere else; the prototype told it the types, and finding the actual code is the linker's job. How the compiler itself works inside is covered in Phases of a Compiler.


3. Assembler

An assembler translates assembly language (symbolic instructions such as mov, call and labels) into machine code, producing a relocatable object file.

Assembly is almost one-to-one with machine instructions, so the assembler's job is mostly table lookup: opcode names to bit patterns, register names to numbers, and labels to addresses. gcc -c main.c creates main.o:

$ file main.o
main.o: ELF 64-bit LSB relocatable, x86-64, version 1 (SYSV), not stripped

The word relocatable is the important part. Look at the machine code with objdump -d -r (compiled with -fcf-protection=none to keep it short):

0000000000000000 <main>:
   0:   55                      push   rbp
   1:   48 89 e5                mov    rbp,rsp
   4:   48 83 ec 10             sub    rsp,0x10
   8:   be 04 00 00 00          mov    esi,0x4
   d:   bf 09 00 00 00          mov    edi,0x9
  12:   e8 00 00 00 00          call   17 <main+0x17>
                        13: R_X86_64_PLT32      add-0x4
  17:   89 45 fc                mov    DWORD PTR [rbp-0x4],eax
   ...
  2e:   e8 00 00 00 00          call   33 <main+0x33>
                        2f: R_X86_64_PLT32      printf-0x4
   ...

Two things to observe:

  1. Addresses start at 0. The assembler does not know where this code will finally live in memory.

  2. The call instructions contain 00 00 00 00 as the target. The assembler does not know where add and printf are, so it leaves a hole and writes a relocation entry ("at offset 0x13, fill in the address of add"). The linker will fill these holes.

The symbol table of each object file (nm) shows what it defines (T = in the text/code section) and what it needs (U = undefined):

$ nm main.o                       $ nm add.o
                 U add            0000000000000000 T add
0000000000000000 T main
                 U printf

One-pass vs two-pass assemblers

The tricky part of assembling is the forward reference: an instruction uses a label that is defined further down, so when the assembler reaches the instruction it does not know the label's address yet. The classic solution is a two-pass assembler:

  • Pass 1: walk through the program keeping a location counter (LC), the address the current instruction will occupy. Whenever a label is defined, record (label, LC) in the symbol table. No code is generated yet.

  • Pass 2: walk through again; now every label's address is known, so translate each instruction using the opcode table and the symbol table.

Worked example. A hypothetical machine where every instruction and every data word occupies 4 bytes. DC defines a constant word; DS n reserves n words. The program starts at address 100.

          START  100
          LOAD   A        ; acc = A
          ADD    B        ; acc = acc + B
          JMPZ   DONE     ; forward reference: DONE not seen yet
          STORE  C
  DONE:   HALT
  A:      DC     5
  B:      DC     7
  C:      DS     2        ; reserve 2 words (8 bytes)
          END

Pass 1 (LC starts at 100 and grows by the size of each line):

LC

Line

Size

Symbol table action

100

LOAD A

4

-

104

ADD B

4

-

108

JMPZ DONE

4

-

112

STORE C

4

-

116

DONE: HALT

4

DONE = 116

120

A: DC 5

4

A = 120

124

B: DC 7

4

B = 124

128

C: DS 2

8

C = 128

136

END

-

program size = 136 - 100 = 36 bytes

Pass 2 uses the finished symbol table:

100: LOAD  120
104: ADD   124
108: JMPZ  116      <-- DONE resolved, although it was a forward reference
112: STORE 128
116: HALT
120: 5
124: 7
128: (8 bytes reserved)

A one-pass assembler avoids reading the source twice by leaving a hole for each forward reference and remembering it in a list ("backpatching"); when the label is finally defined, it goes back and fills all the holes. The same backpatching idea appears again in Translating Control Flow & Backpatching.


4. Linker

A linker (link editor) combines one or more object files and libraries into a single executable. It performs symbol resolution (matching each use of an external name with its definition) and relocation (assigning final addresses and patching every reference to them).

If we forget to give the linker add.o, compilation of main.c still succeeds, but linking fails because add is used and never defined:

$ gcc main.o -o prog
/usr/bin/x86_64-linux-gnu-ld.bfd: main.o: in function `main':
main.c:(.text+0x17): undefined reference to `add'
collect2: error: ld returned 1 exit status

(This object was built with GCC's default -fcf-protection, which adds a 4-byte endbr64 instruction at the start of main, so the hole is at offset 0x17 instead of the 0x13 shown earlier.) The message comes from ld, not from the compiler. "Undefined reference" is always a link-time error. With both object files:

$ gcc main.o add.o -o prog
$ ./prog
result = 13
$ nm prog | grep -E ' (main|add|printf)'
0000000000001187 T add
0000000000001149 T main
                 U printf@GLIBC_2.2.5

Now main and add have real (relative) addresses in one combined code section, and the call add hole has been patched. printf is still undefined because it will come from the C library at run time: this is dynamic linking.

Static vs dynamic linking

$ gcc main.o add.o -o prog                 # dynamic (default)
$ gcc -static main.o add.o -o prog_static  # static
$ ls -l prog prog_static
-rwxrwxrwx 1 imran imran  16008 Nov  2 12:15 prog
-rwxrwxrwx 1 imran imran 816936 Nov  2 12:15 prog_static
$ ldd prog
        linux-vdso.so.1 (0x000071822fd59000)
        libc.so.6 => /usr/lib/x86_64-linux-gnu/libc.so.6 (0x000071822fa00000)
        /lib64/ld-linux-x86-64.so.2 (0x000071822fd5b000)

The static executable is about 51 times larger because the needed parts of the C library are copied into it.

Aspect

Static linking

Dynamic linking

When library code is attached

At link time, copied into the executable

At load time or run time, from a shared library (.so / .dll)

Executable size

Large (816,936 bytes here)

Small (16,008 bytes here)

Memory use with many programs

Each program has its own copy of the library

One copy of the library in memory is shared

Library bug fix

Must relink every program

Update the shared library once

Start-up

Slightly faster, no symbol lookup

Slight cost to load and bind libraries

Dependency problems

None at run time; self-contained

Program fails if the right library version is missing


5. Loader

A loader is the part of the system that places an executable program into main memory and prepares it for execution, then transfers control to its first instruction.

Classically a loader is described by four functions:

  1. Allocation: find memory space for the program.

  2. Linking: resolve references between object modules (if not already done by a separate linker).

  3. Relocation: adjust address-dependent locations to the actual load address.

  4. Loading: physically copy the machine code and data into memory.

Relocation, worked out

Suppose the program from the assembler example was assembled as if it started at address 0 instead of 100, so A is at 20 and the first instruction is LOAD 20. The OS then loads the program at address 5000.

  assembled (origin 0)        loaded at 5000
  0:  LOAD  20         -->    5000: LOAD  5020    (address field + 5000)
  4:  ADD   24         -->    5004: ADD   5024
  8:  JMPZ  16         -->    5008: JMPZ  5016
  12: STORE 28         -->    5012: STORE 5028
  20: 5                -->    5020: 5             (data value, NOT changed)

Only fields that hold addresses are adjusted; the constant 5 is not. That is why the object file must record which locations need relocation (the relocation entries we saw from objdump -r, or "relocation bits" in older textbook loaders).

Types of loaders

Loader

Idea

Compile-and-go (assemble-and-go)

Translator writes code directly into memory and runs it. Simple, but the program is retranslated every time.

Absolute loader

Object code already contains final addresses; the loader just copies it there. No relocation, so the program can only run at that one address.

Relocating loader

Adjusts address fields using relocation information so the program can be loaded anywhere.

Direct linking loader

Performs linking and relocation of several object modules while loading.

Dynamic loading

A routine is loaded only when it is first called, saving memory for rarely used code.

Dynamic linking

Shared-library references are resolved at load or run time.

Bootstrap loader

A tiny loader in firmware/ROM that loads the operating system when the computer starts.

On Linux, when you run ./prog, the kernel's execve system call maps the ELF file into memory, and because the file names an interpreter (file prog reports interpreter /lib64/ld-linux-x86-64.so.2), the dynamic linker/loader ld-linux runs first, maps libc.so.6 and binds printf, then jumps to the program's entry point.


6. Interpreter

An interpreter executes a source program directly: it reads the program and performs the operations it specifies on the given inputs, without producing a separate target program that is saved and run later.

  Compiler:     source --> [COMPILER] --> target program
                                          input --> [target program] --> output

  Interpreter:  source + input --> [INTERPRETER] --> output

Shell scripts, early BASIC systems and many scripting tools are interpreted. Because the interpreter sees each statement at run time, it can give very good error messages that point to the exact failing statement, and you can change code and re-run instantly. The price is speed: the work of understanding each statement is repeated every time it executes (for example, on every loop iteration).

Compiler vs interpreter

Aspect

Compiler

Interpreter

Translation

Whole program translated before execution

Statements analysed and executed one at a time

Output

A target program (object/executable file)

No saved target program; produces the program's results directly

Execution speed

Fast: translation cost paid once

Slower: analysis repeated at run time

Start-up

Must compile (and link) first

Starts immediately

Error reporting

Many errors reported together before running

Stops at the first error it reaches at run time; code that never runs is never checked

Memory

Compiler not needed when the program runs

Interpreter must be in memory with the program

Source needed to run?

No, only the executable

Yes (or its bytecode)

Examples

C, C++, Rust, Go (GCC, Clang, rustc)

Bash, classic BASIC, the bytecode loop inside CPython

Hybrid systems: bytecode and JIT

Most modern "interpreted" languages are actually hybrids. Java source is compiled by javac into platform-independent bytecode (.class files); the Java Virtual Machine interprets that bytecode and its JIT compiler turns frequently executed methods into native machine code. CPython does something similar: it first compiles your source to bytecode, then a loop interprets the bytecode. We can see it with the dis module:

import dis
def area(r):
    return 3.14 * r * r
dis.dis(area)

Python 3.14 prints:

  2           RESUME                   0

  3           LOAD_CONST               0 (3.14)
              LOAD_FAST_BORROW         0 (r)
              BINARY_OP                5 (*)
              LOAD_FAST_BORROW         0 (r)
              BINARY_OP                5 (*)
              RETURN_VALUE

These are instructions for a stack-based virtual machine, not for the real CPU (the exact instruction names change between Python versions). So the question "is Python compiled or interpreted?" has the honest answer: compiled to bytecode, and the bytecode is interpreted.

  Java:    .java --javac--> .class (bytecode) --JVM: interpret + JIT--> machine code
  Python:  .py   --compile--> bytecode (.pyc)  --CPython VM loop------> results

Summary Table of Language Processors

Processor

Input

Output

Main job

Preprocessor

Source with directives

Expanded source

Macros, file inclusion, conditional compilation

Compiler

High-level source

Assembly or machine code

Translation and error detection

Assembler

Assembly

Relocatable object code

Mnemonics and labels to machine code

Linker

Object files, libraries

Executable

Symbol resolution and relocation

Loader

Executable

Program in memory, running

Allocation, relocation, loading, starting

Interpreter

Source (or bytecode) + input

Program's output

Direct execution


Common Mistakes Students Make

  • Thinking "undefined reference" is a compiler error. The compiler only needs a declaration. A missing definition is discovered by the linker.

  • Thinking the preprocessor understands C. It is pure text substitution, which is why #define SQUARE(x) x*x gives SQUARE(1+2) = 1+2*1+2 = 5, not 9. Always parenthesise macro parameters.

  • Mixing up linker and loader. The linker builds the executable file; the loader puts it into memory and starts it. (A linking loader does both.)

  • Saying an interpreter "converts the program to machine code line by line". A pure interpreter does not produce machine code at all; it performs the actions itself. Producing machine code at run time is what a JIT compiler does.

  • Relocating data values. Relocation changes address fields only, never ordinary constants.


GATE / Interview Questions

1. List the stages a C program goes through from source to execution.

Preprocessing (expand includes and macros), compilation (C to assembly), assembly (assembly to relocatable object code), linking (combine objects and libraries into an executable), and loading (copy into memory, relocate/bind, start execution).

2. Why does an assembler need two passes?

Because of forward references: an instruction may use a label defined later. Pass 1 computes every label's address using the location counter and builds the symbol table; pass 2 generates code using it. A one-pass assembler must instead backpatch the holes once labels become known.

3. A program assembled with origin 0 has the instruction LOAD 40 at address 8 and the constant 7 at address 40. It is loaded at address 3000. What are the contents after relocation?

The instruction moves to address 3008 and its address field becomes 3040: LOAD 3040. The constant moves to address 3040 and stays 7, because it is data, not an address.

4. What are the functions of a loader?

Allocation of memory, linking of object modules (in a linking loader), relocation of address-dependent code, and loading the code and data into memory, followed by transferring control to the program's entry point.

5. Static vs dynamic linking: give one advantage of each.

Static: the executable is self-contained and has no run-time library version problems. Dynamic: smaller executables, one shared copy of the library in memory, and library fixes apply without relinking.

6. Is Java compiled or interpreted?

Both. javac compiles source to bytecode; the JVM interprets bytecode and JIT-compiles hot methods to native code.

7. Which is generally faster at run time, compiled or interpreted code, and why?

Compiled code, because the analysis and translation are done once before execution, whereas an interpreter repeats the analysis of each statement every time it executes.

8. What is a bootstrap loader?

A small program stored in firmware/ROM that runs when the machine is powered on and loads the operating system (or a bigger loader) into memory.


Summary

  • A C program passes through the preprocessor, compiler, assembler and linker, and is then started by the loader. gcc is a driver that runs these tools.

  • The preprocessor does text substitution: includes, macros, conditional compilation, comment removal.

  • The assembler produces relocatable object code with holes and relocation entries for unknown addresses; a two-pass assembler handles forward references with a location counter and symbol table.

  • The linker performs symbol resolution and relocation; "undefined reference" is a linker error. Static linking copies libraries in (816,936 vs 16,008 bytes in our test); dynamic linking shares them at run time.

  • The loader allocates, relocates, loads and starts the program; types include absolute, relocating, linking, dynamic and bootstrap loaders.

  • An interpreter executes the program directly without saving a target program. Java and Python are hybrids: compiled to bytecode, then interpreted and (for Java) JIT-compiled.

Next, in Phases of a Compiler, we open up the compiler box and follow one statement through each of its internal phases.