컴파일러, 인터프리터, 가상머신

학부생 때 The Elements of Computing Systems 라는 책을 보고 컴파일러를 만든 적이 있었다.

 

 

 

(http://www.nand2tetris.org/)

 

​이 책을 보고 컴파일러를 만들게 되면, Jack이라는 간단한 객체지향 언어를 중간언어(위 사이트에서 제공 되는 Stack기반의 VirtualMachine에서 쓰이는 언어)로 변환 하고, 이 중간 언어를 어셈블리어(위 사이트에서 제공 되는 CPU Emulator에서 수행 되는 CPU Instruction)로 변환 하고 최종적으로 이를 바이트 코드(위 사이트에서 제공 되는 CPU Emulator에서 수행 되는 CPU Instruction의 바이트 형태)로 변환하는 컴파일러( + VM Translator + 어셈블러)를 만들게 된다.

하지만 만드는 순서는 이의 역순인 어셈블러 -> VM Translator ->​Tokenizer -> Compiler 순으로 만들게 되는데 어셈블러의 경우 명령어와 바이트 코드가 1 대 1 대응 되므로 가장 쉽고, Jack언어를 VM 언어로 만드는 부분이 토큰화 해서 문맥을 파악 해야 하므로 가장 어렵기 때문이다.

컴파일러를 만드는 중간 중간에 http://www.nand2tetris.org/ 에서 제공 되는 CPU Emulator와 VM Emulator를 이용해 변환이 잘 되었는지 테스트를 해 볼 수 있는데 이를 이용하다 보니 VM Emulator와 CPU Emulator도 직접 만들어 볼 수 있을 것 같다는 생각이 들었다.

그때는 생각만 하고 시간에 쫓겨 실행은 하지 못했었는데 최근에 스크립트어의 작동 방식에 관심이 생기면서 Jack 언어를 스크립트 언어처럼 실행 할 수 있는 인터프리터(혹은 가상 머신) 환경을 만드는게 기존에 만들었던 컴파일러를 활용 하면 되므로 가장 빠를 것 같다는 생각이 들어 만들어 보았다.

 

Jack 언어 자체를 바로 실행 하려면 매우 복잡 하지만 Jack을 컴파일러를 이용하여 가상머신의 명령어 집합으로 변환 시키게 되면(Push, Pop, Add, Sub...etc...) 각 명령어에 해당하는 함수와 스택 기반의 가상 머신만 미리 만들어 놓으면 코드를 한줄 한줄 실행 시켜 해당 명령을 수행하면 된다.

간단하게 예를 들어보면 

 

bool Excute()
{
    while (m_programCounter < m_codes.size())
    {
        const VM_Command &command = m_codes.get(m_programCounter);
        
        VM_FunctionBase *func = VM_FunctionHelper::CreateFunctions(command);
        m_programCounter = func->Do();
    }
    return true;
}

이런 식으로 수행 되고 이를 쭉 풀어 써보면

 

bool Excute()
{
    while (m_programCounter < m_codes.size())
    {
        const VM_Command &command = m_codes.get(m_programCounter);
        switch(command.GetCommand())
        {
        case Jack_Definitions.PUSH_COMMAND_IDENTIFIER:
            PushFunc(command);              
            break;
            
        case Jack_Definitions.POP_COMMAND_IDENTIFIER:
            PopFunc(command);
            break;
            
        case Jack_Definitions.ADD_COMMAND_IDENTIFIER:
            AddFunc();
            break;
            
        case Jack_Definitions.SUB_COMMAND_IDENTIFIER:
            SubFunc();
            break;
            
        case Jack_Definitions.NEG_COMMAND_IDENTIFIER:
            NegFunc();
            break;
            
        case Jack_Definitions.EQ_COMMAND_IDENTIFIER:
            EqFunc();
            break;
            
        case Jack_Definitions.GT_COMMAND_IDENTIFIER:
            GtFunc();
            break;
            
        case Jack_Definitions.LT_COMMAND_IDENTIFIER:
            LtFunc();
            break;
            
        case Jack_Definitions.AND_COMMAND_IDENTIFIER:
            AndFunc();
            break;
            
        case Jack_Definitions.OR_COMMAND_IDENTIFIER:
            OrFunc();
            break;
            
        case Jack_Definitions.NOT_COMMAND_IDENTIFIER:
            NotFunc();
            break;
            
        case Jack_Definitions.GOTO_COMMAND_IDENTIFIER:
            GotoFunc(command.GetArgument1());
            break;
            
        case Jack_Definitions.IF_GOTO_COMMAND_IDENTIFIER:
            IfGotoFunc(command.GetArgument1());
            break;
            
        case Jack_Definitions.CALL_COMMAND_IDENTIFIER:
            CallFunc(command);
            break;
            
        case Jack_Definitions.RETURN_COMMAND_IDENTIFIER:
            m_programCounter = ReturnFunc();
            break;
        
        case Jack_Definitions.FUNCTION_COMMAND_IDENTIFIER:
            FunctionFunc(command.GetIntegerArgument2());
            break;
            
        default:
            return false;
        }
        
        ++m_programCounter;
    }
    
    return true;
}

이런식으로 표현 될 수 있다.

 

 

또 Jack 코드가 어떻게 중간 표현으로 변환 되는지 예를 들어보자면

----------------------------------

class Main
{
 field int f;
 static int st;
 function void main()
 {
  var int i, j, s;
  var Main m, m2;
  let st = 500;
  let s = 20;
  let i = 3;
  let j = Main.sum(10, 20);
  let i = i + j;
  let i = i + s;
  do Output.printInt(i);  // 53
  do Output.println();

  let m = Main.new();
  let i = m.msum(i);
  do Output.printInt(i);  // 653
  do Output.println();

  do Output.printInt(st);  // 500
  do Output.println();

  let m2 = Main.new();
  let i = m2.msum(1);
  do Output.printInt(i);  // 601
  do Output.println();

  do m.dispose();

  return;
 }

 function int sum(int i, int j)
 {
  var int result;
  let result = i + j;
  return result;
 }

 constructor Main new()
 {
  let f = 100;
  return this;
 }

 method void dispose()
 {
  do Memory.deAlloc(this);
  return;
 }

 method int msum(int i)
 {
  var int result;
  let result = i + f + st;
  return result;
 }
}

----------------------------------

 

이런 고급 언어가

 

----------------------------------

function Main.main 5
push constant 500
pop static 0
push constant 20
pop local 2
push constant 3
pop local 0
push constant 10
push constant 20
call Main.sum 2
pop local 1
push local 0
push local 1
add
pop local 0
push local 0
push local 2
add
pop local 0
push local 0
call Output.printInt 1
pop temp 0
call Output.println 0
pop temp 0
call Main.new 0
pop local 3
push local 3
push local 0
call Main.msum 2
pop local 0
push local 0
call Output.printInt 1
pop temp 0
call Output.println 0
pop temp 0
push static 0
call Output.printInt 1
pop temp 0
call Output.println 0
pop temp 0
call Main.new 0
pop local 4
push local 4
push constant 1
call Main.msum 2
pop local 0
push local 0
call Output.printInt 1
pop temp 0
call Output.println 0
pop temp 0
push local 3
call Main.dispose 1
pop temp 0
push constant 0
return
function Main.sum 1
push argument 0
push argument 1
add
pop local 0
push local 0
return
function Main.new 0
push constant 1
call Memory.alloc 1
pop pointer 0
push constant 100
pop this 0
push pointer 0
return
function Main.dispose 0
push argument 0
pop pointer 0
push pointer 0
call Memory.deAlloc 1
pop temp 0
push constant 0
return
function Main.msum 1
push argument 0
pop pointer 0
push argument 1
push this 0
add
push static 0
add
pop local 0
push local 0
return

----------------------------------

 

이런 형태의 중간 언어로 변환 되고 인터프리터(혹은 가상 머신)에서

변환된 중간 표현을 한줄 한줄 실행하면 되는것이다.(Push constant 3 이면 3을 스택에 push 하는 등...)

(쉽게쉽게 하기 위해 중간 표현이 string 형태로 사람이 읽기 쉽게 되어 있지만 조금 더 빠르게 하기 위해 바이트 코드로 변환 시켜도 될듯하다.. -> push constant 3 이면 0001 0000 0011 0000 = 0x1030 등으로 실제 바이트 형태로 표현 한다던지....)

 

 

 

 

위의 사이트에서 제공 되는 실제 VM Emulator는 실제 메모리 처럼 연속된 하나의 공간을 스택 영역, 힙 영역, 스태틱 영역, 코드 영역으로 쪼개어 사용 하지만 내가 만드는 인터프리터(혹은 가상머신)에서도 굳이 이를 흉내 낼 필요는 없기 때문에 각각의 영역을 독립된 세그먼트로 분리하였다.

만들다보니 컴파일러 자체를 오래전에 만들어서 위에서 쓰인 this, that, pointer 등의 개념이 생각 안나 약간 애를 먹기는 했지만 책을 다시 들춰보아 가며 해결해 냈다.

 

 c언어의 printf() 등에 해당하는 함수가 Jack 언어에서는 Output.printInt()인데 이러한 built in 함수의 경우 do Output.printInt(3); 을 하게 되면 printf("%d", 3);을 호출 하는 등 추가로 구현을 해주어야 하는 부분이 있는데 이를 구현 하다 보니 heap에서 동적 할당하는 Memory.alloc() 함수, 키보드 입력 등등을 추가로 구현 해야 했고 이를 다해보니 결국 내가 OS를 만든건지 인터프리터를 만든건지 가상머신을 만든건지 헷갈리기 시작했다......

예전에 OS가 먼저일까 컴파일러가 먼저일까 같은 닭이 먼저냐 달걀이 먼저냐 식의 생각을 한 적이 있었는데 만들어보니 결국 돌고 도는 것이라는게 확 와 닿았다.

이렇게 만든 인터프리터에 그림을 그릴수 있는 스크린을 넣고 작업 표시줄을 그리고 각 어플리케이션의 윈도우를 그리고 하게 되면 결국엔 이 가상머신에서 돌아가는 OS를 만든게 되고 이 OS에서 돌아가는 컴파일러를 만들고 이를 이용해 또 인터프리터를 만들고......... 무한히 반복 될수도 있겠다..... 성능은 장담 못하지만.....