Written by
doremin
on
on
VM Translator
VM Translator - 1
가상 머신 패러다임
컴파일 과정은 상당히 복잡한 프로세스다. 보통 고수준 언어를 대상 기계어로 번역하려면 별도의 컴파일러를 따로 만들어야한다. 따라서 언어와 기계어의 특성에 따라 수많은 컴파일러가 생겨나게 된다. 컴파일러에서 기계 종속성을 분리하는 방법 중 하나는 전체 컴파일 과정을 두 단계로 쪼개는 것이다. 먼저 첫 단게에서는 고수준 언어의 구문을 분석(parse)해서 명령들을 중간 처리 단계로 번역한다. 두 번째 단계에서는 이 중간 처리 단계들을 다시 대상 하드웨어의 기계어로 번역한다.
정리하자면 고수준 명령을 분석해서 나온 중간 처리 단계를 명령어(instruction)로 삼는 가상 머신(virtual machine)을 정의한다. 그리고 원래 하나였던 컴파일러를 두 개의 별도의 프로그램으로 분리한다. 앞 단계의 프로그램은 고수준 코드를 중간 VM 명령어로 번역하는 일을 한다. 두 번째 단계의 프로그램은 중간 VM 코드를 대상 플랫폼의 기계어로 번역한다.
이러한 가상 머신 언어 개념은 실용적 장점이 몇 가지 있다. 첫째로 가상 머신 구현 부분만 바꾸면, 여러 플랫폼의 컴파일러들을 상대적으로 쉽게 만들 수 있다. 따라서 VM 코드를 여러 종류의 하드웨어 플랫폼에 옮길 수 있게 되어, 코드 효율성과 하드웨어 및 프로그래밍 작성 비용 사이의 밸런스를 다양한 방식으로 맞출 수 있게 된다. 둘째로 여러 가지 언어의 컴파일러들이 같은 VM 백엔드를 공유함으로써, 코드를 공유하고 상호 운용하기 편해진다. 예를 들어 어떤 고수준 언어는 과학 계산에 유리하고, 또 어떤 언어는 사용자 인터페이스 구성이 편리한 경우가 있다. 이때 이 두 언어가 VM 컴파일 단계를 공유한다면, 한 언어에서 다른 언어의 루틴을 호출해서 활용하는 문법을 만들기가 훨씬 더 수월해진다.
스택 머신 모델
VM도 다른 프로그래밍 언어들처럼 산술 연산, 메모리 접근 연산, 프로그램 흐름 제어 연산, 서브루틴 호출 연산으로 구성된다. 이 언어를 구현하는 방법론은 여러 가지가 있다. 방법론들을 구별하는 핵심 기준 중 하나는 “VM 연산의 피연산자와 결괏값을 어디에 저장하는가?”이다. 아마도 가장 깔끔한 해결책은 스택 데이터 구조에 저장하는 방법일 것이다.
스택 머신 모델(stack machine model)에서 산술 명령은 스택의 최상단에서 피연산자를 꺼내고, 그 결과를 다시 스택의 최상단에 넣는다. 그 외의 다른 명령들의 경우에는 스택의 최상단과 지정된 메모리 주소 사이에 데이터가 이동된다.
스택 산술
스택 기반 산술은 간단한 문제다. 피연산자를 스택에서 꺼내서, 필요한 연산을 수행한 후에 결과를 다시 스택에 넣으면 된다. 예를 들어 덧셈이 처리되는 방식은 다음과 같다.
다른 연산에서 스택을 활용하는 방법도 완전히 똑같다. 예를 들어 고수준 언어로 작성한 d=(2-x)*(y+5)라는 표현식을 생각해 보자. 이 표현식을 스택 기반으로 계산한 것은 다음과 같다.
메모리 접근 명령
지금까지는 메모리 접근 명령을 의사명령(pseudo-command)인 pop과 push x로 설명했지만, 우리가 만들 VM은 다음과 같은 가상 메모리 세그먼트(virtual memory segment)들을 조작하는 메모리 접근 명령을 수행한다.
Parser
from enum import Enum
from constant import *
class Parser:
_command_table = {
"add": C_ARITHMETIC,
"sub": C_ARITHMETIC,
"neg": C_ARITHMETIC,
"eq": C_ARITHMETIC,
"gt": C_ARITHMETIC,
"lt": C_ARITHMETIC,
"and": C_ARITHMETIC,
"or": C_ARITHMETIC,
"not": C_ARITHMETIC,
"push": C_PUSH,
"pop": C_POP,
"label": C_LABEL,
"goto": C_GOTO,
"if-goto": C_IF,
"function": C_FUNCTION,
"return": C_RETURN,
"call": C_CALL
}
_nullary = ["add", "sub", "neg", "eq", "gt", "lt", "and", "or", "not", "return"]
_unary = ["label", "if-goto", "goto"]
_binary = ["push", "pop", "function", "call"]
def __init__(self, raw_data: str):
self.command_type = None
self.current_command = None
self.operator = None
self.operation_type = None
self.current_line = 0
self.raw_data = raw_data
def has_more_commands(self) -> bool:
if self.current_line >= len(self.raw_data):
return False
return True
def advance(self):
self.current_command = self.raw_data[self.current_line].split("//")[0].strip()
self.current_line += 1
if len(self.current_command) == 0:
self.command_type = None
return
self.operator = self.current_command.split()[0]
self.command_type = self._command_table[self.operator]
if self.operator in self._nullary:
self.operation_type = NULLARY
elif self.operator in self._unary:
self.operation_type = UNARY
else:
self.operation_type = BINARY
def arg1(self) -> str:
if self.operation_type == UNARY or self.operation_type == BINARY:
return self.current_command.split()[1]
def arg2(self) -> int:
if self.operation_type == BINARY:
return self.current_command.split()[2]
Code Writer
class CodeWriter:
def __init__(self):
self.file_name = None
self.stream = None
self.differ = 0
def set_file_name(self, file_name: str):
self.file_name = file_name
self.stream = open(self.file_name, "w")
def writer_arithmetic(self, command: str):
translated_str = None
if command == "add":
translated_str = self._popD() + \
"@R15\n" + \
"M=D\n" + \
self._popD() + \
"@R15\n" + \
"D=D+M\n" + \
self._pushD()
elif command == "sub":
translated_str = self._popD() + \
"@R15\n" + \
"M=D\n" + \
self._popD() + \
"@R15\n" + \
"D=D-M\n" + \
self._pushD()
elif command == "neg":
translated_str = self._popD() + \
"@0\n" + \
"D=A-D\n" + \
self._pushD()
elif command == "eq":
translated_str = self._popD() + \
"@R15\n" + \
"M=D\n" + \
self._popD() + \
"@R15\n" + \
"D=D-M\n" + \
f"@TRUE{self.differ}\n" + \
"D;JEQ\n" + \
f"@FALSE{self.differ}\n" + \
"0;JMP\n" + \
f"(TRUE{self.differ})\n" + \
"D=-1\n" + \
f"@END{self.differ}\n" + \
"0;JMP\n" + \
f"(FALSE{self.differ})\n" + \
"D=0\n" + \
f"@END{self.differ}\n" + \
"0;JMP\n" + \
f"(END{self.differ})\n" + \
self._pushD()
self.differ += 1
elif command == "gt":
translated_str = self._popD() + \
"@R15\n" + \
"M=D\n" + \
self._popD() + \
"@R15\n" + \
"D=D-M\n" + \
f"@TRUE{self.differ}\n" + \
"D;JGT\n" + \
f"@FALSE{self.differ}\n" + \
"0;JMP\n" + \
f"(TRUE{self.differ})\n" + \
"D=-1\n" + \
f"@END{self.differ}\n" + \
"0;JMP\n" + \
f"(FALSE{self.differ})\n" + \
"D=0\n" + \
f"@END{self.differ}\n" + \
"0;JMP\n" + \
f"(END{self.differ})\n" + \
self._pushD()
self.differ += 1
elif command == "lt":
translated_str = self._popD() + \
"@R15\n" + \
"M=D\n" + \
self._popD() + \
"@R15\n" + \
"D=D-M\n" + \
f"@TRUE{self.differ}\n" + \
"D;JLT\n" + \
f"@FALSE{self.differ}\n" + \
"0;JMP\n" + \
f"(TRUE{self.differ})\n" + \
"D=-1\n" + \
f"@END{self.differ}\n" + \
"0;JMP\n" + \
f"(FALSE{self.differ})\n" + \
"D=0\n" + \
f"@END{self.differ}\n" + \
"0;JMP\n" + \
f"(END{self.differ})\n" + \
self._pushD()
self.differ += 1
elif command == "and":
translated_str = self._popD() + \
"@R15\n" + \
"M=D\n" + \
self._popD() + \
"@R15\n" + \
"D=D&M\n" + \
self._pushD()
elif command == "or":
translated_str = self._popD() + \
"@R15\n" + \
"M=D\n" + \
self._popD() + \
"@R15\n" + \
"D=D|M\n" + \
self._pushD()
elif command == "not":
translated_str = self._popD() + \
"D=!D\n" + \
self._pushD()
self.stream.write(translated_str)
_segment_table = {
"local": "LCL",
"argument": "ARG",
"this": "THIS",
"that": "THAT",
"pointer": "3",
"temp": "5"
}
def _pushD(self) -> str:
return "@SP\n" + \
"A=M\n" + \
"M=D\n" + \
"@SP\n" + \
"M=M+1\n"
def _popD(self) -> str:
return "@SP\n" + \
"M=M-1\n" + \
"@SP\n" + \
"A=M\n" + \
"D=M\n"
def write_push_pop(self, command: str, segment: str, index: int):
translated_str = None
if command == "push":
translated_str = self._push(segment, index)
elif command == "pop":
translated_str = self._pop(segment, index)
else:
exit(f"command is {command} in write_push_pop")
self.stream.write(translated_str)
def _push(self, segment: str, index: int):
result_str = None
if segment == "constant":
result_str = f"@{index}\n" + \
"D=A\n" + \
self._pushD()
elif segment in ("local", "argument", "this", "that"):
result_str = f"@{index}\n" + \
"D=A\n" + \
f"@{self._segment_table[segment]}\n" + \
"A=M+D\n" + \
"D=M\n" + \
self._pushD()
elif segment in ("pointer", "temp"):
result_str = f"@{index}\n" + \
"D=A\n" + \
f"@{self._segment_table[segment]}\n" + \
"A=A+D\n" + \
"D=M\n" + \
self._pushD()
elif segment == "static":
no_ext = self.file_name.split(".")[0]
result_str = f"@{no_ext}.{index}\n" + \
"D=M\n" + \
self._pushD()
return result_str
def _pop(self, segment: str, index: int):
result_str = None
if segment == "constant":
result_str = "@SP\n" + \
"M=M-1\n" + \
"@SP\n" + \
"A=M\n" + \
"D=M\n" + \
f"@{index}\n" + \
"M=D\n"
elif segment in ("local", "argument", "this", "that"):
result_str = f"@{index}\n" + \
"D=A\n" + \
f"@{self._segment_table[segment]}\n" + \
"D=M+D\n" + \
"@R15\n" + \
"M=D\n" + \
"@SP\n" + \
"M=M-1\n" + \
"@SP\n" + \
"A=M\n" + \
"D=M\n" + \
"@R15\n" + \
"A=M\n" + \
"M=D\n"
elif segment in ("pointer", "temp"):
result_str = f"@{index}\n" + \
"D=A\n" + \
f"@{self._segment_table[segment]}\n" + \
"D=A+D\n" + \
"@R15\n" + \
"M=D\n" + \
"@SP\n" + \
"M=M-1\n" + \
"@SP\n" + \
"A=M\n" + \
"D=M\n" + \
"@R15\n" + \
"A=M\n" + \
"M=D\n"
elif segment == "static":
no_ext = self.file_name.split(".")[0]
result_str = "@SP\n" + \
"M=M-1\n" + \
"@SP\n" + \
"A=M\n" + \
"D=M\n" + \
f"@{no_ext}.{index}\n" + \
"M=D\n"
return result_str
def close(self):
self.stream.close()
self.stream = None
self.file_name = None
Constants
# command type
C_ARITHMETIC = 0
C_PUSH = 1
C_POP = 2
C_LABEL = 3
C_GOTO = 4
C_IF = 5
C_FUNCTION = 6
C_RETURN = 7
C_CALL = 8
# operation type
NULLARY = 0
UNARY = 1
BINARY = 2
main
from argparse import ArgumentParser
from code_writer import CodeWriter
from parser import Parser
from constant import *
from os import path
def parse_args() -> str:
arg_parser = ArgumentParser(
description="python3 assembler.py <file_name>"
)
arg_parser.add_argument(
"file_name",
)
return arg_parser.parse_args().file_name
def main():
file_name = parse_args()
file_name_noext, _ = path.splitext(file_name)
raw_data = None
with open(file_name, "r") as stream:
raw_data = stream.readlines()
parser = Parser(raw_data)
code_writer = CodeWriter()
code_writer.set_file_name(file_name_noext.split("/")[-1] + ".asm")
while parser.has_more_commands():
parser.advance()
if parser.command_type == C_ARITHMETIC:
code_writer.writer_arithmetic(parser.operator)
elif parser.command_type == C_PUSH:
code_writer.write_push_pop(parser.operator, parser.arg1(), parser.arg2())
elif parser.command_type == C_POP:
code_writer.write_push_pop(parser.operator, parser.arg1(), parser.arg2())
code_writer.close()
if __name__ == "__main__":
main()