# teaching machines

## CS 352 Lecture 21 – Assembler Cont’d

October 26, 2016 by . Filed under cs352, fall 2016, lectures.

Dear students,

Today we continue work on our assembler. In short, this is our development checklist:

1. strip out the cruft (unnecessary whitespace, comments)
2. identify addresses for all code labels
3. resolve all symbols to addresses
4. convert text instructions to binary

We accomplished steps 1 and 2 last time, but didn’t test it. Let’s write a quick infinite loop to see if it worked.

Resolving all symbols will look a bit like this:

for each instruction
if instruction is @
if symbol table does not have identifier
"declare" a new symbol and resolve a slot in RAM
look up identifier in symbol table
replace it with address

Once all addresses have been resolved, we have only a mathematical facade over the machine code. We can convert each instruction to its machine code cousin directly via this algorithm:

for each instruction
if instruction is @
else
figure out assignment destination bits
figure out computation bits
figure out jump bits

'111' + computation bits + assignment destination bits + jump bits

If we have any extra time today, I can’t think of a better way to spend it than collectively playing Human Resource Machine.

• The next homework is posted. You will need to git pull template master to get the PDF and updated grader. Due before November 9. No later week submission on this one! It’s just three parts.

See you next class!

Sincerely,

P.S. Here’s the code we wrote together…

#### assembler.rb

#!/usr/bin/env ruby

symbols = {
'R0' => 0,
'R1' => 1,
'R2' => 2,
'R3' => 3,
'R4' => 4,
'R5' => 5,
'R6' => 6,
'R7' => 7,
'R8' => 8,
'R9' => 9,
'R10' => 10,
'R11' => 11,
'R12' => 12,
'R13' => 13,
'R14' => 14,
'R15' => 15,
'KBD' => 24576,
'SCREEN' => 16384,
'SP' => 0,
'LCL' => 1,
'ARG' => 2,
'THIS' => 3,
'THAT' => 4,
}

# Strip out cruft.
src.gsub!(/\/\/.*/, '')
src.gsub!(/\n{2,}/, '')
src.gsub!(/^ +/, '')
src.gsub!(/ +$/, '') # Determine addresses for labels. instructions = [] src.lines.each do |line| if line =~ /$([A-Za-z].*)$/ label =$1
symbols[label] = instructions.size
else
instructions << line
end
end

next_available = 16

# Resolve symbols
instructions.map! do |instruction|
if instruction =~ /^@([A-Za-z].*)/
id = $1 if !symbols.has_key?(id) symbols[id] = next_available next_available += 1 end "@#{symbols[id]}" # '0' + '%015b' % symbols[id] else instruction end end destinations = { nil => '000', 'M' => '001', 'D' => '010', 'MD' => '011', 'A' => '100', 'AM' => '101', 'AD' => '110', 'AMD' => '111', } jumps = { nil => '000', 'JGT' => '001', 'JEQ' => '010', 'JGE' => '011', 'JLT' => '100', 'JNE' => '101', 'JLE' => '110', 'JMP' => '111', } expressions = { '0' => '0101010', '1' => '0111111', '-1' => '0111010', 'D' => '0001100', 'A' => '0110000', '!D' => '0001101', '!A' => '0110001', '-D' => '0001111', '-A' => '0110011', 'D+1' => '0011111', 'A+1' => '0110111', 'D-1' => '0001110', 'A-1' => '0110010', 'D+A' => '0000010', 'D-A' => '0010011', 'A-D' => '0000111', 'D&A' => '0000000', 'D|A' => '0010101', 'M' => '1110000', '!M' => '1110001', '-M' => '1110011', 'M+1' => '1110111', 'M-1' => '1110010', 'D+M' => '1000010', 'D-M' => '1010011', 'M-D' => '1000111', 'D&M' => '1000000', 'D|M' => '1010101' } # puts instructions instructions.map! do |instruction| if instruction =~ /^@(\d+)/ address =$1
instruction =~ /^(?:([AMD]{1,3})=)?(.*?)(?:;(J.*))?$/ computation_bits = expressions[$2]
destination_bits = destinations[$1] jump_bits = jumps[$3]