From Assembly to Machine Code

Every chapter since assembly1-1 has quietly leaned on labels — LOOP, DONE, N — without ever explaining how the assembler figures out the actual numeric address each one refers to. This chapter closes that loop for good: the real algorithm an assembler runs, how it builds and uses a symbol table, what those .FILL/.STRINGZ lines scattered through every example actually are, and — finally, in full mechanical detail — how assembly1-1's own linker stage resolves a label that lives in a completely different file.

The Problem: Forward References

Look back at assembly1-6's own summing loop: the very first real instruction, LD R1, N, refers to the label N — but N's own line doesn't appear until several lines later in the source file. To compute LD's PC-relative offset (per assembly1-3's formula), the assembler needs to know N's actual memory address — but if it only ever reads the file once, top to bottom, generating machine code as it goes, it would hit LD R1, N long before it has any idea where N will end up. This is a forward reference, and it's the exact problem the rest of this chapter exists to solve.

The Two-Pass Algorithm

Real assemblers — including LC-3's — solve this by reading the source file twice:

• Pass 1 — scan the file top to bottom without generating any machine code yet. Track a running location counter, starting at the program's origin address. Every time a label appears, record it — along with the current value of the location counter — in a symbol table. Advance the location counter by one for every instruction or data word, whether or not it has a label.
• Pass 2 — scan the file again, this time actually generating the 16-bit encoding for each line (per assembly1-5's bitfield formats). Any time an operand is a label, look its address up in the symbol table built during Pass 1, and compute whatever offset the instruction's own addressing mode needs.

By the time Pass 2 needs N's address, Pass 1 has already scanned the entire file and recorded it — forward references stop being a problem because the symbol table is fully built before any actual encoding happens.

Directives — Instructions to the Assembler, Not the CPU

A few lines in every example so far aren't real LC-3 instructions at all — they're assembler directives: instructions for the assembler itself, about how to lay out memory, that never get fetched or executed by the CPU.

A Worked Trace — Building the Symbol Table

Take assembly1-6's own summing loop, now with .ORIG/.END added, assembled starting at address x3000:

        .ORIG x3000
        AND R2, R2, #0      ; x3000
        LD  R1, N            ; x3001 — forward reference to N
LOOP    ADD R2, R2, R1      ; x3002
        ADD R1, R1, #-1     ; x3003
        BRp LOOP            ; x3004 — backward reference to LOOP
        ST  R2, SUM          ; x3005
        TRAP x25             ; x3006
N       .FILL #5            ; x3007
SUM     .FILL #0            ; x3008
        .END

Pass 1 walks top to bottom, building this symbol table:

Pass 2 now computes real offsets, using assembly1-3's PC + SEXT(offset9) formula (remembering the PC used is always the address after the current instruction):

• LD R1, N at x3001: offset = N − (x3001+1) = x3007 − x3002 = +5 (a forward reference, resolved only because Pass 1 already knew N's address)
• BRp LOOP at x3004: offset = LOOP − (x3004+1) = x3002 − x3005 = −3 (a backward reference — negative, since it points earlier in the program)
• ST R2, SUM at x3005: offset = SUM − (x3005+1) = x3008 − x3006 = +2

Object Files & the Linker — Multi-File Programs Resolved For Real

assembly1-1's own Exercise 2 asked what happens when main.asm references a label defined only in helper.asm. Here's the full mechanism: each file goes through its own independent two-pass assembly, producing its own object file and its own local symbol table. When main.asm's Pass 2 hits a reference to a label that never appeared anywhere in main.asm's own Pass 1 symbol table, the assembler can't compute a real offset — instead, it records that reference as unresolved, tagged as external, inside main.asm's object file.

The linker is what closes this gap: it reads every object file being combined, collects each one's exported symbols (labels meant to be visible to other files) and each one's unresolved external references, matches them up, and patches the real, final addresses into place — producing one complete, fully-resolved executable image with no unresolved references left anywhere.

Hands-On Exercises