Práctica 6 : El ensamblador

Recursos

Introducción

La primera mitad de los proyectos en la cual describimos y construimos el hardware fue culminada, ahora con este proyecto iniciamos la segunda mitad. Esta se enfoca en la jerarquía del software de los computadores, por lo que debemos empezar con el módulo básico, el ensamblador. En este caso, nuestro principal objetivo es desarrollar un ensamblador Hack, que traduzca un programa escrito en lenguaje ensamblador Hack y genere código binario que pueda ser ejecutador en el hardware hack anteriormente construido.

¿Qué hacer para desarrollarlo?

Se debe escribir un ensamblador en un lenguaje de alto nivel como Python, el cual cuando se le cargue un archivo .asm que contiene un programa de el lenguaje ensamblador Hack, proporcione el código binario Hack correcto y lo almacene en un archivo.
Debemos asegurarnos que la salida producida por nuestro ensamblador sea idéntica a la salida producida por el ensamblador suministrado por nand2tetris.

Desarrollo

En primer lugar, debemos tener claro que vamos a desarrollar un ensamblador en un lenguaje de alto nivel (en nuestro caso Python) que nos permitirá traducir comandos como @128, D=M, D;JMP, a unos y ceros. Pero al ver en los códigos pong.asm, max.asm, etc vemos, que hay un montón de nombres como "temp" o "WHILELOOP" entre otros, por lo que necesitaremos preprocesar el archivo antes de comenzar a traducir. Necesitamos guardar el número de línea de (WHILELOOP) en algún arreglo, y también tendremos que devolverlo cuando se llame en @WHILELOOP.

También, es necesario asignar ubicaciones de memoria para "value" y "temp". Podemos usar las ubicaciones desde R16 en adelante para almacenar esas variables. Entonces, cuando se revise el código, la primera vez que nos encontremos con "value" sabemos que debemos darle una ranura en la memoria para un futuro uso, y la próxima vez que veamos este "valor", solo devolveremos la ubicación de memoria que le asignamos.

Pero esto no lo podemos hacer simplemente revisando el archivo, debemos revisar el archivo dos veces. La primera vez limpiamos los comentarios y también limpiamos las etiquetas, pero cuando limpiamos las etiquetas como (WHILELOOP.), hacemos un seguimiento de su número de línea y lo guardamos en un arreglo. Después de este proceso, sabemos exactamente qué devolver en la segunda ronda de lectura del archivo cuando se llama a @WHILELOOP.

De este modo, para resolver este problema se tuvo que separar en tres partes el desarrollo:

Parser. Se usa para leer en el archivo, guardar los comandos, guardar el número de línea, eliminar comentarios, después de adquirir todos los comandos, parser puede usar una variable @index para controlar el proceso de decodificación (commands[@index] será el comando actual).
Code. Después de obtener una línea del analizador, la evaluamos y la comparamos con nuestro Regex para ver qué tipo de instrucción es: Instrucción A o Instrucción C. Luego escriba los códigos binarios correspondientes en el archivo de pirateo.
Assembler. Crea un code y un parser, para luego utilizarlos y finalizar todo el proceso.

Procesado del archivo Add.asm en el ensamblador desarrollado.

Parser

import sys, re

A_COMMAND = 'A'

C_COMMAND = 'C'

L_COMMAND = 'L'

class Parser:

"""Lee un comando en lenguaje ensamblador, lo analiza y proporciona acceso a los componentes del comando.

Elimina todos los espacios en blanco y comentarios."""

def __init__(self, filepath):

"""Abre el flujo de entrada/archivo y se prepara para analizarlo"""

try:

with open(filepath, 'r') as f:

self.commands = list(filter(len,

[re.sub('//.*$', '', l).strip() for l in f]))

except FileNotFoundError:

print("No pudo encontrar %s" % (filepath))

def hasMoreCommands(self):

"""¿Hay más comandos en la entrada?"""

return len(self.commands) > 0

def next(self):

"""Lee el siguiente comando de la entrada y lo convierte en el comando actual.

Debe llamarse solo si hasMoreCommands() es verdadero."""

self.command = self.commands.pop(0)

def commandType(self):

"""Devuelve el tipo del comando actual:

* A_COMMAND para @Xxx donde Xxx es un símbolo o un número decimal

* C_COMMAND para dest=comp;saltar

* L_COMMAND (pseudocomando) para (Xxx) donde Xxx es un símbolo"""

if self.command[0] == '@':

return A_COMMAND

elif self.command[0] == '(' and self.command[-1] == ')':

return L_COMMAND

return C_COMMAND

def symbol(self):

