이 챕터의 목표는 우리가 쓴 Lox 코드(예: -1 + 2 * (3 / 4))를 컴퓨터가 알아들을 수 있는 저수준 명령어, 즉 바이트코드(bytecode)로 번역하는 '컴파일러'를 만드는 것입니다.
이전 챕터에서 만든 '스캐너(Scanner)'가 코드를 '토큰(Token)'이라는 단어 조각(예: -, 1, +, 2...)으로 자르는 역할이었다면, 이번 챕터의 '컴파일러'는 이 토큰들을 조합해서 실제 '실행 가능한 명령어 묶음(Chunk)'을 만듭니다.
하지만 main.c, compiler.c, vm.c, scanner.c 등 여러 파일에 흩어져 있는 코드들이 정확히 '어떻게' 상호작용해서 결과를 내는지 한눈에 파악하기 어렵습니다.
그래서 오늘은 사용자가 터미널에 -(1 + 2)를 입력하는 순간부터 최종 결과인 -3이 출력되기까지, 코드의 흐름을 한 단계씩 따라가 보려고 합니다.
이전과 달라진 코드가 많이 존재하지만 이를 하나하나 짚기보단 현 단계까지 완성된 코드를 기반으로 어떻게 컴파일러가 코드를 해석하고 결과를 도출하는지 확인해 보겠습니다.
단일 패스 컴파일
일반적인 컴파일러 패스는 파싱을 통한 의미 파악과 이를 바탕으로 동일한 의미를 가지는 저수준 명령어 출력으로 나뉩니다. 하지만 이 챕터의 컴파일러는 코드를 읽는 동시에 바이트코드를 바로 생성하는 '단일 패스(Single Pass)' 방식을 사용합니다.
이미지 출처: Cratring Interpreters
저자의 말을 빌려 설명하자면, 코드를 보는 하나의 구멍이 존재하고 컴파일러는 그 구멍을 통해 즉각적으로 해석하며 바이트코드로 변환하는 것을 의미합니다. 이는 구문을 이해하기 위해 주변 맥락을 많이 필요로하지 않아야 한다는 것입니다.
이 방식은 C언어로 구현하기 더 간단하고 메모리도 적게 쓴다는 장점이 있습니다.
흐름 분석
-(1+2) 를 컴파일하는 과정을 통해 코드 흐름을 알아보겠습니다. 가장 먼저 파서가 첫번째 토큰을 가리키게 합니다. 파서는 현재 토큰(cur), 이전 토큰(pre)을 추적하며 필요에 따라 이전 토큰을 활용합니다.
Source: 소스 코드
Tokens: 소스 코드를 기반으로 생성된 토큰
Parser: 파서가 가리키는 토큰
Byte-c: 파싱을 통해 생성된 바이트 코드
Consts: 상수 배열
Source: "-(1+2)"
Tokens: - ( 1 + 2 ) <EOF>
Parser: ^
|
cur
Byte-c: []
Consts: []표현식의 첫번째 토큰을 스캔합니다. 이는 현재 토큰을 적절한 값으로 초기화 하기 위함입니다.
Source: "-(1+2)"
Tokens: - ( 1 + 2 ) <EOF>
Parser: ^ ^
| |
pre cur
Byte-c: []
Consts: []이후 본격적인 파싱이 시작됩니다. 모든 연산자 토큰은 우선 순위를 가집니다. 예를 들어 = < +,- < *,/ 와 같습니다. 마지막에 결과값을 가져 오기 위해 우선 순위가 가장 낮은 = 을 표현식의 시작 연산자로 정합니다. 현재는 계산만 가능 하기 때문에 생략되어 있지만 소스 코드가 print(-(1+2)); 와 같으며 그 결과를 출력하기 위한 과정이라고 생각하면 됩니다.
이후 다음 토큰을 추가로 스캔하여 현재 토큰과 이전 토큰을 갱신합니다. 토큰 갱신은 아래 함수에서 이루어집니다. 이제 pre 토큰부터 검사합니다.
pre 토큰은 - 입니다. - 는 일반적으로는 이항 연산자로 활용되지만 소스 코드의 상황처럼 전위 연산자로 쓰일 수 있습니다. pre 토큰에서 유효한 토큰이 검출되었으니 처리합니다.
다시 처음에 = 을 표현식의 시작 연산자로 정했던 것처럼 - 이후의 표현식을 부분 표현식처럼 취급해서 - 연산자로 시작합니다. 시작하는 함수를 표현하면 아래와 같습니다. 여기서 pre_token_processing(), cur_token_processing() 이 내부적으로 다시 start_parsing_with() 을 호출하는 재귀 함수의 형태를 가지고 있습니다.
func start_parsing_with('=')
move_parser()
pre_token_processing()
while('=' <= cur_token_precedence)
move_parser()
in_token_processing()
end while
end func
// 함수명은 이해를 돕기 위해 현재 맥락에 직관적인 이름으로 대체하였습니다.
// 실제 함수명은 아래와 같습니다.
// start_parsing_with(): parsePrecedence()
// move_parser(): advance()
// pre_token_processing(): prefix()
// in_token_processing(): infix()
// 자세한 사항은 깃헙을 참조 바랍니다.즉, pre_token_processing('-') 이 내부적으로 start_parsing_with('-') 를 호출한 것입니다. 각 함수는 모두 전역 변수로 파서를 공유하고 있어서 재귀적으로 진행하더라도 표현식을 끝까지 처리할 수 있게 됩니다.
pre_token_processing('-')이 호출되면, 실제 코드에서는 unary() 함수가 실행됩니다. unary의 임무는 간단합니다.
-
자신의 피연산자(
operand)를 파싱한다. (-뒤에 오는 대상) -
피연산자 파싱이 끝나면, "부호를 바꿔라"라는
OP_NEGATE명령어를 붙인다.
피연산자를 파싱하기 위해, unary는 다시 한번 start_parsing_with을 재귀 호출합니다. 이때, 자신(unary)의 우선순위인 PREC_UNARY(='-')를 넘겨줍니다.
Source: "-(1+2)"
Tokens: - ( 1 + 2 ) <EOF>
Parser: ^ ^
| |
pre cur
Call Stack: [ start_parsing_with('=') | start_parsing_with('-') ]
Byte-c: []
Consts: []start_parsing_with('-') 가 시작되고, move_parser() 를 호출하여 다음 토큰을 봅니다. pre -> (, cur -> 1이 됩니다.
이제 pre_token_processing('(')이 실행될 차례입니다. 이는 grouping() 함수에 해당합니다.
grouping 함수의 임무도 간단합니다.
-
괄호 안의 표현식을 처음부터 다시 파싱한다.
-
파싱이 끝나면,
)(닫는 괄호)가 오는지 확인한다.
괄호 안의 1+2는 완전한 새 표현식이므로, grouping은 다시 start_parsing_with('=') 을 재귀 호출합니다.
Source: "-(1+2)"
Tokens: - ( 1 + 2 ) <EOF>
Parser: ^ ^
| |
pre cur
Call Stack: [ start_parsing_with('=') | start_parsing_with('-') | start_parsing_with('=') ]
Byte-c: []
Consts: []이제 3단계의 재귀 호출이 쌓였습니다. 이제 맨 위 start_parsing_with('=')가 move_parser() 를 호출합니다. pre -> 1, cur -> +가 됩니다.
pre_token_processing('1') 가 호출됩니다.
pre_token_processing('1') 함수는 배열 정보를 통해 숫자 토큰에 속하는 전처리 함수로 연결됩니다. 전처리 함수는 number() 함수에 해당합니다. 함수에서는 아래와 같은 작업을 수행합니다.
-
"1"문자열을 숫자1.0으로 변환합니다. -
1.0을 상수 배열(Consts)에 추가합니다. (Consts[0] = 1.0) -
"상수 배열
0번 인덱스의 값을 스택에 밀어 넣어라"라는OP_CONSTANT명령어를Byte-c에 추가합니다.
Source: "-(1+2)"
Tokens: - ( 1 + 2 ) <EOF>
Parser: ^ ^
| |
pre cur
Call Stack: [ start_parsing_with('=') | start_parsing_with('-') | start_parsing_with('=') ]
Byte-c: [OP_CONSTANT, 0]
Consts: [1.0]number()가 리턴되고, start_parsing_with('=')의 while 루프로 돌아옵니다. while('=' <= cur_token_precedence [+] )를 검사합니다. + 연산자의 우선순위(PREC_TERM)는 = (PREC_ASSIGNMENT)보다 높으므로, 루프가 실행됩니다. (연산자 우선 순위는 여기를 참조)
루프 안에서 move_parser() 를 호출합니다. pre -> +, cur -> 2 가 됩니다. cur_token_processing('+') (즉, binary() 함수)가 호출됩니다.
binary 함수는 이항 연산자(Infix)를 처리합니다. 임무는 이렇습니다.
-
+의 오른쪽 피연산자(2)를 파싱한다. -
파싱이 끝나면, "스택 위의 두 값을 더해라"라는
OP_ADD명령어를 붙인다.
오른쪽 피연산자를 파싱하기 위해, binary 는 start_parsing_with('+')를 재귀 호출합니다. 이때 + 보다 한 단계 높은 * or / 우선순위를 넘겨줍니다. 이렇게 하는 이유는 자신보다 우선순위가 높은 연산자들을 재귀 호출을 통해 먼저 계산하도록 하는 것입니다.
Source: "-(1+2)"
Tokens: - ( 1 + 2 ) <EOF>
Parser: ^ ^
| |
pre cur
Call Stack: [ start_parsing_with('=') | start_parsing_with('-') | start_parsing_with('=') | start_parsing_with('* or /') ]
Byte-c: [OP_CONSTANT, 0]
Consts: [1.0]4단계 재귀입니다. start_parsing_with('* or /') 가 move_parser() 를 호출합니다. pre -> 2, cur -> ) 가 됩니다.
pre_token_processing('2') (즉, number())가 호출됩니다. Consts 배열 1번 인덱스에 2.0이 추가되고, Byte-c에 OP_CONSTANT, 1이 추가됩니다.
Source: "-(1+2)"
Tokens: - ( 1 + 2 ) <EOF>
Parser: ^ ^
| |
pre cur
Call Stack: [ start_parsing_with('=') | start_parsing_with('-') | start_parsing_with('=') | start_parsing_with('* or /') ]
Byte-c: [OP_CONSTANT, 0, OP_CONSTANT, 1]
Consts: [1.0, 2.0]number()가 리턴되고, start_parsing_with('* or / ')의 while 루프로 돌아옵니다. cur -> )입니다. )의 우선순위는 * or / 보다 낮습니다. while 루프는 종료되고, start_parsing_with('* or /')가 리턴됩니다. (4단계 재귀 종료)
이제 binary() 함수로 돌아옵니다. 오른쪽 피연산자(2) 파싱이 끝났습니다. binary는 자신의 임무인 OP_ADD 명령어를 Byte-c에 추가합니다.
Byte-c: [OP_CONSTANT, 0, OP_CONSTANT, 1, OP_ADD]
Consts: [1.0, 2.0]binary()가 리턴됩니다. (3단계 while 루프의 in_token_processing 종료)
다시 start_parsing_with('=')의 while 루프로 돌아옵니다. cur 는 여전히 ) 입니다. ) 의 우선순위는 = 보다 낮으므로 while 루프가 종료됩니다. start_parsing_with('=')가 리턴됩니다. (3단계 재귀 종료)
이제 grouping() 함수로 돌아옵니다. 괄호 안의 표현식(1+2) 파싱이 모두 끝났습니다. grouping의 마지막으로 cur 가 ) 인지 확인합니다. 문제가 없다면 move_parser() 를 호출하여 )를 소비합니다.
Source: "-(1+2)"
Tokens: - ( 1 + 2 ) <EOF>
Parser: ^ ^
| |
pre cur
Call Stack: [ start_parsing_with('=') | start_parsing_with('-') ]
Byte-c: [OP_CONSTANT, 0, OP_CONSTANT, 1, OP_ADD]
Consts: [1.0, 2.0]grouping() 이 리턴됩니다.
이제 start_parsing_with('-') 로 돌아옵니다. pre_token_processing('(') (즉, grouping())이 리턴되었습니다. while 루프를 검사합니다. cur 는 <EOF> 입니다. 우선순위가 가장 낮으므로 while 루프가 종료됩니다. start_parsing_with('-') 가 리턴됩니다. (2단계 재귀 종료)
unary() 함수로 돌아옵니다. 피연산자 (1+2)의 파싱이 모두 끝났습니다. unary는 마지막으로 OP_NEGATE 명령어를 Byte-c에 추가합니다.
Byte-c: [OP_CONSTANT, 0, OP_CONSTANT, 1, OP_ADD, OP_NEGATE]
Consts: [1.0, 2.0]unary()가 리턴됩니다.
최초에 호출했던 start_parsing_with('=') 로 돌아옵니다. pre_token_processing('-') (즉, unary())가 리턴되었습니다. while 루프를 검사합니다. cur 는 <EOF> 입니다. 우선순위가 낮으므로 while 루프가 종료됩니다. start_parsing_with('=')가 리턴됩니다. (1단계 재귀 종료)
모든 표현식 파싱 호출이 끝났습니다. 표현식이 종료되었기 때문에 최종적으로 cur 가 <EOF> 인지 확인합니다.
마지막으로 OP_RETURN 을 Byte-c 에 추가합니다.
// 최종 결과
Byte-c: [OP_CONSTANT, 0, OP_CONSTANT, 1, OP_ADD, OP_NEGATE, OP_RETURN]
Consts: [1.0, 2.0]바이트 코드 실행 과정
이것이 -(1+2)가 바이트코드로 컴파일되는 재귀 과정입니다. 이 바이트코드를 VM이 실행하면 다음과 같습니다.
-
OP_CONSTANT, 0: 스택에1.0을 푸시.
(스택:[1.0]) -
OP_CONSTANT, 1: 스택에2.0을 푸시.
(스택:[1.0, 2.0]) -
OP_ADD:1.0과2.0을 팝하여 더하고, 결과3.0을 푸시.
(스택:[3.0]) -
OP_NEGATE:3.0을 팝하여 부호를 바꾸고, 결과-3.0을 푸시.
(스택:[-3.0]) -
OP_RETURN:-3.0을 팝하여 출력.
(스택:empty)
이처럼 프랫 파서는 재귀 호출 스택을 이용하여, 코드를 작성하는 순서와 다르게 VM이 실행해야 하는 순서로 바이트코드를 재정렬합니다.
마치며
여태와는 다르게 이번 코드는 방대하며, 재귀적인 호출이 많았기에 이해하기 어려웠습니다. 그래서 지속적인 디버깅과 예제를 활용하여 다양한 상황에서 어떻게 파싱이 적용되는지 확인해보며 실행되는 과정을 지켜보고 분석하는 과정이 오래 걸렸습니다. 다음에는 Lox 언어에서 활용되는 값의 유형(type)에 대해 알아보겠습니다.
참고 자료: Cratring Interpreters - compiling expressions
Github: Will-big/clox
