Project 07: VM translator part 1

5 files changed, 262 insertions, 0 deletions

diff --git a/projects/hack-vm/__main__.py b/projects/hack-vm/__main__.py
new file mode 100644
index 0000000..a1dce1f
--- /dev/null
+++ b/projects/hack-vm/__main__.py
@@ -0,0 +1,63 @@
+from argparse import ArgumentParser
+from .memory import translate_memory
+from .arith_logic import translate_arith_logic
+from .compare import translate_compare
+from .utils import *
+
+
+def vm_translate(input_path):
+    # program name, for static variable labels
+    input_fn = input_path.split("/")[-1]
+    prog = input_fn[:-3] if input_fn.endswith(".vm") else input_fn
+
+    try:
+        input_file = open(input_path)
+    except:
+        exit_on_error(f"Cannot open input file: {input_fn}", EXIT_CODE_FILE_ERROR)
+
+    # load all vm commands from file
+    vm_cmds = []
+    line = input_file.readline()
+    while line:
+        cmd = line.rstrip("\n").split("//", maxsplit=1)[0].strip()
+        if cmd:
+            vm_cmds.append(cmd)
+        line = input_file.readline()
+
+    input_file.close()
+
+    asm = ""
+    for cmd in vm_cmds:
+        # tokenize vm_line, hand to sub-translators based on first token
+        match cmd.split():
+            case []:
+                continue
+            case [("push" | "pop") as action, segment, index]:
+                asm += translate_memory(action, segment, index, prog)
+            case [("add" | "sub" | "neg" | "and" | "or" | "not") as command]:
+                asm += translate_arith_logic(command)
+            case [("lt" | "eq" | "gt") as command]:
+                asm += translate_compare(command)
+            case _:
+                exit_on_error(
+                    f"Syntax error: invalid command: {cmd}", EXIT_CODE_SYNTAX_ERROR
+                )
+
+    output_path = (
+        input_path[:-3] + ".asm" if input_path.endswith(".vm") else input_path + ".asm"
+    )
+    try:
+        output_file = open(output_path, "w")
+    except:
+        exit_on_error(f"Cannot open output file: {output_fn}", EXIT_CODE_FILE_ERROR)
+
+    output_file.write(asm)
+    output_file.close()
+    print(f"Assembly written to {output_path}")
+
+
+if __name__ == "__main__":
+    parser = ArgumentParser("hack-vm")
+    parser.add_argument("input_path", help="input file in HACK VM")
+    args = parser.parse_args()
+    vm_translate(args.input_path)
diff --git a/projects/hack-vm/arith_logic.py b/projects/hack-vm/arith_logic.py
new file mode 100644
index 0000000..6716ad9
--- /dev/null
+++ b/projects/hack-vm/arith_logic.py
@@ -0,0 +1,26 @@
+from .utils import *
+
+# common preamble to add, sub, and, or
+BINARY_COMMON_ASM = """@SP
+AM=M-1
+D=M
+A=A-1
+"""
+
+# common preamble to neg and not
+UNARY_COMMON_ASM = """@SP
+A=M-1
+"""
+
+ARITH_LOGIC_ASM = {
+    "add": BINARY_COMMON_ASM + "M=D+M\n",
+    "sub": BINARY_COMMON_ASM + "M=M-D\n",
+    "and": BINARY_COMMON_ASM + "M=D&M\n",
+    "or": BINARY_COMMON_ASM + "M=D|M\n",
+    "neg": UNARY_COMMON_ASM + "M=-M\n",
+    "not": UNARY_COMMON_ASM + "M=!M\n",
+}
+
+
+def translate_arith_logic(command):
+    return ARITH_LOGIC_ASM[command]
diff --git a/projects/hack-vm/compare.py b/projects/hack-vm/compare.py
new file mode 100644
index 0000000..1565b11
--- /dev/null
+++ b/projects/hack-vm/compare.py
@@ -0,0 +1,32 @@
+from .utils import *
+
+# template for lt, gt, and eq
+COMPARE_ASM = """@SP
+AM=M-1
+D=M
+A=A-1
+D=M-D
+M=0
+@END_{tag}
+D;{jmp}
+@SP
+A=M-1
+M=-1
+(END_{tag})
+"""
+
+# exact complement of VM command which leaves top of stack false
+JMP = {
+    "lt": "JGE",
+    "eq": "JNE",
+    "gt": "JLE",
+}
+
+tag_idx = 0
+
+
+def translate_compare(command):
+    global tag_idx
+    asm = COMPARE_ASM.format(tag=f"{command.upper()}_{tag_idx}", jmp=JMP[command])
+    tag_idx += 1
+    return asm
diff --git a/projects/hack-vm/memory.py b/projects/hack-vm/memory.py
new file mode 100644
index 0000000..ad22482
--- /dev/null
+++ b/projects/hack-vm/memory.py
@@ -0,0 +1,129 @@
+from .utils import *
+
+# common instructions all push commands end with
+PUSH_COMMON_ASM = """@SP
+A=M
+M=D
+@SP
+M=M+1
+"""
+
+# push <segment> <index>
+# when <segment> is one of local, argument, this and that
+PUSH_ASM = (
+    """@{segment}
+D=M
+@{index}
+A=D+A
+D=M
+"""
+    + PUSH_COMMON_ASM
+)
+
+# when <segment> is one of static, temp and pointer
+PUSH_FIXED_ASM = (
+    """@{addr}
+D=M
+"""
+    + PUSH_COMMON_ASM
+)
+
+# push constant <constant>
+PUSH_CONSTANT_ASM = (
+    """@{constant}
+D=A
+"""
+    + PUSH_COMMON_ASM
+)
+
+
+# pop <segment> <index>
+# when <segment> is one of local, argument, this and that
+POP_ASM = """@{index}
+D=A
+@{segment}
+M=M+D
+@SP
+M=M-1
+A=M
+D=M
+@{segment}
+A=M
+M=D
+@{index}
+D=A
+@{segment}
+M=M-D
+"""
+
+# when <segment> is one of static, temp and pointer
+POP_FIXED_ASM = """@SP
+M=M-1
+A=M
+D=M
+@{addr}
+M=D
+"""
+
+SEGMENT_PTR = {
+    "local": "LCL",
+    "argument": "ARG",
+    "this": "THIS",
+    "that": "THAT",
+}
+
+SEGMENT_SIZE = {
+    "pointer": 2,  # 3..4, i.e. THIS and THAT
+    "temp": 8,  # 5..12
+    "static": 240,  # 16..255
+}
+
+
+def translate_memory(action, segment, index, prog):
+    try:
+        index = int(index)
+    except ValueError:
+        exit_on_error(
+            f"Syntax error: invalid segment index {index}", EXIT_CODE_SYNTAX_ERROR
+        )
+
+    if index < 0:
+        exit_on_error(
+            f"Address error: negative segment index {index}", EXIT_CODE_ADDR_ERROR
+        )
+
+    asm = ""
+    if segment in ["local", "argument", "this", "that"]:
+        # these segments are dynamic
+        asm = PUSH_ASM if action == "push" else POP_ASM
+        return asm.format(segment=SEGMENT_PTR[segment], index=index)
+    elif segment in ["static", "temp", "pointer"]:
+        # these segments have a fixed location and size on memory
+        if index >= SEGMENT_SIZE[segment]:
+            exit_on_error(
+                f"Address error: segment index {index} exceeds size of {segment}",
+                EXIT_CODE_ADDR_ERROR,
+            )
+
+        addr = ""
+        if segment == "static":
+            # translate "static i" in "prog.vm" into "@prog.i"
+            addr = f"{prog}.{index}"
+        elif segment == "temp":
+            addr = str(5 + index)
+        else:
+            # "pointer 0" is THIS, "pointer 1" is THAT
+            addr = "THIS" if index == 0 else "THAT"
+
+        asm = PUSH_FIXED_ASM if action == "push" else POP_FIXED_ASM
+        return asm.format(addr=addr)
+    elif segment == "constant":
+        if action == "pop":
+            exit_on_error(
+                f"Syntax error: popping to constant not allowed", EXIT_CODE_SYNTAX_ERROR
+            )
+        return PUSH_CONSTANT_ASM.format(constant=index)
+    else:
+        exit_on_error(
+            f"Syntax error: invalid memory segment {segment}", EXIT_CODE_SYNTAX_ERROR
+        )
diff --git a/projects/hack-vm/utils.py b/projects/hack-vm/utils.py
new file mode 100644
index 0000000..99c029a
--- /dev/null
+++ b/projects/hack-vm/utils.py
@@ -0,0 +1,12 @@
+from sys import stderr
+
+EXIT_CODE_FILE_ERROR = 1
+EXIT_CODE_ILLEGAL_CHAR = 2
+EXIT_CODE_SIZE_EXCEEDED = 3
+EXIT_CODE_SYNTAX_ERROR = 4
+EXIT_CODE_ADDR_ERROR = 5
+EXIT_CODE_SYMBOL_ERROR = 6
+
+def exit_on_error(msg, code):
+    print(msg, file=stderr)
+    exit(code)