"""Devuelve el símbolo o decimal Xxx del comando actual @Xxx o (Xxx).

Debe llamarse solo cuando commandType() es A_COMMAND o

L_COMMAND"""

return self.command.strip('@()')

def dest(self):

"""Devuelve el mnemotécnico dest en el comando C actual

Debe llamarse solo cuando commandType() es C_COMMAND"""

if '=' not in self.command:

return ''

return self.command.split('=')[0]

def comp(self):

"""Devuelve el mnemotécnico de compilación en el comando C

actual Debe llamarse cuando comandType() es C_COMMAND"""

return self.command.split('=')[-1].split(';')[0]

def jump(self):

"""Devuelve el mnemotécnico de salto en el comando C actual

Debe llamarse solo cuando commandType() es C_COMMAND"""

if ';' not in self.command:

return ''

return self.command.split('=')[-1].split(';')[-1]

if __name__ == "__main__":

if len(sys.argv) < 2:

print("Use: python Parser.py ARCHIVO")

else:

print("Corriendo Parser")

for arg in sys.argv[1:]:

p = Parser(arg)

while p.hasMoreCommands():

p.next()

print("Symbol: %s, instruction: %s, dest: %s, comp: %s, jump: %s"

% (p.symbol(), p.commandType(), p.dest(), p.comp(), p.jump()))

Code

import sys

from Parser import *

class Code:

"""Traduce los nemotécnicos del lenguaje ensamblador de Hack a códigos binarios"""

# Usando las direcciones definidas en el libro de texto.

dest_map = {'': '000', 'M': '001', 'D': '010', 'MD': '011', 'A': '100',

'AM': '101', 'AD': '110', 'AMD': '111'}

a0_comp = {'0': '101010', '1': '111111', '-1': '111010', 'D': '001100',

'A': '110000', '!D': '001101', '-D': '001111', '-A': '110011',

'D+1': '011111', 'A+1': '110111', 'D-1': '001110',

'A-1': '110010', 'D+A': '000010', 'D-A': '010011',

'A-D': '000111', 'D&A': '000000', 'D|A': '010101'}

a1_comp = {'M': '110000', '!M': '110001', '-M': '110011', 'M+1': '110111',

'M-1': '110010', 'D+M': '000010', 'D-M': '010011',

'M-D': '000111', 'D&M': '000000', 'D|M': '010101'}

jump_map = {'': '000', 'JGT': '001', 'JEQ': '010', 'JGE': '011',

'JLT': '100', 'JNE': '101', 'JLE': '110', 'JMP': '111'}

@staticmethod

def dest(mnemonic):

"""Devuelve el código binario del nemotécnico dest - 3 bits"""

return Code.dest_map[mnemonic]

@staticmethod

def comp(mnemonic):

"""Devuelve el código binario de la mnemónica comp - 7 bits"""

if mnemonic in Code.a1_comp:

return '1' + Code.a1_comp[mnemonic]

elif mnemonic in Code.a0_comp:

return '0' + Code.a0_comp[mnemonic]

@staticmethod

def jump(mnemonic):

"""Devuelve el código binario del mnemotécnico de salto - 3 bits"""

return Code.jump_map[mnemonic]

if __name__ == '__main__':

if len(sys.argv) < 2:

print("Use: python3 Code.py FILE")

sys.exit(1)

for arg in sys.argv[1:]:

p = Parser(arg)

while p.hasMoreCommands():

p.next()

if (p.commandType() == A_COMMAND):

instruction = '{0:016b}'.format(int(p.symbol()))

elif (p.commandType() == C_COMMAND):

parts = []

parts.append('111')

parts.append(Code.comp(p.comp()))

parts.append(Code.dest(p.dest()))

parts.append(Code.jump(p.jump()))

instruction = ''.join(parts)

else:

instruction = p.symbol()

print(instruction)

Assembler

import sys, os

from Parser import *

from Code import *

from SymbolTable import *

class Assembler:

"""Maneja la entrada/salida de archivos"""

def __init__(self, files):

self.files = files

self.table = SymbolTable()

def hasFile(self):

return len(self.files) > 0

def softPass(self):

"""Hace un pase para determinar la ubicación de las etiquetas (Xxx)"""

filename = self.files[0]

p = Parser(filename)

current_address = 0

while p.hasMoreCommands():

p.next()

cmd_type = p.commandType()

if cmd_type is A_COMMAND or cmd_type is C_COMMAND:

current_address += 1

elif cmd_type is L_COMMAND:

self.table.addPair(p.symbol(), current_address)

def getAddress(self, symbol):

if symbol.isdigit():

return symbol

