이 시리즈는 go언어로 인터프리터를 만드는 과정을 소개한다. 밑바닥부터 만드는 인터프리터 in Go를 참고하였으며, 말그대로 인터프리터를 밑바닥부터 만드는 과정을 보여주며, 완성되는대로 공백 단순 무시+세미콜론이 있는 c스타일 인터프리터 언어, 이후에 go로 만드는 파이썬 스타일 인터프리터를 깃허브에 올릴 생각이다. 현재 글은 c스타일에 가까운 인터프리터 언어를 만드는 과정이며, 파이썬 스타일에서는 공백 처리 등의 전처리가 다르고, 실제 사용 언어와 같이 만들고자 한다면 더욱 섬세한 처리가 필요하다.
Lexing
- 렉싱 <lexing> : 소스코드를 토큰 열로 변환하는 것
- 위와 같은 과정을 lexer라고 하는 녀석이 수행한다. 이 친구는 토크나이저 또는 스캐너로도 불림
인터프리터는 소스코드->토큰 으로 변환된 이후 토큰을 추상구문트리 <Abstract Syntax Tree> 로 바꾸는 2차 변환 작업이 일어난다.
예를 들면,
let x = 5 + 5
와 같은 소스코드는
[
LET,
IDENTIFIER(“x”)
EQUAL_SIGN,
INTEGER,
PLUS_SIGN,
INTEGER(5),
SEMICOLON
]
과 같이 변환한다. 앞서 말한대로, 이러한 과정은 렉서가 수행한다.
토큰을 어떻게 구성할지는 렉서의 구현에 따라 다르다. 공백의 길이를 처리하거나 크게 영향을 갖지 않을 수도 있다. 예컨대 공백을 단순한 구분자로만 쓴다면
let x = 5 + 5
도 똑같이 처리될 것이란 말이다.
그러나 파이썬과 같은 언어에서는 공백의 길이가 중요하게 작동한다. 알다시피 중괄호 대신 블럭 형태, 즉 공백이 무의미한 구분자가 아니라 중괄호같은 역할을 하기 때문에 그냥 공백을 일괄적으로 처리해버리면 안된다는 뜻이다.
여담이지만 나는 이러한 블럭 형태의 구분을 별로 좋아하지 않는다
토큰 정의하기
그러면 인터프리터의 첫 단계인 렉싱을 수행하기 위해 우리가 가장 먼저 해야할 일은 토큰 정의하기이다. 아래 코드를 보면서 어떤 식으로 토큰을 정의해야할지 생각해보자.
let five = 5;
let ten = 10;
let add = fn(x, y) {
x + y;
}
let result = add(five, ten);
어떤 토큰이 필요할까?
직관적으로는
- 숫자 토큰
- 변수명 x, y, result ...
- 변수가 아닌 문자열: fn, let
- 특수 문자: 괄호 등
를 들어볼 수 있겠다.
사실 토큰화하는 과정에서 ’값‘은 신경 쓸 필요가 없다. 렉서가 할 일은 저게 뭔지 구분해서 쪼개놓을 뿐이지, 사실 저게 5냐 10이냐는 전혀 알 바가 아니라는 거다. 토큰화는 그저 쪼갤 뿐이므로, 5와 10은 어차피 같은 방식으로 처리되기 때문이다.
다른 것도 마찬가지로, 렉서는 저 문자열이 ‘변수명’인지를 고려하지 변수명이 무엇인지는 중요하지 않다. 여러분이 a, b와 같은 알아보기 힘든 변수명을 써서 상사나 교수님한테 혼나더라도, 우리 착한 렉서는 그런 건 아무 신경 쓰지 않는다.
이러한 변수명은 식별자(identifier) 라는 명칭으로 그저 통일되어 구분된다.
그런데 일괄적으로 처리되지 않아야할, 그러니까 식별자가 아닌 문자열도 있지 않은가?
바로 let, fn, 뭐 다른 언어에선 def같은 이런 특수한 문자열들 말이다. 이것들은 식별자와 기능적으로 구분되어야하기 때문이다. 이런 문자열들은 언어 의 일부이다. 따라서 우리는 이것들을 예약어(keywords) 라고 부른다.
추가적으로 특수 문자에 대한 처리가 필요할 수 있겠다. 특수 문자는 기능적으로 함수의 적용 범위 등을 규정할 수 있으므로 또 하나의 기능적으로 다른 친구이다. 또한 소스코드에 괄호의 여부에 따라 처리 과정이 크게 달라지곤 한다고 한다. 중요한 것은 이놈을 별도로 처리하자는 것.
토큰 자료구조 정의하기
그럼 이제 토큰의 자료구조를 정의할 수 있겠다.
이젠 뭐가 필요한가?
토큰은 ‘타입’ 속성이 필요하다. 그래야 정수와 특수 문자, 이런 것들의 구분이 가능하다.
더해, 토큰은 토큰 자체의 문자값(리터럴) 을 가질 필드가 필요하다. 소스코드 자체를 쪼갤 때는 5인지 10인지가 중요하지 않지만, 이후 과정에서는 쓰여야한다. 이러한 필드가 있어야 값을 잃어버리지 않는다.
package token
type TokenType string //토큰의 타입을 필요한만큼 정의해서 쓸 수가 있다!
//성능이 중요하다면 알아서 int, byte쓸 것…
type Token Struct {
Type TokenType
Literal string
}
타입 과 리터럴 필드가 필요하다고 했으니 저런 식으로 구현하면 되겠다.
그렇다면 좀 더 나아가 아래 코드를 추가할 수 있겠다.
const (
ILLEGAL = “ILLEGAL” //어떤 토큰이나 문자를 렉서가 알 수 없음
EOF = “EOF” //파일의 끝
//식별자, 리터럴
IDENT = “IDENT”
INT = “INT”
//연산자
ASSIGN = “,”
PLUS = “+”
//구분자
COMMA = “,”
SEMICOLON = “;”
LPAREN = “(“
RPAREN = “)”
LBRACE = “{“
RBRACE = “}”
//예약어
FUNCTION = “FUNCTION”
LET = “LET”
)
다른 것들은 그렇다치고, EOF와 ILLEGAL은 뭐 하는 놈들인가?
뭐 코멘트에도 달려있다만
- ILLEGAL: 알 수 없는 토큰이나 문자
- EOF: end of file이라는 뜻인데, 나중에 파서에게 여기가 끝이니 멈춰라- 할 때 쓰인다.
어느정도 토큰을 정의하였다. 당연하지만 실제 인터프리터 언어로 쓰일 정도면 이보다 훨씬 확장되어야한다—그러나 여기서는 이만 멈추고, 렉서를 작성해보자.
렉서
이제 렉서를 작성할 차례다.
렉서가 뭐 하는 놈이던가? 이 녀석은 소스코드를 입력으로 받고, 소스코드를 토큰 열로 쪼갠 다음 이를 뱉어낼 것이다. 그런데 이 렉서는 버퍼도 필요 없고 토큰을 저장할 공간을 따로 만들지 않아도 된다.
이건 소스코드를 보고 토큰으로 쪼갤 때마다 그 토큰을 바로바로 뱉어내기 때문에, 렉서 안에 저장 공간이 있을 필요는 없다. 대신 나중에 뱉은 것을 다른 친구가 잘 주워담야겠지..그게 이따 볼 NextToken이라는 친구인데, 일단 넘어가자.
따라서 렉서를 초기화할 때 소스코드를 인자로 전달하고, 초기화 이후에 NextToken을 호출하면서 소스코드를 토큰 단위->문자 단위로 훑는 작업을 할 것이다.
여기서는 그냥 string타입으로 다룰 거지만, 실제 작업 시에는 파일 이름, 행 번호도 추가하여 작업해야한다. 이런 식의 간단한 작업은 에러 처리에서 매우 불리하다..
그러나, 인터프리터 구조 살펴보기라면 이 정도로도 충분하다.
//lexer_test.go
package lexer
import (
“testing”
“lang/token” //이건 참고 책에서는 monkey라고 하는데, 그냥 만들 언어의 이름인것이다
)
func TestNextToken(t *testing, T) {
input := ‘=+(){},;’
tests := []struct {
expectedType token.TokenType
expectedLiteral string
} {
{token.ASSIGN, “=“},
{token.PLUS, “+”},
{token.LPAREN, “(“},
{token.RPREN, “)”},
{token.COMMA, “,”},
{token.SEMICOLON, “;”},
{token.EOF, “”},
}
l := New(input)
for i, tt := range tests {
tok := l.NextToken()
if tok.Type != tt.expectedType {
t.Fatal(“tests[%d] - tokentype wrong, expeced=%q, got=%q”,
i, tt.expectedType, tok.Type)
}
if tok.Literal != tt.expectedLiteral {
t.Fatal(“tests[%d] - literal wrong. expected=%q, got=%q”,
i, tt.expectedLiteral, tok.Literal)
}
}
}
와 같이 야심차게 작성한 후 실행하면! 당연히 실패한다. 이유는 코드가 없으므로.
아래는 *Lexer를 반환하는 New 함수이다.
//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 구조체는 input, position, readPosition, ch로 되어있는데, 이 중 input은 그냥 들어온 입력, 즉 소스코드일 것이고, 나머지 세 개가 무엇인가 하면. 사실 주석에 전부 있긴 하다.
그렇지만 조금 헷갈릴 수 있는 부분이 position과 readPositio의 차이 정도일 것이다.
둘 다 시점은 현재인데, 현재 위치 와 현재 읽는 위치는 뭐가 다른 것인가?
둘 모두 입력 문자열의 문자에 인덱스로 접근하기 위해 사용되는데, 둘 모두 사용되는 이유는 다음 문자를 미리 살펴봄과 동시에 현재 문자를 보존해야하기 때문이다. 그러므로,
- readPosition: 다음 문자를 가리킴
- position: 현재 문자를 가리킴
그렇다. 현재 읽음 이라는 것의 의미는 다음 인덱스에 있는 문자를 미리 살펴본다는 것이다.
헬퍼 메서드
readChar
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
}
readChar 메서드는 다음 문자에 접근할 수 있도록 만들어준다.
하나하나 쪼개서 보자면
if l.readPosition >= len(l.input()) {
l.ch = 0
}
문자열 input의 끝에 도달했는지 확인한다. 만약 끝이라면 l.ch에 0을 넣게 되는데,
0은 ‘아직 아무것도 읽지 않은 상태’ 혹은 ‘EOF’(파일의 끝)을 의미한다.
else {
l.ch = l.input[l.readPosition]
}
만약 input문자열의 끝에 도달하지 못했다면, l.readPosition을 통해 l.ch에 다음 문자를 저장한다.
l.position = l.readPosition
l.readPosition += 1
아까 position은 실제 현재 위치 readPosition은 다음 문자라고 말했다. 따라서 위치를 업데이트하기 위해 미리 살펴본 문자의 위치로 position을 다시 세팅해주고, readPosition은 1 늘려주면 된다.
아까 코드가 없어서 New함수가 작동하지 않는다고 했다. 인풋(소스코드드가 들어와야하는데, 그것을 읽을 수 있지 않기 때문이다. 그래서 readChar를 써주면 인풋에서의 문제점은 사라진다.
func New(input string) {
l := &Lexer{input: input}
l.readChar()
return l
}
리마인드하자면 우리가 해야할 것은
- 소스코드를 인자로 전달하고
- NextToken을 호출하여 토큰 단위->문자 단위로 훑는다-
이 중에 1번이 readChar를 통해 해결되었다.
NextToken
위의 과정에서 NextToken이 없었으므로, 이것을 만들 것이다.
package lexer
import “lang/token”
func (l *Lexer) NextToken() token.Token {
var tok token.Token
swtich 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.Literal = “”
tok.Type = token.EOF
}
l.readChar()
return tok
}
func newToken(tokenType token.Tokentype, ch byte) token.Token {
return token.Token{Type: tokentype, Literal: string(ch)}
}
위 코드가 NextToken 메서드의 기본 구조이다.
현재 검사하고 있는 문자 l.ch를 보고 이에 대응하는 토큰을 반환한다. 토큰을 반환하기 전에 입력 문자열의 인덱스인 position과 readPosition을 증가시킨다.
테스트 케이스를 확장해서,
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.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”},
// …
}
}
뭐가 엄청 많다…
위와 같이 성공적으로 토큰화할 수도 있지만 문제가 될 수 있는 상황이 있다.
만약 순서가 식별자(identifier)-예약어(keywords)-숫자의 형태라면 정확한 토큰화에 실패하게 된다. 왜냐하면 현재 로직은 글자인 문자, 글자가 아닌 문자로 구분하여 글자가 아닌 문자까지 도달할 때까지 이를 한 번에 읽어버리게 되는데,
예약어들은 지정되어있으므로 이것들이 먼저 있으면 처음-끝을 파악 가능하지만 식별자-예약어가 되면 예약어의 문자열이 식별자로 들어가게 될 수 있다. 식별자+예약어, 숫자로 읽어들이게 될 수 있는 것이다.
그렇다면 이것을 읽어낸 후 구분할 필요가 있다는 것이다.
import “lang/token”
func (l *Lexer) NextToken() token.Token {
var tok token.Token
switch l.ch {
// defualt분기: 앞선 분기문에서 처리되지 않은 문자일때 식별자로 처리
default:
// 글자일 때
if isLetter(l.ch) {
// readIdentifier를 호출하여 현재 토큰의 Literal필드를 채움
tok.Literal = l.readIdentifier()
return tok
} else {
//처리되지 않은 문자, 즉 ILLEGAL
tok = newToken(token.ILLEGAL, l.ch)
}
}
}
// 식별자를 하나 읽어들이고 렉서의 position과 readPosition을 글자가 아닌 문자를 만날 때까지 증가시킨다.
func (l *Lexer) readIdentifier() string {
position := l.position
for isLetter(l.ch) {
l.readChar()
}
return l.input[position:l.position]
}
// 전달받은 인자가 글자인지 아닌지 판단한다.
func isLetter(ch byte) bool {
return ‘a’ <= ch && ch <= ‘z’ || ‘A’ <= ch && ch <= ‘Z’ || ch == ‘_’ // _를 문자 처리. under_var같은 것도 변수명으로 이용 가능해졌다.
}
아, 그리고 글자인 문자라는 것은 숫자와 특수문자가 아닌 자연어?문자. 여기서는 알파벳을 말하는 것이다. char라는 자료형 자체는 1,2,3,%$^이런 것도 다 포함하고 있기에, 알파벳인지 판단하는 것.
물론 여기서는 확장 가능하기 때문에 알파벳뿐 아니라 한글 등 다양하게 확장 가능하지만 현재로서는 isalpha()와 비슷한 놈이다.
앞서 필드에는 Type, Literal가 필요하다고 밝혔다.
위 코드에서 readIdentifier를 호출하여 Literal필드를 해결하였다. 이제는 Type필드를 처리할 차례이다.
이미 let, fn과 같은 식별자는 읽어놓은 상태이므로, 토큰 리터럴에 맞는 TokenType반환 함수를 하나 정의해야한다. 사용자 정의 식별자와 예약어도 처리해야하기 때문.
var keywords = map[string]TokenType {
“fn”: FUNCTION,
“let”: LET
}
//keywords 테이블을 검사해서 주어진 식별자가 예약어인지 아닌지 살펴본다.
func LookupIdent(ident string) TokenType {
//예약어라면 예약어에 맞는 TokenType반환
if tok, ok := keywords[ident]; ok {
return tok
}
//아니라면 식별자 반환
return IDENT
}
위 과정을 통해 식별자와 예약어 렉싱이 마무리되었다.
func (l *Lexer) NextToken() token.Token {
var tok token.Token
switch l.ch
// …
default:
if isLetter(l.ch) {
tok.Literal = l.readIdentifier()
tok.Type = token.LookupIdent(tok.Literal)
//아랫줄을 통해 조기 종료하게 된다.
//switch문 이후에 readChar는 다시 호출할 필요가 없다.
return tok
} else {
tok = newToken(token.ILLEGAL, l.ch)
}
}
그러면 이대로 마무리되는가?
아니다. 공백에 대한 처리가 제대로 이루어지지 않았다.
현재 만들고자 하는 것은 공백을 그냥 토큰 구분자로 사용할 뿐, 그냥 넘어가야하는데, 현재는 그렇지 않은 것.
func (l *Lexer) NextToken() token.Token {
var tok token.Token
l.skipwhitespace()
switch l.ch {…}
}
func (l *Lexer) skipWhitespace() {
for l.ch == ‘ ‘ || l.ch == ‘\t’ || l.ch == ‘\n’ || l.ch == ‘\r’ {
l.readChar()
}
}
공백 처리 함수를 넣어주었다. 이를 적절히 수정하면 공백이 아닌 다른 문자 처리에서도 활용할 수 있다. 마참내 let five = 5;에서 숫자5를 읽을 수 있게 된 것
그럼 된 것인가?
아니다. 무언가 잊어버리지 않았는가?
우리는 식별자와 예약어를 구분할 수도 있고, 숫자 즉 글자가 아닌 문자와 글자인 문자도 구분할 수 있지만 렉서는 숫자를 토큰으로 바꾸는 법을 모른다. 그냥 추가하면 그만이다.
swtich l.ch {
//…
default:
if isLetter(l.ch) {
tok.Literal = l.readIdentifier()
tok.Type = token.LookupIdent(tok.Literal)
return tok
} else if isDigit(l.ch) {
tok.Type = token.INT
tok.Literal = l.readNumber()
return tok
} else {
tok = newToken(token.ILLEGAL, l.ch)
}
}
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’
}
간단하다. 전에 isalpha함수랑 비슷한 isLetter함수를 소개했듯 마찬가지로 isDigit을 추가하고 검사한다. 글자가 아닌 것 중 숫자인 것이 else if분기문에서 한 번 더 걸러지는것이다. 이제 숫자는 ILLEGAL이 아니다!!