BASIC에서 Go로 변환하는 자신만의 간단한 컴파일러(toybasic)를 직접 만든 과정을 단계별로 소개합니다.
컴퓨터과학 학위가 있습니다. 컴파일러에 관한 전체 강의도 들은 적이 있고, 그 결과로 "빨간 용 책"을 꽤 좋아하게 되었죠. 하지만 사실 이번 지난 주말의 비 오는 날까지 처음부터 끝까지 직접 컴파일러 를 써본 적은 없었습니다. 네, 이게 바로 저의 취미입니다.
진짜 언어를 위한 컴파일러를 만들고 싶었지만, 몇 시간 만에 프로젝트를 끝낼 수 있을 만큼 단순한 언어여야 했어요. 예전부터 BASIC에 약간 애착이 있었는데—어릴 때 처음 배운 프로그래밍 언어니까요. 다행히 TinyBASIC이라는 실용적인 변형이 있다는 걸 알게 되었습니다(wikipedia에게 감사!). 제가 만든 버전은 TinyBASIC보다 더 단순해서(INPUT
문 없음) 이름을 toybasic
이라 붙였습니다. 전체 코드는 GitHub에서 볼 수 있습니다.
Go로 작성되었고, BASIC을 Go 코드로 변환합니다.
예제 프로그램 example/hello.bas
10 PRINT "Hello, world."
20 LET x = (3 * 2) + 3
30 LET x = x + 1
40 IF x == 10 THEN PRINT "Ten!"
45 PRINT x
50 IF x >= 15 THEN GOTO 70
60 GOTO 30
70 END
예상되는 출력 결과
$ ./toybasic <example/hello.bas
$ go run out.go
Hello, world.
Ten!
10
11
12
13
14
15
제가 만든 컴파일러는 세 단계로 이루어져 있습니다:
어휘 분석기와 파서는 전부 직접 작성할 수도 있지만, 이를 단순화해주는 좋은 오프더셸프 도구들이 있습니다. 전통의 lex
와 yacc
는 1975년부터 C 언어에서 이 문제를 해결해 왔죠. yacc
의 원저자는 Mike Lesk와 Eric Schmidt—네, 그 Eric Schmidt입니다.
Go에는 여러 lex
클론이 있는데, 저는 nex
를 선택해 어휘 분석기를 만들었습니다. Nex는 awk
와 유사한 직관적인 문법과 매우 따라하기 쉬운 README를 갖추고 있습니다.
Go에는 기본 도구로 포함된 goyacc
라는 yacc 변형이 있어서, 파서 쪽에는 이를 사용했습니다.
코드 처리의 두 번째 단계이지만, 파서에는 toybasic의 문법 이 담겨 있어 컴파일러를 작성하거나 설명할 때 가장 좋은 출발점입니다. 저의 문법은 Bogdan Kravtsov의 tinybasic에서 영감을 받았지만, 문자열을 추가하고 INPUT
을 뺐습니다. 전체 문법은 여기서 볼 수 있습니다. 일부 예시를 보면:
statement:
PRINT expr_list { $$ = opr(PRINT, 1, $2); }
| IF expression relop expression THEN statement { $$ = opr(IF, 4, $2, $3, $4, $6); }
| GOTO expression { $$ = opr(GOTO, 1, $2); }
| LET v '=' expression { $$ = opr(LET, 2, $2, $4); }
| END { $$ = opr(END, 0); }
;
언어의 문법을 특수한 문법으로 정의하고, 컴파일된 트리를 생성하기 위해 해당 심볼을 파싱할 때 goyacc
가 실행할 Go 코드를 제공합니다. 위는 toy BASIC이 지원하는 모든 문(statement)을 파싱하는 부분입니다. opr
함수는 문법 트리를 구성하는 데 필요한 객체를 만드는 역할을 제 코드에서 합니다.
결과적으로 다음과 같은 BASIC 문장은:
10 PRINT "Look!", (2 + 3) * 3
아래와 같은 트리로 파싱됩니다:
PrintOp
|
ListOp --------.
| |
StringOp *Op --------.
| |
GroupOp INTEGER
|
InfixOp
| | |
INTEGER + INTEGER
문법 정의 옆에는 트리의 각 노드에 채워야 하는 속성을 지정하는 중요한 테이블도 있습니다:
%union {
v string /* 변수 */
s string /* 문자열 */
num int /* 정수 상수 */
dec float64 /* 실수 상수 */
node Node /* AST 내 노드 */
};
nex
는 결정적 유한 오토마타(Deterministic Finite Automata)를 이용해 언어를 토큰화하는 데 필요한 Go 코드를 생성합니다. 아래는 toybasic을 위해 자동 생성된 1000여 줄이 넘는 코드 중 극히 일부입니다. 이걸 손으로 직접 짤 필요가 없다는 게 정말 다행이죠.
...
var dfas = []dfa{
// LET
{[]bool{false, false, false, true}, []func(rune) int{ // 상태 전이
func(r rune) int {
switch r {
case 69:
return -1
case 76:
return 1
case 84:
return -1
}
return -1
},
...
}, []int{ /* 입력 시작 시 전이 */ -1, -1, -1, -1}, []int{ /* 입력 종료 시 전이 */ -1, -1, -1, -1}, nil},
...
대신, nex
는 구성 파일(여기에 있습니다)을 받아, 언어의 키워드와 식별자를 모두 담을 수 있는 정규표현식 집합을 지정합니다. 몇 가지 예를 보면:
/PRINT/ {return PRINT}
/==/ {return EQ}
/[0-9]+/ {lval.num, _ = strconv.Atoi(yylex.Text()); return INTEGER}
/[0-9]+\.[0-9]*/ {lval.dec, _ = strconv.ParseFloat(yylex.Text(), 64);return DECIMAL}
/"[^"]*"/ {lval.s = yylex.Text(); return STRING}
왼쪽의 /
로 감싼 부분이 정규표현식입니다. 우선순위대로 나열해야 하고, 이 코드는 yacc
문법과 긴밀히 연결됩니다. 각 정규식이 일치하면 중괄호 내 Go 코드를 실행해 토큰 타입을 반환하고, 트리의 리프 노드에 해당하는 속성을 채워줘야 합니다.
직접 Go로 작성해야 하는 유일한 부분이 이겁니다. 구문 트리의 가능한 각 노드 타입을 정의하고, 각 Node
타입에는 해당 노드를 Go 코드로 변환할 줄 아는 Generate
함수가 있습니다(필요하면 자식 노드의 Generate
도 호출).
type Node interface {
Generate()
}
...
type PrintOp struct {
expression Node
}
func (op PrintOp) Generate() {
fmt.Fprint(writer, "fmt.Println(")
op.expression.Generate()
fmt.Fprintln(writer, ")")
}
PrintOp
는 이런 식입니다. 자식 노드가 생성하는 코드를 fmt.Println([자식 노드의 코드])
형태로 Go로 만들어냅니다!
이상으로 toy BASIC에서 Go로 변환해주는 컴파일러가 완성됐습니다. 테스트를 위해 언어의 모든 구문을 사용하는 작은 BASIC 프로그램을 짜고, 기대한 대로 동작하고 출력도 맞는지 확인했습니다. 이론적으로 각 단계가 어떻게 동작하는지 알고 있었지만, 실제로 직접 해보며 정말 많은 걸 배웠고 엄청나게 재미있는 경험이었습니다. 비 오는 토요일 오후를 보내기에 딱 좋은 방법이죠.
이제 제가 프로그래밍을 처음 배울 때 가장 먼저 만들었던 BASIC 프로그램도 여전히 잘 동작함을 확실하게 증명할 수 있게 되었습니다.
10 PRINT "David is cool"
20 GOTO 10