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