프로그래밍을 한다면 컴파일러는 빼놓을 수 없는 부분입니다. 항상 사용하지만
어떻게 내부적으로 구현되어 있는지는 잘 알기 어려울 수 있습니다. 이 글은
작은 컴파일러를 직접 만들어보는 과정을 통해서 현대적인 컴파일러가 어떤 방식으로
동작하는지 설명합니다. 적은 양의 코드지만 구조나 동작 원리를 이해하는 데에는
부족함이 없습니 다. 더 자세히 알고 싶다면 찾아볼 수 있도록 각각의 키워드를
잘 알려주고 있어서 아주 유익합니다.
이 포스트는 jamiebuilds/the-super-tiny-compiler의 번역글입니다. 그리고 전체 코드는 the-super-tiny-compiler.js에서 확인할 수 있습니다.
아주 조그마한 컴파일러 만들기
오늘은 함께 컴파일러를 작성하려고 합니다. 하지만 그냥 아무 컴파일러가 아닌
엄청나게 작고 조그만 컴파일러를 만들겁니다! 컴파일러가 엄청 작은 나머지
파일에 있는 주석을 모두 지운다면 코드는 200여 줄만 남습니다.
여기서는 lisp 스타일의 함수 호출을 C 스타일의 함수 호출로 컴파일 하려고 합니다.
물론 이 스타일에 익숙하지 않을 수 있으니 짧게 설명하고 지나갈게요!
만약 두 함수 add와 subtract가 각 스타일로 작성되었다고 하면 다음과 같습니다.
LISP 스타일 C 스타일
2 + 2 (add 2 2) add(2, 2)
4 - 2 (subtract 4 2) subtract(4, 2)
2 + (4 - 2) (add 2 (subtract 4 2)) add(2, subtract(4, 2))
간단하죠?
이게 바로 우리가 컴파일 할 내용입니다. 완벽한 LISP이나 C 문법은 아니긴 하지만
요즘 현대적인 컴파일러가 어떤 역할을 하고 있는지 대략적으로 보여주기엔 적당한
예제입니다.
대부분 컴파일러는 분석, 변환, 코드 생성 같은 단계를 거칩니다.
- 분석(parsing) 단계에서는 코드 그대로를 좀 더 추상화된 코드로 변환합니다.
- 변환(transformation) 단계는 이 추상화된 코드를 컴파일러가 하려는 작업에
용이하도록 조작합니다.
- 코드 생성(code generation) 단계는 이 변환된 코드 표현을 갖고서 새로운
코드 형태로 변환하는 일을 합니다.
컴파일 단계
분석 (Parsing)
분석 단계는 일반적으로 어휘 분석과 구문 분석 단계로 나눠집니다.
-
어휘 분석(Lexical Analysis) 단계는 코드를 더 작은 형태인 토큰(token)
단위로 나누는 작업을 합니다. 토크나이저(tokenizer) 또는 렉서(lexer)가
이 작업을 수행합니다.
토큰은 배열 형태의 작은 개체로 한 조각의 문법을 담고 있습니다. 숫자나
꼬리표(labels), 구두법, 연산자 등 어떤 것이든 이렇게 저장됩니다.
-
구문 분석(Syntatic Analysis) 단계는 앞 단계에서 만든 토큰을 각각의 문법이나
서로 관계를 잘 표현하는 형태로 재구성하게 됩니다. 이 과정으로 만든 결과물을
중간 표현(intermediate representation) 또는 추상 구문 트리(Abstract Syntax
Tree)이라고 말합니다.
추상 구문 트리(줄여서 AST)는 깊숙하게 중첩된 형태의 개체로 존재합니다. 그
형태로 코드가 쉽게 동작할 수 있으며 동시에 많은 정보를 알려줍니다.
다음 구문을 봅시다.
이 구문에서 생성한 토큰은 다음과 같은 모습입니다.
[
{ type: 'paren', value: '(' },
{ type: 'name', value: 'add' },
{ type: 'number', value: '2' },
{ type: 'paren', value: '(' },
{ type: 'name', value: 'subtract' },
{ type: 'number', value: '4' },
{ type: 'number', value: '2' },
{ type: 'paren', value: ')' },
{ type: 'paren', value: ')' },
]
그리고 추상 구문 트리(AST)는 이런 모습이 될 겁니다.
{
type: 'Program',
body: [{
type: 'CallExpression',
name: 'add',
params: [{
type: 'NumberLiteral',
value: '2',
}, {
type: 'CallExpression',
name: 'subtract',
params: [{
type: 'NumberLiteral',
value: '4',
}, {
type: 'NumberLiteral',
value: '2',
}]
}]
}]
}
컴파일러의 다음 단계는 변환입니다. 다시 말하면 앞 단계에서 생성한 AST를
갖고서 변환 작업을 수행합니다. AST를 동일한 언어로 조작하거나 완전히 다른
언어로 번역할 수도 있습니다.
이제 이 AST를 어떻게 변환하는지 확인해봅시다.
AST를 보면 비슷하게 생긴 요소가 많은걸 알 수 있습니다. 각 개체마다 타입
속성(property)를 포함하고 있습니다. 각각 개체를 AST 노드라고 부릅니다.
이 각각의 노드는 여러 속성이 있으며 동시에 트리의 일부를 각자 정의하는
역할을 하고 있습니다.
"NumberLiteral" 노드를 상상해봅시다.
{
type: 'NumberLiteral',
value: '2',
}
또는 "CallExpression" 이라는 노드도 존재할 수 있죠.
{
type: 'CallExpression',
name: 'subtract',
params: [...여기에 중첩 노드가 위치합니다...],
}
AST를 변환하면서 속성을 추가하거나 제거, 치환하는 식으로 노드를 조작할 수
있습니다. 그러면서 새로운 노드를 추가하거나 제거하거나 아니면 아예 AST를
그대로 두고 완전 새로운 트리를 만들어낼 수도 있습니다.
여기서는 새로운 언어로 변환하는 것이 목표이기 때문에 목표가 되는 언어에
딱 맞춰서 새로운 AST를 만들기로 합니다.
순회 (Traversal)
이 노드를 모두 탐색하려면 일일이 순회 할 필요가 있습니다. 이 순회 과정은
AST의 각 노드를 깊이 우선으로 탐색합니다.
{
type: 'Program',
body: [{
type: 'CallExpression',
name: 'add',
params: [{
type: 'NumberLiteral',
value: '2'
}, {
type: 'CallExpression',
name: 'subtract',
params: [{
type: 'NumberLiteral',
value: '4'
}, {
type: 'NumberLiteral',
value: '2'
}]
}]
}]
}
이 AST라면 다음 같은 순서로 접근하게 됩니다.
- Program - AST의 가장 윗 단계에서 시작
- CallExpression (add) - Program의 첫 요소로 이동
- NumberLiteral (2) - CallExpression 속성의 첫 번째 요소로 이동
- CallExpression (subtract) - CallExpression 속성의 두 번째 요소로 이동
- NumberLiteral (4) - CallExpression 속성의 첫 번째 요소로 이동
- NumberLiteral (2) - CallExpression 속성의 두 번째 요소로 이동
만약 분리된 AST를 생성하는 것 대신에 AST를 직접 변환한다면 여기서 온갖 종류의
추상적 접근을 소개해야 합니다. 다만 여기서의 목적으로는 단순히 트리 내 각 노드를
일일이 보는, 방문하는 정도면 충분하겠습니다.
여기서 "방문하다(visiting)"이란 표현을 사용한건 이유가 있습니다. 바로 개체
구조의 요소를 대상으로 연산하게 되는데 거기서 사용하는 패턴이 비지터 패턴을 사용하기
때문입니다.
방문자(Visitors)
여기서 "방문자" 개체를 만드는데 이 개체에 각각 메소드로 다른 노드 타입을
처리하도록 하는게 기본 아이디어입니다.
var visitor = {
NumberLiteral() {},
CallExpression() {},
};
AST를 순회하면서 노드에 "입장"할 때면 그 노드 타입에 맞춰서 이 방문자 개체에
있는, 동일한 이름의 메소드를 호출할 겁니다.
이걸 유용하게 만들려면 해당 노드와 함께 부모 노드의 참조도 그 메소드에
전달해야 합니다.
var visitor = {
NumberLiteral(node, parent) {},
CallExpression(node, parent) {},
};
하지만 "퇴장"하는 경우에 무언가를 호출해야 하는 가능성도 있습니다. 앞서 트리
구조를 목록 형태로 다시 확인해봅시다.
- Program
- CallExpression
- NumberLiteral
- CallExpression
- NumberLiteral
- NumberLiteral
트리를 순회해서 가지(branch) 끝까지 내려가면 더이상 갈 곳이 없는 곳에 도달하게
됩니다. 각 가지 끝에 도달하면 그 가지에서 "퇴장"해야 합니다. 즉 트리를 타고
내려 가면 각 노드에 "입장"해야 하고 다시 올라오면서 "퇴장"해야 하는 겁니다.
-> Program (입장)
-> CallExpression (입장)
-> Number Literal (입장)
<- Number Literal (퇴장)
-> Call Expression (입장)
-> Number Literal (입장)
<- Number Literal (퇴장)
-> Number Literal (입장)
<- Number Literal (퇴장)
<- CallExpression (퇴장)
<- CallExpression (퇴장)
<- Program (퇴장)
최종적으로 입장과 퇴장을 처리할 수 있는 방문자 개체의 모습은 다음과 같습니다.
var visitor = {
NumberLiteral: {
enter(node, parent) {},
exit(node, parent) {},
}
};
코드 생성 (Code Generation)
컴파일러 최종 단계는 코드 생성입니다. 컴파일러는 종종 변환 단계서 하는 작업과
겹치는 작업을 여기서 하게 되는데 대부분 코드 생선 단계에서는 AST를 가지고
문자열 같은 코드 형태로 출력하는 일을 하게 됩니다.
코드 생성기는 여러 다른 방식으로 동작하는데 어떤 컴파일러는 앞서 생성한 토큰을
재활용하기도 하고 또 다른 방식은 완전히 코드와 분리된 표현식을 생성해서 노드를
선형적으로 생성하기도 합니다. 하지만 여기서 얘기하자면 대부분은 동일한 AST를
생성하기 때문에 여기서도 그 방법에 집중하려고 합니다.
코드 생성기는 모든 다른 노드 타입을 어떻게 "출력"하는지 실질적으로 알고 있게
될 겁니다. 또한 중첩된 노드를 하나의 긴 문자열 코드로 전부 출력할 때까지
스스로를 재귀적으로 호출하도록 작성하려고 합니다.
여기까지! 컴파일러에 필요한 모든 부분을 확인했습니다.
물론 모든 컴파일러가 여기서 설명한 것처럼 완전 동일하게 동작하진 않을 겁니다.
컴파일러는 각각 다른 용도에 따라 쓰이기도 하고 여기서 설명보다 더 많은 단계로
동작하기도 합니다.
하지만 컴파일러 대부분에서 찾을 수 있는 고수준의 개념은 여기서 다 얘기했습니다.
이제 모든 내용을 설명했으니 가서 컴파일러를 직접 만들 수 있으시겠죠?
물론 농담입니다 :) 여기서 함께 작성해보도록 합시다!
코드 작성하기
토크나이저 (Tokenizer)
컴파일러의 가장 첫 단계인 분석에서 어휘 분석을 토크나이저로 시작합니다.
다음 코드 문자열을 갖고 토큰 배열 형태로 변환할 겁니다.
(add 2 (subtract 4 2)) => [{ type: 'paren', value: '(' }, ...]
이제 코드를 작성해봅시다.
function tokenizer(input) {
let current = 0;
let tokens = [];
while (current < input.length) {
let char = input[current];
if (char === '(') {
tokens.push({
type: 'paren',
value: '(',
});
current++;
continue;
}
if (char === ')') {
tokens.push({
type: 'paren',
value: ')',
});
current++;
continue;
}
let WHITESPACE = /\s/;
if (WHITESPACE.test(char)) {
current++;
continue;
}
let NUMBERS = /[0-9]/;
if (NUMBERS.test(char)) {
let value = '';
while (NUMBERS.test(char)) {
value += char;
char = input[++current];
}
tokens.push({ type: 'number', value });
continue;
}
if (char === '"') {
let value = '';
char = input[++current];
while (char !== '"') {
value += char;
char = input[++current];
}
char = input[++current];
tokens.push({ type: 'string', value });
continue;
}
let LETTERS = /[a-z]/i;
if (LETTERS.test(char)) {
let value = '';
while (LETTERS.test(char)) {
value += char;
char = input[++current];
}
tokens.push({ type: 'name', value });
continue;
}
throw new TypeError('I dont know what this character is: ' + char);
}
return tokens;
}
파서 (Parser)
파서에서는 토큰이 담긴 배열을 AST로 변환하려고 합니다.
[{ type: 'paren', value: '(' }, ...] => { type: 'Program', body: [...] }
코드를 작성해봅시다.
'use strict';
function parser(tokens) {
let current = 0;
function walk() {
let token = tokens[current];
if (token.type === 'number') {
current++;
return {
type: 'NumberLiteral',
value: token.value,
};
}
if (token.type === 'string') {
current++;
return {
type: 'StringLiteral',
value: token.value,
};
}
if (
token.type === 'paren' &&
token.value === '('
) {
token = tokens[++current];
let node = {
type: 'CallExpression',
name: token.value,
params: [],
};
token = tokens[++current];
while (
(token.type !== 'paren') ||
(token.type === 'paren' && token.value !== ')')
) {
node.params.push(walk());
token = tokens[current];
}
current++;
return node;
}
throw new TypeError(token.type);
}
let ast = {
type: 'Program',
body: [],
};
while (current < tokens.length) {
ast.body.push(walk());
}
return ast;
}
트래버서 (Traverser, 순회자)
AST까지 만들었으니 방문자가 각 노드를 방문하는 작업을 해야 합니다. 매 노드를
방문하면서 노드의 타입과 일치하는 방문자의 메소드를 호출하는 코드를 작성해야
합니다.
traverse(ast, {
Program: {
enter(node, parent) {
},
exit(node, parent) {
},
},
CallExpression: {
enter(node, parent) {
},
exit(node, parent) {
},
},
NumberLiteral: {
enter(node, parent) {
},
exit(node, parent) {
},
},
});
이제 코드로 적어봅시다.
function traverser(ast, visitor) {
function traverseArray(array, parent) {
array.forEach(child => {
traverseNode(child, parent);
});
}
function traverseNode(node, parent) {
let methods = visitor[node.type];
if (methods && methods.enter) {
methods.enter(node, parent);
}
switch (node.type) {
case 'Program':
traverseArray(node.body, node);
break;
case 'CallExpression':
traverseArray(node.params, node);
break;
case 'NumberLiteral':
case 'StringLiteral':
break;
default:
throw new TypeError(node.type);
}
if (methods && methods.exit) {
methods.exit(node, parent);
}
}
traverseNode(ast, null);
}
다음은 트랜스포머입니다. 생성한 AST를 방문자와 함께 순회 함수로 호출하면 새로운 AST를 생성하게 됩니다.
----------------------------------------------------------------------------
원본 AST | 변환된 AST
----------------------------------------------------------------------------
{ | {
type: 'Program', | type: 'Program',
body: [{ | body: [{
type: 'CallExpression', | type: 'ExpressionStatement',
name: 'add', | expression: {
params: [{ | type: 'CallExpression',
type: 'NumberLiteral', | callee: {
value: '2' | type: 'Identifier',
}, { | name: 'add'
type: 'CallExpression', | },
name: 'subtract', | arguments: [{
params: [{ | type: 'NumberLiteral',
type: 'NumberLiteral', | value: '2'
value: '4' | }, {
}, { | type: 'CallExpression',
type: 'NumberLiteral', | callee: {
value: '2' | type: 'Identifier',
}] | name: 'subtract'
}] | },
}] | arguments: [{
} | type: 'NumberLiteral',
| value: '4'
---------------------------------- | }, {
| type: 'NumberLiteral',
| value: '2'
| }]
(미안하지만 변환된 쪽이 더 길어요..) | }
| }
| }]
| }
----------------------------------------------------------------------------
이제 AST를 받는 변환 함수를 작성합니다.
function transformer(ast) {
let newAst = {
type: 'Program',
body: [],
};
ast._context = newAst.body;
traverser(ast, {
NumberLiteral: {
enter(node, parent) {
parent._context.push({
type: 'NumberLiteral',
value: node.value,
});
},
},
StringLiteral: {
enter(node, parent) {
parent._context.push({
type: 'StringLiteral',
value: node.value,
});
},
},
CallExpression: {
enter(node, parent) {
let expression = {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: node.name,
},
arguments: [],
};
node._context = expression.arguments;
if (parent.type !== 'CallExpression') {
expression = {
type: 'ExpressionStatement',
expression: expression,
};
}
parent._context.push(expression);
},
}
});
return newAst;
}
코드 제너레이터 (Code generator, 코드 생성기)
이제 마지막 단계인 코드 생성기를 살펴봅니다.
이 코드 생성기는 함수 스스로를 재귀적으로 호출해서 트리에 있는 각 노드를 하나의 긴 문자열로 출력하게 됩니다.
function codeGenerator(node) {
switch (node.type) {
case 'Program':
return node.body.map(codeGenerator)
.join('\n');
case 'ExpressionStatement':
return (
codeGenerator(node.expression) +
';'
);
case 'CallExpression':
return (
codeGenerator(node.callee) +
'(' +
node.arguments.map(codeGenerator)
.join(', ') +
')'
);
case 'Identifier':
return node.name;
case 'NumberLiteral':
return node.value;
case 'StringLiteral':
return '"' + node.value + '"';
default:
throw new TypeError(node.type);
}
}
컴파일러 (compiler)
드디어 끝났습니다! 이제 compiler 함수를 만듭니다. 지금까지 만든, 모든
함수를 하나의 함수로 묶습니다.
- 입력 => 토크나이저 => 토큰 묶음
- 토큰 묶음 => 파서 => 추상 구문 트리(AST)
- AST => 트랜스포머 => 새 AST
- 새 AST => 코드 생성기 => 출력
함수와 인자명으론 다음처럼 정리할 수 있습니다.
1. input => tokenizer => tokens
2. tokens => parser => ast
3. ast => transformer => newAst
4. newAst => generator => output
이제 함수로 작성해볼까요?
function compiler(input) {
let tokens = tokenizer(input);
let ast = parser(tokens);
let newAst = transformer(ast);
let output = codeGenerator(newAst);
return output;
}
모두 완성되었습니다! (테스트 코드도 확인해보세요.)
