이번 장은 일반적인 객체 지향 고수준 언어용 컴파일러를 만드는 첫 단계에 해당한다. 우리는 이 작업을 두 단계로 나누어 10~11장에서는 고수준 프로그램이 중간 코드로 번역되는 과정, 그 후에 7~8장에서 중간 코드가 기계어로 번역되는 과정을 살펴볼 예정이다.
기본 개념은 이렇다. 코드를 실제 플랫폼에서 실행하는 대신, 가상 머신(Virtual Machine, VM)에서 실행 가능한 중간 코드를 만든다. VM은 실재하지는 않지만, 다른 컴퓨터 플랫폼 상에서 구현 가능한 추상적인 컴퓨터다.
이 아이디어는 코드 이동성, 즉 동일한 코드를 수정 없이, 또는 약간의 변경만으로 여러 컴퓨터 환경에서 실행시키도록 하기 때문에 매우 유용하게 사용할 수 있다.
VM은 다른 플랫폼에서 상대적으로 구현하기 쉽기 때문에, VM 기반 소프트웨어는 소스 코드를 수정할 필요 없이 여러 프로세서와 운영체제에서 실행 가능하다.
7.1 배경
7.1.1 가상 머신 패러다임
고수준 언어가 실행되려면 먼저 기계어로 번역되어야 한다. 이 과정을 보통 컴파일이라 부르며, 해당 아키텍처에 따라서 수많은 컴파일러가 생겨난다. 이러한 컴파일러의 기계 종속성 문제를 해결하기 위해서 전체 컴파일 과정을 두 단계로 쪼갰다.
- 고수준 언어의 구문을 분석해서 명령들을 중간 처리 단계(VM 언어)로 번역한다. (front-end)
- 중간 처리된 명령어들을 다시 대상 하드웨어의 기계어로 번역한다. (back-end)
또한 가상 머신 언어 개념은 실용적 장점이 몇 가지 있다.
- 가상 머신 구현 부분(백엔드)만 바꾸면, 여러 플랫폼의 컴파일러들을 상대적으로 쉽게 만들 수 있다.
- 여러 가지 언어의 컴파일러들이 같은 VM 백 엔드를 공유함으로써, 코드를 공유하고 상호 운용하기 편해진다. 예를 들어, 같은 VM 컴파일 단계를 공유한다면, 한 언어에서 다른 언어의 루틴을 호출해서 활용하는 문법을 만들기가 훨씬 더 수월해진다.
- 모듈성을 가지고 있기 때문에, VM 구현이 더 효율적으로 개선될 때마다. 텀파일러들도 곧바고 그 이점을 누린다.
다음은 Jack 프로그램에 대한 컴파일 과정이다.
7.1.2 스택 머신 모델
스택 모신 모델에서 산술 명령은 스택의 최상단에서 피연산자를 꺼내고(pop), 그 결과를 다시 스택의 최상단에 넣는다(push). 그 외의 다른 명령들의 경우에는 스택의 최상단과 지정된 메모리 주소 사이에 데이터가 이동된다.
- 기본 스택 연산
스택은 push와 pop을 기본 연산으로 삼는 추상 데이터 구조다. push는 한개의 데이터 원소를 스택의 최상단에 추가하는 연산이다. 이때 최상단에 있던 원소는 새로 추가된 원소의 아래로 내려간다. pop은 최상단 원소를 꺼낸 후 스택에서 삭제하는 연산이다. 이때 바로 아래 있던 원소는 최상단으로 올라오게 된다. 그래서 스택을 '후입선출'저장 방식이라 한다.
스택 데이터 구조를 구현할 수 있는 여러 방법 중 하나는 스택 배열과, 최상단 원소 바로 위 위치를 가리키는 스택 포인터 변수로 구현하는 것이다. push x 명령은 x를 sp가 가리키는 배열 위치에 저장하고 sp를 1증가시키는 방식으로 구현된다. (stack[sp]=x; sp=sp+1) 그리고 pop연산은 먼저 sp를 1 감소시키고 최상단 위치의 값을 반환하는 식이 된다. (sp=sp-1; return stack[sp]) - 스택 산술
산술의 피연산자를 스택에서 꺼내서(POP), 필요한 연산을 수행한 후에 결과를 다시 스택에 넣으면(PUSH) 된다. 다음은 스택 산술 예시다.
7.2 VM 명세, 1부
7.2.1 일반
이 가상 머신은 스택 기반이다. 즉, 모든 연산이 스택 위에서 이루어진다. 또한 함수 기반이다. 그리고 이 언어는 다음과 같은 네 가지 종류의 명령으로 구성된다.
- 산술 명령(arithmetic command)은 스택에서 산술 및 논리 연산을 수행한다.
- 메모리 접근 명령(memory access command)은 스택과 가상 메모리 세그먼트 사이에 데이터를 주고받는 명령이다.
- 프로그램 흐름 명령(program flow command)은 조건 및 무조건 분기 연산을 가능하게 한다.
- 함수 호출 명령(function calling command)은 함수를 호출하고 결과를 반환한다.
이번 장에서는 산술, 메모리 접근 명령을 구현하고, 다음 장에서는 프로그램 흐름 제어, 함수 호출 명령을 구현할 것이다.
- 프로그램 명령 구조
.vm 파일 내부에서 한 라인은 한 VM 명령이 되며, 다음과 같은 형식을 띈다. command(ex: add), command arg(ex: goto loop), 또는 command arg1 arg2(ex: push loacl 3). command 부분과 각 인수들은 임의 개수의 봉백문자로 구분된다.
7.2.2 산술 및 논리 명령
이 VM 언어는 9개의 스택 기반 산술 및 논리 명령들이 있다. 이 중 7개는 2항 명령이다. 즉, 스택에서 두 개의 항복을 꺼내서(POP), 2항 함수를 계산하고, 결과를 다시 넣는(PUSH) 명령이다. 나머지 두 함수는 하나의 항목을 꺼내서, 단항 함수를 계산하고, 결과를 다시 넣는 단항 명령이다. 여기에서 우리는 명령들이 단지 해당 피연산자를 결괏값으로 교체함을 알 수 있다. 
여기에서의 boolean 값은 true와 false를 각각 -1(0xFFFF)과 0(0x0000)으로 표시한다.
7.2.3 메모리 접근 명령
지금까지는 단순히 스택에 데이터를 PUSH, POP 만을 했다면, 지금부터는 가상 메모리 세그먼트들을 조작해볼 것이다. 각각의 세그먼트에 대한 설명은 다음과 같다.
| 세그먼트 | 목적 | 설명 |
|---|---|---|
argument | 함수의 인수를 저장 | 함수가 입력되면 VM이 동적으로 할당함 |
local | 함수의 지역 변수를 저장 | 함수가 입력되면 VM이 동적으로 할당하고 0으로 초기화함 |
static | 같은 .vm 파일 내 모든 함수가 공유하는 정적 변수를 저장 | 각 .vm 파일에 대해 VM이 할당함. .vm 파일 내 모든 함수가 공유함 |
constant | 0...32767 범위 내 모든 상수를 가지는 의사 세그먼트 | VM이 에뮬레이션함. 프로그램 내 모든 함수에서 접근 가능 |
this, that | 다목적 세그먼트. 힙(heap) 내 서로 다른 영역에대응하도록 설정 가능. 프로그래밍 내의 다양한 필요에 따라 이용됨 | 모든 VM 함수는 힙 상에서 선택된 영역을 조작하는 용도로 이 세그먼트를 사용 가능함 |
pointer | this와 that 세그먼트의 기준 주소값을 가지고 있는 두 개의 입력 세그먼트 | 모든 VM 함수는 pointer 0(또는 1)을 특정 주소로 설정 가능함. 이로 인해 this(또는 that)세그먼트가 그 주소에서 시작하는 힙 영역으로 정렬됨 |
temp | 일반적 용도의 임시 변수를 가지는 고정 8-엔트리 세그먼트 | VM 함수 내에서 어떤 목적으로든 사용될 수 있음. 프로그램 내 모든 함수가 공유함 |
- 메모리 접근 명령
-> 모든 메모리 세그먼트는 두 개의 동일한 명령으로 접근 가능하다.
여기서 segment는 8개 세그먼트 이름 중 하나이면, index는 음수가 아닌 정수다. 예를 들어 push argument 2 다음의 pop local 1 명령은, 함수의 세 번째 인수 값을 함수의 두 번째 지역 변수에 저장하라는 뜻이다.- push segment index -> segment[index] 값을 스택에 넣는다(PUSH).
- pop segment index -> 최상단 스택 값을 꺼내서(POP) segment[index]에 저장한다.
- 스택
VM 연산에서 데이터 값은 한 세그먼트에서 다른 세그먼트로 점프하는 대신에 스택을 거쳐서 이동한다. - 힙
힙은 객체와 배열 데이터를 저장하는데 사용되는 RAM 영역의 명칭이다.
7.2.4 프로그램 흐름과 함수 호출 명령
지금까지 설명한 명령들 말고도 다음 장에서 설명할 명령들이 존재한다.
- 프로그램 흐름 명령
label symbol // 레이블 선언
goto symbol // 무조건 분기
if-goto symbol // 조건 분기- 함수 호출 명령
function fincionName nLocals // 함수 선언. 함수의 지역 변수 개수를 지정함.
call functionName nArgs // 함수 호출. 함수의 인자 개수를 지정함
return // 호출하는 함수로 제어를 되돌림7.3 구현
우리는 지금부터 .vm 파일을 입력 받아, 핵 어셈블리 언어로 된 .asm 파일 하나를 출력으로 생성하는 프로그램을 구현할 것이다.
- RAM 사용
다음은 RAM의 주소별 활용 방법이다.
| RAM 주소 | 사용법 |
|---|---|
| 0-15 | 16개의 가상 레지스터. 사용법은 아래에 설명됨 |
| 16-255 | 정적 변수(프로그램 내 모든 VM 함수에서 사용) |
| 256-2047 | 스택 |
| 2048-16383 | 힙(객체와 배열 저장에 활용됨) |
| 16384-24575 | 메모리 매핑 I/O |
| 24575-32767 | 사용하지 않는 메모리 공간 |
| 레지스터 | 이름 | 사용법 |
|---|---|---|
| RAM[0] | SP | 스택 포인터: 스택에서 다음 최상위 위치를 가리킨다. |
| RAM[1] | LCL | 현재 VM 함수의 local 세그먼트의 기저 주소를 가리킨다. |
| RAM[2] | ARG | 현재 VM 함수의 argument 세그먼트의 기저 주소를 가리킨다. |
| RAM[3] | THIS | 현재 this 세그먼트의 시작 주소(힙 내부)를 가리킨다. |
| RAM[4] | THAT | 현재 that 세그먼트의 시작 주소(힙 내부)를 가리킨다. |
| RAM[5-12] | temp 세그먼트의 내용을 저장한다. | |
| RAM[13-15] | VM 구현에서 다용도 레지스터로 사용될 수 있다. |
여기에서 각각의 세그먼트 활용법에 대해 헷갈릴 것이다. 이에 대해서는 nand2tetris가 기본으로 제공하는 tool에 있는 VMEmulater.sh 를 활용하면 쉽게 이해할 수 있을 것이다.
프로그램 구조
Parser 모듈
| 루틴 | 인수 | 반환 | 기능 |
|---|---|---|---|
| 생성자 | 입력 파일 | - | 입력 파일을 열고 분석할 준비를 한다. |
| hasMoreCommands | - | Bool | 입력에 명령이 더 있는가? |
| advance | - | - | 입력에서 다음 명령을 읽고 현재 명령으로 만든다. |
| commandType | - | C_ARITHMETIC. C_PUSH, C_POP, C_LABEL, C_GOTO, C_IF, C_FUNCTION, C_RETURN, C_CALL | 현재 VM 명령의 타입을 반환한다. |
| arg1 | - | 문자열 | 현재 명령의 첫 인수를 반환한다. C_ARRITHMETIC의 경우에는 명령 그 자체가 반환된다. C_RETURN의 경우 호출되지 않는다. |
| arg2 | - | 정수 | 현재 명령의 두 번째 인수를 반환한다. C_PUSH, C_POP, C_FUNCTION, C_CALL일 때만 호출된다. |
class Parser:
def __init__(self, file_name):
self._file_name = file_name
self._read_f = open(self._file_name, 'r')
self._cur_index = 0
self._vm_instruction = self._read_f.readlines()
for i in range(0, len(self._vm_instruction)):
self._vm_instruction[i] = self._vm_instruction[i].replace("\n", "")
if not self._vm_instruction[i].find('//'):
self._vm_instruction[i] = self._vm_instruction[i].replace(self._vm_instruction[i][self._vm_instruction[i].find('/'):], '')
for i in range(0, self._vm_instruction.count('')):
self._vm_instruction.remove('')
print(self._vm_instruction)
def hasMoreCommands(self):
if self._cur_index == len(self._vm_instruction):
return False
return True
def advance(self):
self._cur_index+=1
def commandType(self):
instruction = self._vm_instruction[self._cur_index].split()[0]
arithmetic = ['add', 'sub', 'neg', 'eq', 'gt', 'lt', 'and', 'or', 'not']
if instruction in arithmetic:
return 'C_ARITHMETIC'
elif instruction == 'push':
return 'C_PUSH'
elif instruction == 'pop':
return 'C_POP'
elif instruction == 'label':
return 'C_LABEL'
elif instruction == 'goto':
return 'C_GOTO'
elif instruction == 'if-goto':
return 'C_IF'
elif instruction == 'function':
return 'C_FUNCTION'
elif instruction == 'call':
return 'C_CALL'
elif instruction == 'return':
return 'C_RETURN'
def arg1(self):
if self.commandType() == 'C_ARITHMETIC':
return self._vm_instruction[self._cur_index].split()[0]
elif self.commandType() in ['C_PUSH', 'C_POP', 'C_LABEL', 'C_GOTO', 'C_IF', 'C_FUNCTION', 'C_CALL']:
return self._vm_instruction[self._cur_index].split()[1]
else:
return None
def arg2(self):
if self.commandType() in ['C_PUSH', 'C_POP', 'C_FUNCTION', 'C_CALL']:
return self._vm_instruction[self._cur_index].split()[2]
else:
return None
def printInstruction(self):
print(self._vm_instruction)
CodeWriter 모듈
| 루틴 | 인수 | 반환 | 기능 |
|---|---|---|---|
| 생성자 | 출력 파일 | - | 출력 파일을 열고 기록할 준비를 한다. |
| writerArithmetic | command(string) | - | 주어진 산술 명령을 번역한 어셈블리 코드를 기록한다. |
| writePushPop | command, segment(string), index(int) | - | 주어진 command를 번역한 어셈블리 코드를 기록한다. 여기서 command는 push나 pop이다. |
class CodeWriter:
def __init__(self, file_name):
self._file_name = file_name[:file_name.find('.')]
self._write_file = open(self._file_name + '.asm', 'w')
self._file_name = self._file_name.split('/').pop()
self._true_counter = 1
self._end_counter = 1
def writeArithmetic(self, command):
if command=='add':
self._write_file.write('@SP\n')
self._write_file.write('AM=M-1\n')
self._write_file.write('D=M\n')
self._write_file.write('@SP\n')
self._write_file.write('AM=M-1\n')
self._write_file.write('M=M+D\n')
self._write_file.write('@SP\n')
self._write_file.write('M=M+1\n')
elif command=='sub':
self._write_file.write('@SP\n')
self._write_file.write('AM=M-1\n')
self._write_file.write('D=M\n')
self._write_file.write('@SP\n')
self._write_file.write('AM=M-1\n')
self._write_file.write('M=M-D\n')
self._write_file.write('@SP\n')
self._write_file.write('M=M+1\n')
elif command=='neg':
self._write_file.write('@SP\n')
self._write_file.write('A=M-1\n')
self._write_file.write('M=-M\n')
elif command=='eq':
self._write_file.write('@SP\n')
self._write_file.write('AM=M-1\n')
self._write_file.write('D=M\n')
self._write_file.write('@SP\n')
self._write_file.write('AM=M-1\n')
self._write_file.write('D=M-D\n')
self._write_file.write('@TRUE_%d\n' % self._true_counter)
self._write_file.write('D;JEQ\n')
self._write_file.write('@SP\n')
self._write_file.write('A=M\n')
self._write_file.write('M=0\n')
self._write_file.write('@END_%d\n' % self._end_counter)
self._write_file.write('0;JMP\n')
self._write_file.write('(TRUE_%d)\n' % self._true_counter)
self._true_counter += 1
self._write_file.write('@SP\n')
self._write_file.write('A=M\n')
self._write_file.write('M=-1\n') #TRUE가 -1?
self._write_file.write('(END_%d)\n' % self._end_counter)
self._end_counter += 1
self._write_file.write('@SP\n')
self._write_file.write('M=M+1\n')
elif command=='gt':
self._write_file.write('@SP\n')
self._write_file.write('AM=M-1\n')
self._write_file.write('D=M\n')
self._write_file.write('@SP\n')
self._write_file.write('AM=M-1\n')
self._write_file.write('D=M-D\n')
self._write_file.write('@TRUE_%d\n' % self._true_counter)
self._write_file.write('D;JGT\n')
self._write_file.write('@SP\n')
self._write_file.write('A=M\n')
self._write_file.write('M=0\n')
self._write_file.write('@END_%d\n' % self._end_counter)
self._write_file.write('0;JMP\n')
self._write_file.write('(TRUE_%d)\n' % self._true_counter)
self._true_counter += 1
self._write_file.write('@SP\n')
self._write_file.write('A=M\n')
self._write_file.write('M=-1\n') #TRUE가 -1?
self._write_file.write('(END_%d)\n' % self._end_counter)
self._end_counter += 1
self._write_file.write('@SP\n')
self._write_file.write('M=M+1\n')
elif command=='lt':
self._write_file.write('@SP\n')
self._write_file.write('AM=M-1\n')
self._write_file.write('D=M\n')
self._write_file.write('@SP\n')
self._write_file.write('AM=M-1\n')
self._write_file.write('D=M-D\n')
self._write_file.write('@TRUE_%d\n' % self._true_counter)
self._write_file.write('D;JLT\n')
self._write_file.write('@SP\n')
self._write_file.write('A=M\n')
self._write_file.write('M=0\n')
self._write_file.write('@END_%d\n' % self._end_counter)
self._write_file.write('0;JMP\n')
self._write_file.write('(TRUE_%d)\n' % self._true_counter)
self._true_counter += 1
self._write_file.write('@SP\n')
self._write_file.write('A=M\n')
self._write_file.write('M=-1\n') #TRUE가 -1?
self._write_file.write('(END_%d)\n' % self._end_counter)
self._end_counter += 1
self._write_file.write('@SP\n')
self._write_file.write('M=M+1\n')
elif command=='and':
self._write_file.write('@SP\n')
self._write_file.write('AM=M-1\n')
self._write_file.write('D=M\n')
self._write_file.write('@SP\n')
self._write_file.write('AM=M-1\n')
self._write_file.write('M=M&D\n')
self._write_file.write('@SP\n')
self._write_file.write('M=M+1\n')
elif command=='or':
self._write_file.write('@SP\n')
self._write_file.write('AM=M-1\n')
self._write_file.write('D=M\n')
self._write_file.write('@SP\n')
self._write_file.write('AM=M-1\n')
self._write_file.write('M=M|D\n')
self._write_file.write('@SP\n')
self._write_file.write('M=M+1\n')
elif command=='not':
self._write_file.write('@SP\n')
self._write_file.write('A=M-1\n')
self._write_file.write('M=!M\n')
else:
pass
def writePushPop(self, command, segment, index):
if command=='C_PUSH':
if segment=='constant':
self._write_file.write('@%s\n' % index)
self._write_file.write('D=A\n')
self._write_file.write('@SP\n')
self._write_file.write('A=M\n')
self._write_file.write('M=D\n')
self._write_file.write('@SP\n')
self._write_file.write('M=M+1\n')
elif segment=='argument':
self._write_file.write('@ARG\n')
self._write_file.write('A=M+%s\n' % index)
self._write_file.write('D=M\n')
self._write_file.write('@SP\n')
self._write_file.write('A=M\n')
self._write_file.write('M=D\n')
self._write_file.write('@SP\n')
self._write_file.write('M=M+1\n')
elif segment=='local':
self._write_file.write('@LCL\n')
self._write_file.write('A=M+%s\n' % index)
self._write_file.write('D=M\n')
self._write_file.write('@SP\n')
self._write_file.write('A=M\n')
self._write_file.write('M=D\n')
self._write_file.write('@SP\n')
self._write_file.write('M=M+1\n')
elif segment=='static':
self._write_file.write('@{}.{}\n'.format(self._file_name, index))
self._write_file.write('D=M\n')
self._write_file.write('@SP\n')
self._write_file.write('A=M\n')
self._write_file.write('M=D\n')
self._write_file.write('@SP\n')
self._write_file.write('M=M+1\n')
elif segment=='pointer':
if index==0:
self._write_file.write('@THIS\n')
self._write_file.write('D=M\n')
self._write_file.write('@SP\n')
self._write_file.write('A=M\n')
self._write_file.write('M=D\n')
self._write_file.write('@SP\n')
self._write_file.write('M=M+1\n')
elif index==1:
self._write_file.write('@THAT\n')
self._write_file.write('D=M\n')
self._write_file.write('@SP\n')
self._write_file.write('A=M\n')
self._write_file.write('M=D\n')
self._write_file.write('@SP\n')
self._write_file.write('M=M+1\n')
elif segment=='this':
self._write_file.write('@THIS\n')
self._write_file.write('A=A+%s\n' % index)
self._write_file.write('D=M\n')
self._write_file.write('@SP\n')
self._write_file.write('A=M\n')
self._write_file.write('M=D\n')
self._write_file.write('@SP\n')
self._write_file.write('M=M+1\n')
elif segment=='that':
self._write_file.write('@THAT\n')
self._write_file.write('A=A+%s\n' % index)
self._write_file.write('D=M\n')
self._write_file.write('@SP\n')
self._write_file.write('A=M\n')
self._write_file.write('M=D\n')
self._write_file.write('@SP\n')
self._write_file.write('M=M+1\n')
elif segment=='temp':
self._write_file.write('@5\n')
self._write_file.write('A=A+%s\n' % index)
self._write_file.write('@D=M\n')
self._write_file.write('@SP\n')
self._write_file.write('A=M\n')
self._write_file.write('M=D\n')
self._write_file.write('@SP\n')
self._write_file.write('M=M+1\n')
else:
pass
if command=='C_POP':
if segment=='argument':
self._write_file.write('@SP\n')
self._write_file.write('M=M-1\n')
self._write_file.write('A=M\n')
self._write_file.write('D=M\n')
self._write_file.write('@ARG\n')
self._write_file.write('A=M+%s\n' % index)
self._write_file.write('D=M\n')
elif segment=='local':
self._write_file.write('@SP\n')
self._write_file.write('M=M-1\n')
self._write_file.write('A=M\n')
self._write_file.write('D=M\n')
self._write_file.write('@LCL\n')
self._write_file.write('A=M+%s\n' % index)
self._write_file.write('M=D\n')
elif segment=='static':
self._write_file.write('@SP\n')
self._write_file.write('M=M-1\n')
self._write_file.write('A=M\n')
self._write_file.write('D=M\n')
self._write_file.write('@{}.{}\n'.format(self._file_name, index))
self._write_file.write('M=D\n')
elif segment=='pointer':
if index==0:
self._write_file.write('@SP\n')
self._write_file.write('M=M-1\n')
self._write_file.write('A=M\n')
self._write_file.write('D=M\n')
self._write_file.write('@THIS\n')
self._write_file.write('M=D\n')
elif index==1:
self._write_file.write('@SP\n')
self._write_file.write('M=M-1\n')
self._write_file.write('A=M\n')
self._write_file.write('D=M\n')
self._write_file.write('@THAT\n')
self._write_file.write('M=D\n')
elif segment=='this':
self._write_file.write('@SP\n')
self._write_file.write('M=M-1\n')
self._write_file.write('A=M\n')
self._write_file.write('D=M\n')
self._write_file.write('@THIS\n')
self._write_file.write('A=A+%s\n' % index)
self._write_file.write('M=D\n')
elif segment=='that':
self._write_file.write('@SP\n')
self._write_file.write('M=M-1\n')
self._write_file.write('A=M\n')
self._write_file.write('D=M\n')
self._write_file.write('@THAT\n')
self._write_file.write('A=A+%s\n' % index)
self._write_file.write('M=D\n')
elif segment=='temp':
self._write_file.write('@SP\n')
self._write_file.write('M=M-1\n')
self._write_file.write('A=M\n')
self._write_file.write('D=M\n')
self._write_file.write('@5\n')
self._write_file.write('A=A+%s\n' % index)
self._write_file.write('M=D\n')
else:
pass
