C 언어로 Lox 인터프리터 만들기 3

이전까지는 추후 작성될 Lox 코드를 실행 가능한 형태로 저장하는 명령어 자료형, Chunk를 만드는 과정이었습니다. 이제 Chunk를 실행 할 수 있는 VM(가상 머신)을 만들 차례입니다.

VM의 구성

VM은 명령어, 즉 Chunk를 실행하기 위한 장치입니다. 정확히는 Chunk::code를 실행합니다. 따라서 현재 실행할 Chunk와 그 안에서 실행하고 있는 바이트 코드의 위치를 알고 있어야 하며, 계산과 임시 값을 추적할 수 있어야 합니다. 이는 아래와 같은 구조를 가짐으로써 가능합니다.

typedef struct
{
    Chunk* chunk;
    uint8_t* ip;
    Value stack[STACK_MAX];
    Value* stackTop;
} VM;

ip는 Chunk::code 배열 중 어느 인덱스를 참조하고 있는지 나타내는 '명령어 포인터'입니다. 성능을 위해 인덱스가 아닌 실제 메모리 주소를 참고하고 있습니다.

stack은 VM이 계산의 결과와 값을 관리할 수 있도록 하는 자료형입니다. 값의 반환은 후입선출의 형태를 따르기 때문에 쉬운 구현을 위해 스택을 사용하였습니다.

인터프리터 실행 흐름

지금까지 작성한 코드를 기반으로 Lox 인터프리터의 실행 흐름을 분석하면,

1. 소스 코드(Lox) 작성
2. 어휘 분석(토큰 분리)
3. 구문 분석(문장 구조 생성)
4. 바이트 코드(Chunk) 생성
5. 인터프리터(VM) 실행

위의 순서를 가지고 있습니다. 하지만 1 ~ 3은 구현하지 않은 상태이며 인위적으로 main.c에서 주입하고 있습니다.

현재는 5(인터프리터 실행)를 구현하기 위해 VM의 최소 기능중 하나인 값을 관리하고 순서에 따라 명령을 시행하는 기능을 구현하고 있습니다.

이 페이지에서 최종적으로 실행하려는 가상의 소스 코드는 다음과 같습니다.

return -((1.2 + 3.4) / 5.6) 

위 가상의 소스 코드를 C 언어를 활용해 Chunk 로 만들어 넣는 과정은 아래와 같습니다.

int main(int argc, const char* argv[])
{
    initVM();
    Chunk chunk;
    initChunk(&chunk);

    int constant = addConstant(&chunk, 1.2); // 1.2
    writeChunk(&chunk, OP_CONSTANT, 123);
    writeChunk(&chunk, constant, 123);

    constant = addConstant(&chunk, 3.4);    // 3.4
    writeChunk(&chunk, OP_CONSTANT, 123);
    writeChunk(&chunk, constant, 123);

    writeChunk(&chunk, OP_ADD, 123); // +

    constant = addConstant(&chunk, 5.6); // 5.6
    writeChunk(&chunk, OP_CONSTANT, 123);
    writeChunk(&chunk, constant, 123);

    writeChunk(&chunk, OP_DIVIDE, 123); // /

    writeChunk(&chunk, OP_NEGATE, 123); // -

    writeChunk(&chunk, OP_RETURN, 123); // return

    disassembleChunk(&chunk, "Test Chunk");

    interpret(&chunk);
    freeChunk(&chunk);
    freeVM();

    return 0;
}

실행 예

바이트 코드를 실행하기 위한 함수, run()은 interpret() 안에서 실행됩니다. interpret()은 Chunk와 VM을 연결하는 역할을 하며 VM 객체는 전역으로 선언되어 있습니다.

run()은 VM에 연결된 Chunk를 실행하며 VM 객체 안의 stack을 활용합니다. main.c에 사용한 writeChunk 순서에 의존하여 아래 이미지와 같은 스택을 구성합니다.

stack에 1.2, 3.4를 넣고, OP_ADD 연산자를 만나면 pop()을 두 번 한 후, 값을 연산하고 그 값을 다시 push()하는 방식으로 stackTop을 움직이며 값을 관리합니다. 다른 이항 연산자도 이와 같은 형식을 가집니다. 자세한 사항은 하단 Github의 vm.c로 확인할 수 있습니다.

OP_NEGATE는 단항 연산자기 때문에 아래와 같은 연산 방식을 사용합니다.

case OP_NEGATE:
{
	push(-pop());
    break;
}

OP_NEGATE 연산자의 피연산자 값을 pop() 하고 단항 연산자를 적용한 후 다시 값을 push() 하여 스택에 값을 유지할 수 있습니다.

다양한 연산자들을 사용하여 처음 목표했던 식의 결과 값을 리턴하는 과정을 나타내면 아래 이미지와 같습니다.

• 0000 ~ 0009은 offset으로 바이트 코드 배열의 인덱스에 해당합니다.
• 123은 소스 코드의 줄 번호에 해당합니다.
  • |은 위 소스 코드와 같은 줄 번호임을 의미합니다.
• OP_CODE는 명령어에 해당합니다.
• [ NUM ]은 스택에 저장된 값입니다.
• 0, 1, 2는 offset으로 상수 풀의 인덱스에 해당합니다.
• '1.2', '3.4', '5.6'은 상수 값으로 상수 풀의 해당 인덱스에 저장된 값을 의미합니다.

마치며

VM이 어떻게 동작하는지를 살펴보며 내부적으로 스택을 활용하는 과정을 구현해보았습니다. 인터프리터는 현재 연산 값을 보관하고 다음 연산에 활용하기 위해 스택을 필요로 합니다. 그리고 이는 연산 뿐이 아니라 일반적인 프로그래밍에서도 마찬가지로 활용됩니다. 다음에는 소스코드로부터 토큰을 만드는 스캐너(어휘 분석기)를 만들어 보도록 하겠습니다.

참고자료: Crafting Interpreters - A Virtual Machine
Github: Will-Big/clox