6.4 MARIE Assembly Language & the Two-Pass Assembler

Theory: MARIE Assembly Language & the Two-Pass Assembler

Mnemonics vs Machine Code

The CPU only understands machine code: bit patterns such as 0001 0001 0000 0100. Humans write assembly language: one mnemonic instruction per line, such as Load 104. Each assembly instruction corresponds to exactly one machine instruction. An assembler is the program that translates assembly into machine code.

Different architectures use different mnemonics and formats for the same operation, which is why assembly is not portable.

Anatomy of a MARIE Source Line

Label,  Mnemonic  Operand    / comment
Loop,   Load      Count      / AC <- Count

Directives (pseudo-instructions)

Directives tell the assembler what to do; they are not translated into CPU instructions themselves.

Mini-example

X, DEC 35 reserves one word labelled X containing $35 = \text{0023}_{16}$. Y, DEC -23 stores the two’s complement of 23: $23 = \text{0017}$ → invert → FFE8 → +1 → FFE9.

Data must be placed after the Halt (or otherwise out of the instruction stream). The CPU cannot tell data from instructions: if execution runs into DEC 35 it will happily execute 0023 as JnS 023.

The Two-Pass Assembler

Labels can be used before they are defined (a forward reference: Load X appears before the line X, DEC 35). So the assembler cannot finish line 1 until it has seen the whole program. The solution is to read the source twice.

Pass 1: build the symbol table.

1. Set the location counter (LC) from ORG (default 0).
2. For each line: if it has a label, record label → LC in the symbol table. Translate the mnemonic into its opcode (partial code; the address is left blank if it is a label). Increment LC by 1 (every instruction and every DEC/HEX takes one word).

Pass 2: complete the code. 3. For each line: replace each label operand by its address from the symbol table, convert DEC/HEX constants to 16-bit hex, and output the finished machine word.

Mini-example (as in the lecture)

        ORG 100
        Load X
        Add Y
        Store Z
        Halt
X,      DEC 35
Y,      DEC -23
Z,      HEX 0000
        END

Pass 1: LC runs 100, 101, … ; labels seen at 104, 105, 106 → symbol table X = 104, Y = 105, Z = 106. Partial code: 1 ???, 3 ???, 2 ???, 7000, … Pass 2: fill in → 1104, 3105, 2106, 7000, 0023, FFE9, 0000. This is exactly the addition program of 6.3.

Input and Output

Input copies a value typed by the user into the AC (AC ← InREG); Output displays the AC (OutREG ← AC). Neither uses its address field.

Mini-example

Read two numbers and print the second minus the first:

        ORG 100
        Input       / AC <- first number
        Store A
        Input       / AC <- second number
        Subt A      / AC <- second - first
        Output
        Halt
A,      DEC 0

Hex: 5000 2106 5000 4106 6000 7000 0000. With inputs 9 then 30 it outputs $30 - 9 = 21$ (hex 0015).

Translating Control Structures

MARIE has only one conditional instruction, Skipcond, which skips the next instruction. Every if and loop is built as “test, Skipcond, Jump”:

1. Compute a value in the AC whose sign answers the question (usually by subtracting: X − Y).
2. Skipcond with the condition under which you want to stay on the straight path.
3. The next line is a Jump to the “other” path; it is skipped when the condition holds.

For $X \ge Y$ (or any “not” condition), test the opposite condition, $X \lt Y$, and simply swap which code is the THEN part and which is the ELSE part.

If / else template

        Load X
        Subt Y
        Skipcond 800    / X - Y > 0 ?  -> skip the Jump, run THEN
        Jump Else
Then,   ...             / THEN part
        Jump EndIf
Else,   ...             / ELSE part
EndIf,  ...

While-loop template (while X < Y do body)

While,  Load X
        Subt Y
        Skipcond 000    / X - Y < 0 ?  -> skip the Jump, run the body
        Jump EndW
        ...             / body
        Jump While
EndW,   ...

Counting-loop template (repeat N times, N counts down)

Loop,   Load N
        Skipcond 800    / N > 0 ?  -> skip the Jump, run the body
        Jump Done
        ...             / body
        Load N
        Subt One
        Store N
        Jump Loop
Done,   ...

Subroutines with JnS and JumpI

A subroutine starts with one word reserved for the return address, followed by its code, and ends with JumpI on that word:

        JnS Sub         / M[Sub] <- return address, PC <- Sub + 1
        ...             / execution resumes here
Sub,    HEX 0000        / holds the return address
        ...             / subroutine body (starts at Sub + 1)
        JumpI Sub       / PC <- M[Sub]: return

Parameters are passed through agreed memory locations (MARIE has no stack). Remember that JnS overwrites the AC.

Worked Examples

        ORG 100
        Load X
        Add Y
        Store Z
        Halt
X,      DEC 35
Y,      DEC -23
Z,      HEX 0000
        END

if (A < B) Max = B; else Max = A;
output Max;

        ORG 100
Loop,   Load N
        Skipcond 800    / N > 0 ? skip the Jump
        Jump Done
        Load Sum
        Add N           / Sum = Sum + N
        Store Sum
        Load N
        Subt One        / N = N - 1
        Store N
        Jump Loop
Done,   Load Sum
        Output
        Halt
N,      DEC 5
Sum,    DEC 0
One,    DEC 1

while (X < Limit) X = X + X;
output X;