else:

if not self.table.contains(symbol):

self.table.addPair(symbol, self.current_address)

self.current_address += 1

return self.table.address(symbol)

def translateFile(self):

"""Traduce el siguiente archivo en la cola"""

filename = self.files.pop(0)

p = Parser(filename)

if filename.endswith('.asm'):

fileout = filename.replace('.asm', '.hack')

else:

fileout = filename + '.hack'

f = open(fileout, 'w')

print("Translating %s" % (filename))

self.current_address = 16

while p.hasMoreCommands():

p.next()

if p.commandType() is A_COMMAND:

address = self.getAddress(p.symbol())

instruction = '{0:016b}'.format(int(address))

elif p.commandType() is C_COMMAND: # dest=comp;jump

instruction = ''.join(['111', Code.comp(p.comp()),

Code.dest(p.dest()), Code.jump(p.jump())])

else: # L_COMMAND (Xxx)

continue

print(instruction, end='\n', file=f)

f.close()

if __name__ == '__main__':

if len(sys.argv) < 2:

print("Use: python3 Assembler.py FILE")

sys.exit(1)

a = Assembler(sys.argv[1:])

while a.hasFile():

a.softPass()

a.translateFile()

Testeo con programas

Para comprobar que las salidas de nuestro ensamblador sean las correctas y concuerden con los resultados del ensamblador que proporciona nand2tetris debemos utilizar el Hack Assembler de la Software Suite de nand2tetris el cual nos garantiza si nuestro ensamblador genera el código correcto.

Add.asm

// This file is part of www.nand2tetris.org

// and the book "The Elements of Computing Systems"

// by Nisan and Schocken, MIT Press.

// File name: projects/06/add/Add.asm

// Computes R0 = 2 + 3 (R0 refers to RAM[0])

@2

D=A

@3

D=D+A

@0

M=D

Resultados obtenidos

Como ya vimos en la anterior práctica, este suma las constantes 2 y 3 y pone el resultado en R0.‎

Para hacer la prueba, cargamos el programa Add.asm como archivo fuente en el Hack Assembler, cargamos el archivo a comparar con el resultado del ensamblador de Hack y analizamos los resultados. Vemos que, el código binario suministrado por el Assembler Hack está de acuerdo con el archivo de comparación.

Max.asm

// This file is part of www.nand2tetris.org

// and the book "The Elements of Computing Systems"

// by Nisan and Schocken, MIT Press.

// File name: projects/06/max/Max.asm

// Computes R2 = max(R0, R1) (R0,R1,R2 refer to RAM[0],RAM[1],RAM[2])

@R0

D=M // D = first number

@R1

D=D-M // D = first number - second number

@OUTPUT_FIRST

D;JGT // if D>0 (first is greater) goto output_first

@R1

D=M // D = second number

@OUTPUT_D

0;JMP // goto output_d

(OUTPUT_FIRST)

@R0

D=M // D = first number

(OUTPUT_D)

@R2

M=D // M[2] = D (greatest number)

(INFINITE_LOOP)

@INFINITE_LOOP

0;JMP // infinite loop

Resultados obtenidos

Asimismo, se pudo observar en la anterior práctica que este programa calcula max(R0,R1) y pone el resultado en R2.‎

Para hacer la prueba, cargamos el programa Max.asm como archivo fuente en el Hack Assembler, cargamos el archivo a comparar con el resultado del ensamblador de Hack y analizamos los resultados. Vemos que, el código binario suministrado por el Assembler Hack está de acuerdo con el archivo de comparación.

Rect.asm

// This file is part of www.nand2tetris.org

// and the book "The Elements of Computing Systems"

// by Nisan and Schocken, MIT Press.

// File name: projects/06/rect/Rect.asm

// Draws a rectangle at the top-left corner of the screen.

// The rectangle is 16 pixels wide and R0 pixels high.

@0

D=M

@INFINITE_LOOP

D;JLE

@counter

M=D

@SCREEN

D=A

@address

M=D

(LOOP)

@address

A=M

M=-1

@address

D=M

@32

D=D+A

@address

M=D

@counter

MD=M-1

@LOOP

D;JGT

(INFINITE_LOOP)

@INFINITE_LOOP

0;JMP

Resultados obtenidos

‎De la misma manera, en prácticas anteriores se logró apreciar que este programa dibuja un rectángulo en la esquina superior izquierda de la pantalla. El rectángulo tiene 16 píxeles de ancho y R0 píxeles de alto.‎

