CS 352 Lecture 21 – Assembler Cont’d

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 @
    '@' + 15-bit address
  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.

Here’s your TODO list:

  • 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,
}

src = File.read(ARGV[0])

# 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
    '0' + '%015b' % address
  else
    instruction =~ /^(?:([AMD]{1,3})=)?(.*?)(?:;(J.*))?$/
    computation_bits = expressions[$2]
    destination_bits = destinations[$1]
    jump_bits = jumps[$3]

    "111#{computation_bits}#{destination_bits}#{jump_bits}"
  end
end

puts instructions

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *