[CS] 나만의 인터프리터를 만들어보자!(1): Lexer 만들기

🔊 해당 포스팅은 밑바닥부터 만드는 인터프리터 in go 책을 읽고 개인적인 정리 목적 하에 작성된 글입니다. 본 포스팅에 사용된 자료는 모두 본인이 직접 재구성하여 작성하였음을 알립니다.
 
최근에 C언어를 조금씩 접하기 시작하면서 로우 레벨 프로그래밍 언어 공부에 대한 갈증이 많아졌다. 하지만 C언어에 대한 기초를 배우고 난 뒤, 가장 당혹스러웠던 부분은 현재 실무에서 C언어를 자주 접할 일이 없어서 프로젝트 할만한 게 없다는 것이었다. 물론 Python의 구현체 중 하나인 CPython 소스코드를 살펴볼 수 있겠지만, 이것도 단지 '보기만 할 뿐'이지, 뭔가 결과물이 있거나 내 지식으로 체득되는 느낌이 아니었다. 그러던 중, 요즘 실무에서 쿠버네티스 기술과 Go로 작성된 벡터 데이터베이스인 Milvus(검색 엔진은 C계열로 작성되었지만) 등을 다루어보면서 Go언어에 대한 공부의 필요성을 느꼈다. 그리고 아래의 책을 추천받아 CS 공부를 더 하고 싶었는데, 아래 책이 Go언어로 작성된 것을 발견했다! 그래서 해당 책을 깊게 공부하기로 마음 먹었다. CS 지식을 소스코드 레벨에서 이해하고, 그 소스코드도 내가 배우고자 하는 Go언어를 배우면서 말이다. 그러면 이번에도 천천히 한 걸음씩 내딛어보자!
 

출처: Yes24

---

일반적으로 사람들이 주로 사용하는 Python 즉, CPython 구현체로 구현된 Python 언어는 인터프리터 언어에 속한다. 물론 내부적으로 일부 바이트 코드로 컴파일하는 과정이 있지만, C언어나 Java, Go 언어들과 같은 완전 컴파일 언어는 아니다. Python 이라는 언어를 주로 사용해온 개발자로서, 궁금했다. 대체 인터프리터는 어떤 원리로 만들어지는 것일까?
 
인터프리터는 정말 그 자체로는 단순하다. 'interpret' 라는 영어단어의 의미처럼 "어떤 것을 해석 즉, 번역한다". 다시 말해, 어떤 것을 입력으로 받는 순간, 바로 무엇인가 출력으로 튀어나온다. 우리가 흔히 대화형 인터프리터라고 하는 것처럼, 터미널에 python 이라는 명령어를 쳐 접속한 후, 코드를 입력할 때마다 결과물이 콘솔에 출력되어 나온다. 그러면 단순한 동작을 수행하는 인터프리터는 대체 어떤 원리도 동작하는 걸까? 우리는 이제 앞으로 이 원리에 대해 알아보려고 한다.
 
물론 모든 인터프리터가 방금 언급한 것처럼 단순히 번역하는 동작만 수행하진 않는다. CPython도 내부적으로는 바이트 코드로 변환하는 동작이 수반된다.(이 과정을 거쳐 나오는 파일이 확장자 .pyc 라는 파일이다) 즉, 입력을 단순히 평가하는 게 아니라, 바이트 코드라는 내부 표현물로 컴파일한 다음 평가한다. 좀 더 진보된 인터프리터 종류로는 JIT(Just in Time) 인터프리터로, 입력을 그 자리에서 네이티브 기계어로 컴파일한 후 실행을 하기도 한다.
 
이렇게 상용화되고 진보된 인터프리터의 원리에 대해서는 배우지는 않는다. 우리는 이러한 인터프리터들 보다는 비록 성능이 좋지 않겠지만 더 간단한 원리로 만들어지는 인터프리터를 직접 만들어보면서 원리를 익혀볼 것이다. 이 원리라 함은 사용자가 입력한 소스코드를 파싱하고, 이를 추상구문트리(AST, Abstract Syntax Tree)로 만들고, 이것을 평가하는 이른바 '트리 탐색(tree-walking) 인터프리터'를 의미한다.
 
트리 탐색 인터프리터를 구현하기 위해서는 렉서(Lexer), 파서(Parser), 트리 표현법(Tree representation), 평가기(Evaluator)를 만들어야 한다. 이번 포스팅에서는 그 첫번째 구성요소로, 렉서를 만들어볼 것이다.
 
참고로 해당 책에서 원저자는 해당 책을 이해하기 위해 Go 언어에 대해서 아예 몰라도 이해할 수 있다고 한다. 하지만 번역가분도 책에서 언급했듯이 필자의 생각에도 Go 언어에 대한 기초는 간단히 숙지한 후 책을 읽기를 권장한다. 필자도 Go 언어에 대한 기초를 간단하고 빠르게 습득한 후 책을 읽으니 수월했다. 개인적으로는 Go 공식 문서의 Tutorials 와 A Tour of Go 정도는 같이 병행하면서 책을 읽기를 권장한다.

---

1. 소스코드라는 어휘를 분석하는 과정

소스코드를 가지고 어떤 작업을 수행하려면 이 소스코드를 좀더 접근하기 쉬운 형태로 변환할 필요가 있다. 이 변환 작업을 수행하기 위해서는 아래의 단계들이 필요하다. 아래 그림을 보자.
 

소스코드가 추상구문트리 까지 가는 과정

 
먼저 소스코드 형태는 여러 개의 토큰들로 나뉘어져야 한다. 최근 대 LLM 시대에 접어들면서 '토큰'이라는 단어는 대부분 익숙할 것이다. 자연어 처리할 때의 토큰 의미와 유사하다. 어쨌건 소스코드도 문자열 형태이다. 이 문자열들을 어떤 단위로 댕강댕강 잘라내야 하는데, 이 과정을 인터프리터에서는 어휘 분석 즉, 렉싱(Lexing)이라고 용어를 정의한다. 이 때, 렉싱을 수행하는 주체는 렉서가 수행한다.
 
이제 잘게 쪼개진 토큰들은 트리 형태의 자료구조인 추상구문트리로 변환이 되는데, 이를 파싱(Parsing)이라고 하며 파싱을 수행하는 주체는 파서가 된다.
 
우리는 이번 목차에서는 위 과정 중 Lexing 을 수행하는 Lexer를 만들어볼 것이다.

2. 가장 먼저 할 일: 토큰 정의하기

렉싱을 본격적으로 하기에 앞서 가장 먼저 할 일은 토큰을 미리 정의하는 것이다. 직전 목차에서 봤던 그림을 보면 이상하다 싶을 수 있다. 렉싱을 거쳐서 나온 게 토큰이라면서 왜 토큰을 먼저 정의하는 것이지? 할 수 있다. 토큰을 먼저 정의해야 하는 이유는 컴퓨터에게 "이런 문자열은 이런 뜻이야" 라고 매핑할 수 있도록 마치 가이드를 주는 셈이다. 머신러닝 분야에서 쉽게 이야기해보자면, 자연어 처리를 하거나 카테고리컬한 성격이 있는 피쳐를 인코딩 할 때, 어떤 단어는 어떤 숫자에 매핑되도록 한다. 이렇게 단어와 숫자가 매핑된 자료구조를 일명 사전(Vocabulary)이라고도 한다.
 
다시 말해, 컴퓨터에게 "소스코드 중 '=' 라는 문자가 있으면 이건 어떤 값을 할당한다는 의미야. 또는 '+' 라는 문자가 나오면 이것은 덧셈 연산을 의미하는 거야." 처럼 이야기 해주기 위해, 소스코드에 어떤 문자열이 등장하면 이것은 어떤 것을 의미하는지 나타내는 토큰을 사전에 미리 정의해놓는 것이다. 인터프리터를 계속 확장해서 개발할 때, 이전에 컴퓨터가 알아듣지 못했던 문자열을 이해시키기 위해서 단순히 이 토큰이라는 것에 추가하기만 하면 되는 것이다.
 
이제 토큰을 정의하기 위해서 우리만의 프로그래밍 언어 소스코드를 먼저 살펴보자. 이 소스코드는 (책에서도 소개하는) Monkey 라는 세상에 상용화되어 있지 않지만 우리만의 프로그래밍 언어 소스코드이다. 우리는 이 Monkey 라는 프로그래밍 언어로 작성되어 있는 소스코드를 렉싱하는 렉서를 만들 것이다.
 

let five = 5;
let ten = 10;

let add = fn(x, y) {
  x + y;
};

let result = add(5, 10);

 
위 소스코드를 보았을 때, 사전에 정의해야 할 토큰은 무엇이 있을까?

• 5, 10과 같은 값을 보고 숫자 토큰 타입이 필요. 참고로 정수형에 대한 토큰이면 됨. 렉서와 파서는 숫자인지만 식별하면 됨. 숫자가 5인지 10인지는 신경쓰지 않아도 됨
• x, y, five, ten, add, result 를 보고 변수 이름이라고 추측할 수 있다. 즉, 식별자 중 '사용자 정의 식별자'를 위한 토큰이 필요
• fn, let 과 같이 식별자이긴 하지만, 변수가 아닌 일명 예약어에 대한 토큰이 필요
• { } , ( ) ; = 과 같이 특수문자에 대한 토큰이 필요

토큰을 이제 정의해보자. 그리고 토큰을 담고 렉서에서 사용하기 위해서 구조체를 활용해 정의하자.
 

// token/token.go

package token

type TokenType string

type Token struct {
	Type    TokenType
	Literal string   // 여기엔 토큰화한 문자열을 담아놓을 곳
}

const (
	ILLEGAL = "ILLEGAL"
	EOF     = "EOF"

	// Identifiers + literals
	IDENT = "IDENT" // add, result, x, y, ...
	INT   = "INT"   // 1343456

	// Operators
	ASSIGN   = "="
	PLUS     = "+"

	// Delimiters
	COMMA     = ","
	SEMICOLON = ";"

	LPAREN = "("
	RPAREN = ")"
	LBRACE = "{"
	RBRACE = "}"

	// 예약어
	FUNCTION = "FUNCTION"
	LET      = "LET"
)

 
위에서 정의한 토큰 중 특이한 것이 2개 있다. 바로 ILLEGAL 과 EOF이다. ILLEGAL은 렉서가 알 수 없는 토큰이나 문자를 마주했을 때 명시할 타입이다. 그리고 EOF는 End Of File의 줄임말로, 말 그대로 입력된 소스코드의 끝이다. 이 EOF는 추후에 만들 파서에게 이제 그만 파싱을 멈추라고 알려주는 시그널이기도 하다.

2. 소스코드를 토큰화시키기: Lexing

이제 본격적으로 Lexing을 수행하는 렉서를 만들어볼 차례다. 가장 처음에는 간단한 소스코드만 렉싱할 수 있는 기능을 만들고, 이를 하나씩 점점 고도화시키는 단계로 진행한다. 그에 앞서 우리가 만든 렉서가 잘 동작하는지 테스트하는 테스트 코드부터 소개한다. 그리고 난 뒤, 이 테스트 코드에서 사용되고 있는 함수 하나하나의 기능을 코드 조각으로 살펴보도록 하자.
(참고로 Go를 활용한 테스트 코드 작성 방법은 여기서 다루지 않는다. 공식 문서에서 잘 가이드 되어있으니, 혹시 모른다면 꼭 읽어보자)
 

// lexer/lexer_test.go

package lexer

import (
	"monkey/token"
	"testing"
)

func TestNextToken(t *testing.T) {
	input := `=+(){},;`

	tests := []struct {
		expectedType    token.TokenType
		expectedLiteral string
	}{
		{token.ASSIGN, "="},
		{token.PLUS, "+"},
		{token.LPAREN, "("},
		{token.RPAREN, ")"},
		{token.LBRACE, "{"},
		{token.RBRACE, "}"},
		{token.COMMA, ","},
		{token.SEMICOLON, ";"},
		{token.EOF, ""},
	}

	src := New(input)

	for i, tt := range tests {
		tok := src.NextToken()
		if tok.Type != tt.expectedType {
			t.Fatalf("tests[%d] - tokentype wrong. expected=%q, got=%q",
				i, tt.expectedType, tok.Type)
		}
		if tok.Literal != tt.expectedLiteral {
			t.Fatalf("tests[%d] - literal wrong. expected=%q, got=%q",
				i, tt.expectedLiteral, tok.Literal)
		}
	}
}

 
가장 먼저 input 변수명을 보면 백틱(`)을 활용해서 어떤 문자열을 명시했다. 참고로 Go언어에서 백슬래쉬나 개행을 문자로 간주하기 위해서는 백틱을 사용하면 된다. 어쨌건 백틱을 활용해 문자열을 명시한 것이 바로 렉서가 렉싱할 대상인 소스코드이다. 즉, 우리는 아래의 소스코드를 렉싱할 것이다.

=+(){},;

 
그리고 tests 라는 변수에 슬라이스로 이루어진 구조체를 정의했다. 해당 구조체에는 2개의 멤버를 갖는데, 하나는 직전 목차에서 정의한 token.TokenType 이라는 타입이다. 그리고 나머지 하나는 문자열 타입이다. 그리고 구조체들을 정의했다. 이 구조체들은 사실 방금 '렉서가 렉싱할 대상인 소스코드'를 토큰으로 사전에 분할해 놓은 것이다. 어떻게 보면 정답을 미리 정의한 셈이다. 우리는 이 '정답'을 가지고 for loop 구문을 이용해 우리가 만든 렉서가 잘 동자하는지 검사하는 것이다.
 
src 변수를 보면 New 라는 함수에 소스코드 문자열을 넣어주었다. 이 함수는 렉서가 렉싱할 수 있도록 만드는 구조체로 만드는 역할을 한다. 추후에 소개할 것이다. 이제 for loop 구문을 보자. tests 라는 변수에 정의한 즉, 미리 정의한 토큰 정답을 하나씩 loop를 돌면서 우리가 만든 렉서가 소스코드 문자열을 잘 렉싱하는지 테스트하는 것이다. 
 
이제 그러면 테스트 코드에 작성되어 있는 아직 소개하지 않은 여러가지 함수들을 하나씩 살펴보자.

2-1. 렉싱할 수 있는 대상으로 만들기

가장 먼저 입력으로 받은 소스코드 문자열(src 변수)을 우리만의 렉서가 렉싱할 수 있는 대상으로 만들어야 한다. 소스코드 부터 살펴보자.
 

// lexer/lexer.go

package lexer

type Lexer struct {
	input        string
	position     int
	readPosition int
	ch           byte
}

func New(input string) *Lexer {
	l := &Lexer{input: input}
	return l
}

 
먼저 Lexer 라는 이름의 구조체를 정의했다. 해당 구조체가 갖는 멤버는 총 4가지인데 설명은 다음과 같다.

• input : 입력된 소스코드 문자열
• position : 입력된 소스코드 문자열에서 현재 위치
• readPosition : 입력된 소스코드 문자열에서 현재 위치의 다음 위치
• ch : 현재 렉싱하고 있는 대상 문자(문자열 아님! 에 주의. 그래서 위에서 타입을 byte로 정의함. Go언어에서 byte는 부호가 없는 8비트 즉, uint8 타입이며 나타낼 수 있는 숫자 경우의 수가 0~255이다. 우리가 만들 렉서는 ASCII 문자 범위 내에 표기되는 소스코드를 렉싱하는 것이 목표이기 때문에 rune(32비트) 타입을 사용하지 않음)

다음으로 New 라는 함수를 보자. 해당 함수는 입력된 소스코드 문자열을 그대로 받되 Lexer 라는 구조체로 만드는 역할을 한다. 단, 리턴하는 값은 구조체의 포인터 변수이다.
 
그런데 이제 우리는 이 New 함수에 한 가지 함수를 더 추가할 것이다. 소스코드부터 보자.
 

// lexer/lexer.go

func New(input string) *Lexer {
	l := &Lexer{input: input}
	l.readChar()
	return l
}

func (l *Lexer) readChar() {
	if l.readPosition >= len(l.input) {
		l.ch = 0
	} else {
		l.ch = l.input[l.readPosition]
	}
	l.position = l.readPosition
	l.readPosition += 1
}

 
Lexer 구조체의 포인터 변수를 Receiver로 하는 readChar 함수를 호출했다. 이 readChar 함수는 어떤 기능을 하는건지 보자. 이름 그대로 문자(Char)를 읽는 기능이다. if ~ else 분기문을 보자. Lexer 구조체의 readPosition 값이 소스코드 문자열보다 크거나 같다면 즉, readPosition 값이 소스코드 문자열 길이의 범위를 벗어났다면 Lexer 구조체의 렉싱 대상 문자(ch 라는 구조체 멤버)에는 0 즉, NULL을 집어넣는다. 
 
만약 그렇지 않으면 소스코드 문자열에서 렉싱할 대상의 문자를 ch 구조체 멤버에 할당한다. 그리고 렉싱할 대상의 문자 위치를 현재 처리한 렉싱 대상 문자의 다음 위치에 있는 문자로 옮기도록 한다.

2-2. 소스코드 문자열에서 토큰화 시키기

직전 목차까지는 소스코드 문자열에서 렉싱할 대상의 위치를 찾는 작업을 했다. 렉싱할 대상의 위치를 찾았으니 이제는 렉싱 대상의 문자가 어떤 토큰으로 매핑시킬지 결정해야 한다. 이번에도 소스코드를 먼저 살펴보자.
 

// lexer/lexer.go

func (l *Lexer) NextToken() token.Token {
	var tok token.Token
	
	switch l.ch {
	case '=':
		tok = newToken(token.ASSIGN, l.ch)
	case ';':
		tok = newToken(token.SEMICOLON, l.ch)
	case '(':
		tok = newToken(token.LPAREN, l.ch)
	case ')':
		tok = newToken(token.RPAREN, l.ch)
	case ',':
		tok = newToken(token.COMMA, l.ch)
	case '+':
		tok = newToken(token.PLUS, l.ch)
	case '{':
		tok = newToken(token.LBRACE, l.ch)
	case '}':
		tok = newToken(token.RBRACE, l.ch)
	case 0:
		tok.Type = token.EOF
		tok.Literal = ""
	}
	l.readChar()
	return tok
}

func newToken(tokenType token.TokenType, ch byte) token.Token {
	return token.Token{Type: tokenType, Literal: string(ch)}
}

 
먼저 newToken 이라는 함수를 보자. 해당 함수는 토큰 타입과 렉싱 대상 문자를 인자로 받은 뒤, token.Token 이라는 구조체로 만든 후 리턴한다. 
 
이제 NextToken 함수를 보자. 해당 함수에서는 실제 현재 렉싱 대상의 문자(ch)가 어떤 문자랑 일치하는지 보고, 그 문자랑 매핑되는 토큰으로 변환 후 토큰을 반환한다. 여기서 주목할 점은 switch-case 문이 끝난 뒤, 위에서 알아본 readChar 함수를 한 번 호출함으로써 렉싱 대상의 문자를 다음 위치로 옮기게 된다.
 
이제 위 함수까지 모두 작성했으면 위에서 살펴보았던 lexer_test.go 라는 테스트 코드 파일을 실행시켜보자. 테스트 코드 실패가 나지 않는다면 정상 통과한 것이다!

3. 조금 더 그럴듯한 소스코드를 렉싱해보자

직전 목차에서는 단순한 소스코드를 렉싱해보았다. 이번에는 정말 우리만의 프로그래밍 언어인 Monkey 언어의 문법을 렉싱할 수 있도록 렉서를 개선시켜보자. 이번에도 테스트 코드를 먼저 살펴보자. 직전에 보았던 테스트 코드에서 inputs 와 tests 변수만 달라졌다.
 

// lexer/lexer_test.go

func TestNextToken(t *testing.T) {
	input := `let five = 5;
let ten = 10;

let add = fn(x, y) {
 x + y;
};
let result = add(five, ten);`

	tests := []struct {
		expectedType    token.TokenType
		expectedLiteral string
	}{
		{token.LET, "let"},
		{token.IDENT, "five"},
		{token.ASSIGN, "="},
		{token.INT, "5"},
		{token.SEMICOLON, ";"},
		{token.LET, "let"},
		{token.IDENT, "ten"},
		{token.ASSIGN, "="},
		{token.INT, "10"},
		{token.SEMICOLON, ";"},
		{token.LET, "let"},
		{token.IDENT, "add"},
		{token.ASSIGN, "="},
		{token.FUNCTION, "fn"},
		{token.LPAREN, "("},
		{token.IDENT, "x"},
		{token.COMMA, ","},
		{token.IDENT, "y"},
		{token.RPAREN, ")"},
		{token.LBRACE, "{"},
		{token.IDENT, "x"},
		{token.PLUS, "+"},
		{token.IDENT, "y"},
		{token.SEMICOLON, ";"},
		{token.RBRACE, "}"},
		{token.SEMICOLON, ";"},
		{token.LET, "let"},
		{token.IDENT, "result"},
		{token.ASSIGN, "="},
		{token.IDENT, "add"},
		{token.LPAREN, "("},
		{token.IDENT, "five"},
		{token.COMMA, ","},
		{token.IDENT, "ten"},
		{token.RPAREN, ")"},
		{token.SEMICOLON, ";"},
		{token.EOF, ""},
	}

	src := New(input)

	for i, tt := range tests {
		tok := src.NextToken()
		if tok.Type != tt.expectedType {
			t.Fatalf("tests[%d] - tokentype wrong. expected=%q, got=%q",
				i, tt.expectedType, tok.Type)
		}
		if tok.Literal != tt.expectedLiteral {
			t.Fatalf("tests[%d] - literal wrong. expected=%q, got=%q",
				i, tt.expectedLiteral, tok.Literal)
		}
	}
}

 
inputs에 있는 소스코드 문자열을 보니, 정말 꽤나 실제 프로그래밍 언어답다! 이 inputs 문자열에 맞게 tests 변수에도 미리 정해진 정답 토큰을 추가해두도록 하자.
 
이번에는 직전에 만든 렉서 기능으로 렉싱하기에는 한계점이 있다. 바로 식별자, 예약어, 숫자이다. 식별자는 크게 사용자 정의 식별자(일명 변수 같은..)와 예약어로 구성된다. 사용자 정의 식별자라 함은 위 소스코드에서 five, ten, add 와 같은 것들이다. 예약어는 이건 변수라는 것을 의미하는 let 또는 이건 함수라는 것을 의미하는 fn 같은 것이 된다. 마지막으로 숫자는 5와 10이라는 것들인데, 렉싱에서는 사실 이것이 숫자라는 것만 인지하면 된다. 이 값이 5인지 1인지 2인지는 렉싱이 신경쓸 역할은 아니기 때문이다.
 
이제 개선된 렉서의 기능을 하나씩 추가해보자.

3-1. 사용자 정의 식별자, 예약어, 숫자를 구분하기

렉서는 사용자 정의 식별자, 예약어, 숫자를 잘 구분해서 입력된 소스코드 문자열을 잘 렉싱해야 한다. 이를 위해 NextToken 함수를 개선해야 한다. 먼저 개선된 NextToken 함수를 살펴보자.
 

// lexer/lexer.go

func (l *Lexer) NextToken() token.Token {
	var tok token.Token

	switch l.ch {
	case '=':
		tok = newToken(token.ASSIGN, l.ch)
	case ';':
		tok = newToken(token.SEMICOLON, l.ch)
	case '(':
		tok = newToken(token.LPAREN, l.ch)
	case ')':
		tok = newToken(token.RPAREN, l.ch)
	case ',':
		tok = newToken(token.COMMA, l.ch)
	case '+':
		tok = newToken(token.PLUS, l.ch)
	case '{':
		tok = newToken(token.LBRACE, l.ch)
	case '}':
		tok = newToken(token.RBRACE, l.ch)
	case 0:
		tok.Type = token.EOF
		tok.Literal = ""
	default:
		if isLetter(l.ch) {
			tok.Literal = l.readIdentifier()
			tok.Type = token.LookupIdent(tok.Literal)
			return tok
		} else {
			tok = newToken(token.ILLEGAL, l.ch)
		}
	}
	l.readChar()
	return tok

 
수정된 부분은 default 부분이다. default 구문을 위 case 구문에 어떤 것도 분기되지 않았을 경우 타게 되는 구문이다. 먼저 isLetter 함수가 등장한다. 이 isLetter 함수는 어떤 기능을 하는지 살펴보자.
 

// lexer/lexer.go

func isLetter(ch byte) bool {
	return 'a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z' || ch == '_'
}

 
간단하다. 바이트 타입의 문자를 받아서 해당 문자가 알파벳 a ~ z 또는 A ~ Z 또는 언더스코어(_)인 경우에만 true를 반환한다. 그런데 여기서 함수 기능보다는 이 isLetter 함수가 왜 존재해야 하는지를 이해하는 것이 더 중요하다. 우선 '문자' 라는 것에는 '글자'가 포함되어 있다. 쉽게 말해 벤다이어 그램으로 표시하면 문자와 글자간의 관계는 다음과 같다.
 

 
그러면 이 문자 중에 '글자' 인 것과 '글자가 아닌 문자'를 대체 왜 구분해야 할까? 바로 식별자를 구분하기 위함이다. 예를 들어, 우리가 처음 예시에서 입력 소스코드로 보았던 =+(){},; 이런 것들도 '문자'이다. 그리고 add, five, ten 과 같은 것들도 '문자'가 모여 문자열을 형성한 것이다. 하지만, =+(){},; 이런 것들은 '글자가 아닌 문자'이다. 반면에 add, five, ten 같은 것들은 '글자'이다. 즉, 이 두개를 구분하기 위해서 우리는 특정 문자가 '글자'인지, 혹은 '글자가 아닌 문자'인지 판별해야 한다. 그리고 이러한 판별을 수행하는 것이 바로 isLetter 함수이다.
 
이제 다음으로 넘어가보자. 다음으로 볼 함수는 Lexer 구조체 포인터 변수를 Receiver 로하는 메소드인 readIdentifier 함수이다. 해당 함수의 소스코드 부터 살펴보자.
 

// lexer/lexer.go

func (l *Lexer) readIdentifier() string {
	position := l.position
	for isLetter(l.ch) {
		l.readChar()
	}
	return l.input[position:l.position]
}

 
함수 이름에서 알 수 있듯이 이 함수는 렉싱 대상 문자열(입력된 소스코드 문자열)에서 '식별자'를 추출해내는 함수이다. 따라서 렉싱 대상 문자열의 현재 위치를 시작점으로 해서 해당 위치에 있는 문자가 '글자'라면 무한 루프를 타게한다. 그리고 그 무한루프 안에서는 렉싱 대상 문자열의 현재 위치에서 다음 위치로 이동시키는 readChar 함수를 호출하도록 한다. 이렇게 루프를 돌다가 '글자가 아닌 문자'가 나오게 되면 루프를 빠져나와 '글자가 아닌 문자'의 직전 위치까지의 문자열을 슬라이싱해서 리턴한다.
 
그리고 마지막으로 token.LookupIdent 함수를 살펴보자. 해당 함수는 식별자 중에서도 이것이 사용자 정의 식별자(IDENT)인지, 예약어인지 분기하는 기능을 하는 함수다. 해당 함수의 소스코드를 보자.
 

// token/token.go

var keywords = map[string]TokenType{
	"fn":  FUNCTION,
	"let": LET,
}

func LookupIdent(ident string) TokenType {
	if tok, ok := keywords[ident]; ok {
		return tok
	}
	return IDENT
}

 
우선 가장 먼저 할 일은 keywords 라는 맵 자료구조를 정의했다. 해당 맵은 소스코드 문자열에서 추출한 식별자가 예약어에 해당하는지 매핑해놓은 테이블이다. 즉, 룩업 테이블인 셈이다. 추후에 확장하겠지만 앞으로 우리가 렉싱 대상에 어떤 예약어를 포함시키고 싶다고 하면 해당 맵 자료구조에 계속 추가해나가면 된다.
 
이제 LookupIdent 함수를 보자. 로직은 간단하다. 문자열을 입력 받은 뒤 해당 문자열이 keywords 맵 자료구조의 키 값에 존재하는지 즉, 우리가 사전에 명시해놓은 예약어 목록에 포함되는지 여부를 판단하는 것이다. 해당 분기를 타지 않으면 그것은 사용자 정의 식별자로 간주해 리턴한다.
 
그리고 마지막으로 default 구문 내의 else 구문이 존재하는 것은 case 구문에서 '글자가 아닌 문자'에 대해서는 분기를 다 했으므로, 만약 해당 else 구문으로 타는 문자는 우리가 만든 렉서가 처리할 수 없는 문자임을 즉, 예외처리를 하기 위해 ILLEGAL 이라는 토큰을 사용했다. 해당 토큰이 반환되면 우리의 렉서에 대한 테스트가 실패했다고 보면 된다.

3-2. 공백과 숫자임을 구분하기

다음으로 개선할 부분은 렉싱 대상 문자열에 공백이 있거나 숫자로 된 문자열(ex. 5, 10)이 있을 경우 숫자라는 토큰으로 인지하도록 개선해야 한다. 먼저 공백이 있을 경우 처리하기 위해 아래의 소스코드를 추가해보자.
 

// lexer/lexer.go

func (l *Lexer) skipWhitespace() {
	for l.ch == ' ' || l.ch == '\t' || l.ch == '\n' || l.ch == '\r' {
		l.readChar()
	}
}

 
이 함수 로직도 간단하다. 현재 렉싱 대상 문자가 공백이거나 탭 문자, 공백 문자, 그리고 커서를 앞으로 옮기는 문자(\r)라면 다음 위치로 렉싱 대상을 옮기는 것이다.
 
그리고 숫자인지를 구분하는 함수의 소스코드도 살펴보자.
 

// lexer/lexer.go

func (l *Lexer) readNumber() string {
	position := l.position
	for isDigit(l.ch) {
		l.readChar()
	}
	return l.input[position:l.position]
}

func isDigit(ch byte) bool {
	return '0' <= ch && ch <= '9'
}

 
isDigit 함수는 간단하니 별다른 설명은 하지 않겠다. readNumber 함수도 사실 위에서 살펴본 식별자를 추출하는 함수인 readIdentifier 함수와 로직은 동일하다. 단순히 조건문 분기에 isDigit 함수를 사용한 것으로 바뀌었을 뿐이다.
 
이제 위 2가지 함수를 NextToken 함수에 추가해주면 다음과 같아진다.
 

// lexer/lexer.go

func (l *Lexer) NextToken() token.Token {
	var tok token.Token

	switch l.ch {
	case '=':
		tok = newToken(token.ASSIGN, l.ch)
	case ';':
		tok = newToken(token.SEMICOLON, l.ch)
	case '(':
		tok = newToken(token.LPAREN, l.ch)
	case ')':
		tok = newToken(token.RPAREN, l.ch)
	case ',':
		tok = newToken(token.COMMA, l.ch)
	case '+':
		tok = newToken(token.PLUS, l.ch)
	case '{':
		tok = newToken(token.LBRACE, l.ch)
	case '}':
		tok = newToken(token.RBRACE, l.ch)
	case 0:
		tok.Type = token.EOF
		tok.Literal = ""
	default:
		if isLetter(l.ch) {
			tok.Literal = l.readIdentifier()
			tok.Type = token.LookupIdent(tok.Literal)
			return tok
		} else if isDigit(l.ch) {
			tok.Literal = l.readNumber()
			tok.Type = token.INT
			return tok
		} else {
			tok = newToken(token.ILLEGAL, l.ch)
		}
	}
	l.readChar()
	return tok
}

 
이제 위처럼 코드를 작성하고 테스트 코드를 수행하면 그럴듯한 Monkey 프로그래밍 언어로 작성된 소스코드가 잘 렉싱될 것이다!

3-3. 두개 짜리 문자와 다른 종류의 예약어도 렉싱하기

이번엔 [목차 3-2]에서 테스트 코드에서 수행했던 것보다 좀 더 다양한 예약어가 추가된 Monkey 언어 소스코드를 렉싱해보자. 이번에도 테스트 코드부터 살펴보도록 하자.

 

// lexer/lexer_test.go

func TestNextToken(t *testing.T) {
	input := `let five = 5;
let ten = 10;

let add = fn(x, y) {
 x + y;
};
let result = add(five, ten);
!-/*5;
5 < 10 > 5;
if (5 < 10) {
  return true;
} else {
  return false;
}

10 == 10;
10 != 9;
`

	tests := []struct {
		expectedType    token.TokenType
		expectedLiteral string
	}{
		{token.LET, "let"},
		{token.IDENT, "five"},
		{token.ASSIGN, "="},
		{token.INT, "5"},
		{token.SEMICOLON, ";"},
		{token.LET, "let"},
		{token.IDENT, "ten"},
		{token.ASSIGN, "="},
		{token.INT, "10"},
		{token.SEMICOLON, ";"},
		{token.LET, "let"},
		{token.IDENT, "add"},
		{token.ASSIGN, "="},
		{token.FUNCTION, "fn"},
		{token.LPAREN, "("},
		{token.IDENT, "x"},
		{token.COMMA, ","},
		{token.IDENT, "y"},
		{token.RPAREN, ")"},
		{token.LBRACE, "{"},
		{token.IDENT, "x"},
		{token.PLUS, "+"},
		{token.IDENT, "y"},
		{token.SEMICOLON, ";"},
		{token.RBRACE, "}"},
		{token.SEMICOLON, ";"},
		{token.LET, "let"},
		{token.IDENT, "result"},
		{token.ASSIGN, "="},
		{token.IDENT, "add"},
		{token.LPAREN, "("},
		{token.IDENT, "five"},
		{token.COMMA, ","},
		{token.IDENT, "ten"},
		{token.RPAREN, ")"},
		{token.SEMICOLON, ";"},
		{token.BANG, "!"},
		{token.MINUS, "-"},
		{token.SLASH, "/"},
		{token.ASTERISK, "*"},
		{token.INT, "5"},
		{token.SEMICOLON, ";"},
		{token.INT, "5"},
		{token.LT, "<"},
		{token.INT, "10"},
		{token.GT, ">"},
		{token.INT, "5"},
		{token.SEMICOLON, ";"},
		{token.IF, "if"},
		{token.LPAREN, "("},
		{token.INT, "5"},
		{token.LT, "<"},
		{token.INT, "10"},
		{token.RPAREN, ")"},
		{token.LBRACE, "{"},
		{token.RETURN, "return"},
		{token.TRUE, "true"},
		{token.SEMICOLON, ";"},
		{token.RBRACE, "}"},
		{token.ELSE, "else"},
		{token.LBRACE, "{"},
		{token.RETURN, "return"},
		{token.FALSE, "false"},
		{token.SEMICOLON, ";"},
		{token.RBRACE, "}"},
		{token.INT, "10"},
		{token.EQ, "=="},
		{token.INT, "10"},
		{token.SEMICOLON, ";"},
		{token.INT, "10"},
		{token.NOT_EQ, "!="},
		{token.INT, "9"},
		{token.SEMICOLON, ";"},
		{token.EOF, ""},
	}

	src := New(input)

	for i, tt := range tests {
		tok := src.NextToken()
		if tok.Type != tt.expectedType {
			t.Fatalf("tests[%d] - tokentype wrong. expected=%q, got=%q",
				i, tt.expectedType, tok.Type)
		}
		if tok.Literal != tt.expectedLiteral {
			t.Fatalf("tests[%d] - literal wrong. expected=%q, got=%q",
				i, tt.expectedLiteral, tok.Literal)
		}
	}
}

 

입력으로 주어지는 소스코드 문자열을 보니, 크게 추가된 것들은 !-/*<> 그리고 !=, == 라는 2개짜리 문자와 if, else, return 같은 다른 종류의 예약어이다. 여기서 소스코드 문자열 중 아래와 같은 부분이 보인다.

 

!-/*5;
5 < 10 > 5;

 

물론 아무리 우리만의 프로그래밍 언어인 Monkey 라고 해도 사실 이게 문법적으로는 맞지 않는다. 하지만 이 테스트에서 이런 소스코드 문자열을 입력한 것은 렉서의 역할이 "그저 입력된 소스코드 문자열을 토큰화 하는 것일 뿐"을 강조하기 위해서다. 다시 말해, 렉서는 소스코드 문자열을 토큰화하는 것만 신경쓰면 된다. 그 소스코드 문자열이 문법적으로 맞는지, 맞지 않는지는 그 이후에 판별하면 된다.

 

먼저 !-/*<> 와 같은 1개짜리 문자로 된 것을 렉싱하기 위해서 우리는 가장 먼저 해당 문자를 토큰에 추가해준다. 그리고 if, else, return 과 같이 새롭게 추가된 예약어에 대해서는 토큰 뿐만 아니라 어떤 글자가 어떤 예약어로 매핑되는지 룩업 테이블인 keywords 변수에다가도 추가해주자.

 

// token/token.go

const (
	ILLEGAL = "ILLEGAL"
	EOF     = "EOF"

	// Identifiers + literals
	IDENT = "IDENT" // add, result, x, y, ...
	INT   = "INT"   // 1343456

	// Operators
	ASSIGN   = "="
	PLUS     = "+"
	MINUS    = "-"
	BANG     = "!"
	ASTERISK = "*"
	SLASH    = "/"

	LT = "<"
	GT = ">"
	// Delimiters
	COMMA     = ","
	SEMICOLON = ";"

	LPAREN = "("
	RPAREN = ")"
	LBRACE = "{"
	RBRACE = "}"

	// 예약어
	FUNCTION = "FUNCTION"
	LET      = "LET"
	TRUE     = "TRUE"
	FALSE    = "FALSE"
	IF       = "IF"
	ELSE     = "ELSE"
	RETURN   = "RETURN"
)

var keywords = map[string]TokenType{
	"fn":  FUNCTION,
	"let": LET,
	"true": TRUE,
	"false": FALSE,
	"if":   IF,
	"else": ELSE,
	"return": RETURN,
}

 

그리고 이제 렉싱할 대상 문자가 어떤 토큰인지 확인하고 그에 맞는 토큰을 생성하는 NextToken 함수의 switch-case 구문에 방금 추가한 문자들을 반영해보자. 참고로 새롭게 추가된 예약어의 경우는 기존 NextToken 함수의 default 구문을 그대로 이용하면 된다.

 

// lexer/lexer.go

func (l *Lexer) NextToken() token.Token {
	var tok token.Token

	switch l.ch {
	case '=':
		tok = newToken(token.ASSIGN, l.ch)
	case ';':
		tok = newToken(token.SEMICOLON, l.ch)
	case '(':
		tok = newToken(token.LPAREN, l.ch)
	case ')':
		tok = newToken(token.RPAREN, l.ch)
	case ',':
		tok = newToken(token.COMMA, l.ch)
	case '+':
		tok = newToken(token.PLUS, l.ch)
	case '-':
		tok = newToken(token.MINUS, l.ch)
	case '!':
		tok = newToken(token.BANG, l.ch)
	case '*':
		tok = newToken(token.ASTERISK, l.ch)
	case '/':
		tok = newToken(token.SLASH, l.ch)
	case '<':
		tok = newToken(token.LT, l.ch)
	case '>':
		tok = newToken(token.GT, l.ch)
	case '{':
		tok = newToken(token.LBRACE, l.ch)
	case '}':
		tok = newToken(token.RBRACE, l.ch)
	case 0:
		tok.Type = token.EOF
		tok.Literal = ""
	default:
		if isLetter(l.ch) {
			tok.Literal = l.readIdentifier()
			tok.Type = token.LookupIdent(tok.Literal)
			return tok
		} else if isDigit(l.ch) {
			tok.Literal = l.readNumber()
			tok.Type = token.INT
			return tok
		} else {
			tok = newToken(token.ILLEGAL, l.ch)
		}
	}
	l.readChar()
	return tok

 

하지만 위 상태에서의 렉서는 아직 극복하지 못하는 점이 있다. 바로 두 개의 글자가 아닌 문자로 구성된, 예를 들어 != 나 == 와 같은 연산자에 대한 토큰화이다.(또 다른 예시로 <= >= ++, -- 이런 것들이 있다. 하지만 해당 책에서는 이런 연산자들에 대한 렉싱은 다루지 않는다)

 

우리는 이 2개 문자로 이루어진 연산자를 어떻게 토큰화시킬 수 있을까? 우선 우리가 확인하려고는 '2개 문자'가 맞는지 확인하는 함수가 필요하다. 즉, 만약 렉싱 대상의 문자가 = 로 등장했다고 해보자. 이 = 문자 다음에 또 문자 = 가 나오는지를 살펴보아야 한다. 이를 확인하기 위한 peekChar 함수를 먼저 살펴보자.

 

// lexer/lexer.go

func (l *Lexer) peekChar() byte {
	if l.readPosition >= len(l.input) {
		return 0
	} else {
		return l.input[l.readPosition]
	}
}

 

해당 함수의 로직 자체는 간단하다. 단순히 현재 렉싱 대상 문자의 다음 위치에 있는 문자를 반환하는 것이다. 이제 위 함수를 NextToken 함수에 반영해보도록 하자. 우리가 고려하는 2개 문자는 == 또는 != 이기 때문에 switch-case 구문에서 = 또는 ! 문자가 나왔을 때의 부분에 반영해주면 된다.

 

// lexer/lexer.go

func (l *Lexer) NextToken() token.Token {
	var tok token.Token

	switch l.ch {
	case '=':
		if l.peekChar() == '=' {
			ch := l.ch
			l.readChar()
			literal := string(ch) + string(l.ch)
			tok = token.Token{Type: token.EQ, Literal: literal}
		} else {
			tok = newToken(token.ASSIGN, l.ch)
		}
        
	...(생략)...
    
	case '!':
		if l.peekChar() == '=' {
			ch := l.ch
			l.readChar()
			literal := string(ch) + string(l.ch)
			tok = token.Token{Type: token.NOT_EQ, Literal: literal}
		} else {
			tok = newToken(token.BANG, l.ch)
		}
        
	...(생략)...
    
	l.readChar()
	return tok
}

 

이제 마지막으로, == 와 != 라는 토큰이 존재한다는 것을 아래와 같이 상수값에 추가해주자.

 

// token/token.go

const (
	...(생략)...
    
	ASTERISK = "*"
	SLASH    = "/"
	EQ       = "=="
	NOT_EQ   = "!="

	...(생략)...
    
	ELSE     = "ELSE"
	RETURN   = "RETURN"
)

4. 렉서에 대한 REPL 만들기

3번 목차까지 해서 우리만의 렉서를 만들었다! 이제는 우리가 만든 렉서를 테스트하기 위해 좀 더 사용자 친화적인 REPL(Read, Eval, Print, Loop)을 만들어보자. REPL은 콘솔 또는 대화형 모드라고 이야기한다. 파이썬 언어가 익숙한 사람들은 터미널에 python 명령어를 입력하면 들어가게 되는 대화형 모드랑 똑같다고 생각하면 된다.

 

REPL을 만드는 코드는 우리가 구체적인 로직을 작성하는 것은 거의 없고, 패키지를 가져다 쓰거나 예외처리하는 로직이 전부다. 따라서 코드만 첨부하고 글을 마무리하려고 한다.

 

먼저 repl 패키지를 생성해서 아래의 소스코드를 입력하자.

 

// repl/repl.go

package repl

import (
	"bufio"
	"fmt"
	"io"
	"monkey/lexer"
	"monkey/token"
)

const PROMPT = ">> "

func Start(in io.Reader, out io.Writer) {
	scanner := bufio.NewScanner(in)

	for {
		fmt.Fprintf(out, PROMPT)
		scanned := scanner.Scan()
		if !scanned {
			return
		}
		line := scanner.Text()
		l := lexer.New(line)

		for tok := l.NextToken(); tok.Type != token.EOF; tok = l.NextToken() {
			fmt.Fprintf(out, "%+v\n", tok)
		}
	}
}

 

그리고 이제 사용자의 엔트리포인트인 main 패키지를 만들고, main 함수를 작성해보자.

 

// main.go

package main

import (
	"fmt"
	"monkey/repl"
	"os"
	"os/user"
)

func main() {
	user, err := user.Current()
	if err != nil {
		panic(err)
	}
	fmt.Printf("Hello, %s!\n", user.Username)
	fmt.Printf("Feel free to type in commands\n")
	repl.Start(os.Stdin, os.Stdout)
}

 

그리고 위 스크립트를 현재 경로로 두고, go run 명령어를 수행해보자. 우리만의 렉서에 대해서 대화형 모드로 테스트를 수행할 수 있게 되었다!

---

이제 다음 포스팅에서는 이번 포스팅에서 만든 렉서가 토큰화시킨 토큰들을 추상구문트리로 만드는 파싱(Parsing)을 해볼 차례다.