Para hacer la prueba, cargamos el programa Rect.asm como archivo fuente en el Hack Assembler, cargamos el archivo a comparar con el resultado del ensamblador de Hack y analizamos los resultados. Vemos que, el código binario suministrado por el Assembler Hack está de acuerdo con el archivo de comparación.

Pong.asm

// This file is part of www.nand2tetris.org

// and the book "The Elements of Computing Systems"

// by Nisan and Schocken, MIT Press.

// File name: projects/06/pong/Pong.asm

// The Pong game program was originally written in the high-level Jack language.

// The Jack code was then translated by the Jack compiler into VM code.

// The VM code was then translated by the VM translator into the Hack

// assembly code shown here.

@256

D=A

@SP

M=D

@133

0;JMP

@R15

M=D

@SP

AM=M-1

D=M

A=A-1

D=M-D

M=0

@END_EQ

D;JNE

@SP

A=M-1

M=-1

(END_EQ)

@R15

A=M

0;JMP

@R15

M=D

@SP

AM=M-1

D=M

A=A-1

D=M-D

M=0

@END_GT

D;JLE

@SP

A=M-1

M=-1

(END_GT)

@R15

A=M

0;JMP

@R15

M=D

@SP

AM=M-1

D=M

A=A-1

D=M-D

M=0

@END_LT

D;JGE

@SP

A=M-1

M=-1

(END_LT)

@R15

A=M

0;JMP

@5

D=A

@LCL

A=M-D

D=M

@R13

M=D

@SP

AM=M-1

D=M

@ARG

A=M

M=D

D=A

@SP

M=D+1

@LCL

D=M

@R14

AM=D-1

D=M

@THAT

M=D

@R14

AM=M-1

D=M

@THIS

M=D

@R14

AM=M-1

D=M

@ARG

M=D

@R14

AM=M-1

D=M

@LCL

M=D

@R13

A=M

0;JMP

@SP

A=M

M=D

@LCL

D=M

@SP

AM=M+1

M=D

@ARG

D=M

@SP

AM=M+1

M=D

@THIS

D=M

@SP

AM=M+1

M=D

@THAT

D=M

@SP

AM=M+1

M=D

@4

D=A

@R13

D=D+M

@SP

D=M-D

@ARG

M=D

@SP

MD=M+1

@LCL

M=D

@R14

A=M

0;JMP

@0

D=A

@R13

M=D

@sys.init

D=A

@R14

M=D

@RET_ADDRESS_CALL0

D=A

@95

0;JMP

(RET_ADDRESS_CALL0)

(ball.new)

@15

D=A

@SP

AM=M+1

A=A-1

M=D

@1

D=A

@R13

M=D

@memory.alloc

D=A

@R14

M=D

@RET_ADDRESS_CALL1

D=A

@95

0;JMP

(RET_ADDRESS_CALL1)

@SP

AM=M-1

D=M

@THIS

M=D

@ARG

A=M

D=M

@SP

AM=M+1

A=A-1

M=D

@SP

AM=M-1

D=M

@THIS

A=M

M=D

@ARG

A=M+1

D=M

@SP

AM=M+1

A=A-1

M=D

@SP

AM=M-1

D=M

@THIS

A=M+1

M=D

@ARG

A=M+1

A=A+1

D=M

@SP

AM=M+1

A=A-1

M=D

@THIS

D=M

@10

D=D+A

@R13

M=D

@SP

AM=M-1

D=M

@R13

A=M

M=D

@ARG

D=M

@3

A=D+A

D=M

@SP

AM=M+1

A=A-1

M=D

@6

D=A

@SP

AM=M+1

A=A-1

M=D

@SP

AM=M-1

D=M

A=A-1

M=M-D

@THIS

D=M

@11

D=D+A

@R13

M=D

@SP

AM=M-1

D=M

@R13

A=M

M=D

@ARG

D=M

@4

A=D+A

D=M

@SP

AM=M+1

A=A-1

M=D

@THIS

D=M

@12

D=D+A

@R13

M=D

@SP

AM=M-1

D=M

@R13
...

Resultados obtenidos

Este programa es un juego de Pong para un solo jugador. Una pelota rebota en las "paredes" de la pantalla. El jugador intenta golpear la pelota con una paleta presionando las teclas del teclado de flecha izquierda y derecha. Por cada golpe exitoso, el jugador gana un punto y la paleta se encoge un poco, para hacer que el juego sea un poco más desafiante.

Para hacer la prueba, cargamos el programa Rect.asm como archivo fuente en el Hack Assembler, cargamos el archivo a comparar con el resultado del ensamblador de Hack y analizamos los resultados. Vemos que, el código binario suministrado por el Assembler Hack está de acuerdo con el archivo de comparación.