From 10c9f64f592198d78aad11ebc676629d92ca6576 Mon Sep 17 00:00:00 2001 From: Frederick Yin Date: Mon, 22 Aug 2022 17:04:19 +0800 Subject: Project 07: VM translator part 1 --- projects/hack-vm/__main__.py | 63 ++++++++++++++++++++ projects/hack-vm/arith_logic.py | 26 ++++++++ projects/hack-vm/compare.py | 32 ++++++++++ projects/hack-vm/memory.py | 129 ++++++++++++++++++++++++++++++++++++++++ projects/hack-vm/utils.py | 12 ++++ 5 files changed, 262 insertions(+) create mode 100644 projects/hack-vm/__main__.py create mode 100644 projects/hack-vm/arith_logic.py create mode 100644 projects/hack-vm/compare.py create mode 100644 projects/hack-vm/memory.py create mode 100644 projects/hack-vm/utils.py (limited to 'projects/hack-vm') 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 +# when is one of local, argument, this and that +PUSH_ASM = ( + """@{segment} +D=M +@{index} +A=D+A +D=M +""" + + PUSH_COMMON_ASM +) + +# when is one of static, temp and pointer +PUSH_FIXED_ASM = ( + """@{addr} +D=M +""" + + PUSH_COMMON_ASM +) + +# push constant +PUSH_CONSTANT_ASM = ( + """@{constant} +D=A +""" + + PUSH_COMMON_ASM +) + + +# pop +# when 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 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) -- cgit v1.2.3