상세 컨텐츠

본문 제목

"밑바닥부터 만드는 인터프리터 in Go" 공부 정리 (1) - Lexing, Token, REPL

Computer Science

by Yongari 2023. 6. 7. 12:33

본문

사전 준비물

  • 컴퓨터에 Go 언어 1.7 버전 이상 설치되어 있으면 좋습니다. 
  • 이 게시물은 "밑바닥부터 만드는 인터프리터 in Go"를 보고 정리를 하기위해 만든 게시물입니다. "밑바닥부터 만드는 인터프리터 in Go"는 어떤 서드파티 툴이나 라이브러리를 이용하지 않고 바닥부터 인터프리터를 만드는 책입니다. 여러 인터프리터 중에서도 소스코드를 파싱하고 나서 추상구문트리(AST, Abstract Syntax Tree)를 만들고 이것을 평가하는 인터프리터인 "트리 탐색(tree-walking) 인터프리터"에 대한 책이다. 이 트리 탐색 인터프리터를 Go 언어로 설명하는 책이다.  그리고 렉서(lexer), 파서(parser), 트리 표현법(tree representation), 평가기(evaluator)를 만들고 토큰이 무엇인지, 추상구문트리가 무엇인지 설명하는 책이다. 

 

참고 

이 게시물은 공부한 내용을 정리하기 위한 게시물입니다. 글의 질이 떨어지더라도 양해바랍니다!~

 

 

 

인터프리터란 무엇인가? 

모든 인터프리터는 특정 프로그래밍 언어를 해석(interpret)하기 위해 만들어진다. 이것이 프로그래밍 언어를 구현하는 방법이다. 
컴파일러나 인터프리터가 없는 프로그래밍 언어는 실현되지 않은 생각 또는 구현 명세에 지나지 않는다. 개인적인 의견으로는 의사코드 같은것?이 되지 않을까 생각된다.

 

이 책에서는 다음과 같은 특징을 가지는 언어를 만들려고 한다.

 

  • C 계열의 문법 구조
  • 변수 바인딩
  • 정수와 불
  • 산술 표현식
  • 내장 함수
  • 일급 함수(함수를 값처럼 취급하는 함수)와 고차 함수(다른 함수를 함수의 인수(argument)로 하는 함수)
  • 클로저
  • 문자열 자료구조
  • 배열 자료구조 
  • 해시 자료구조 

 

인터프리터는 다음과 같이 몇 개의 주요 부분으로 구성된다.

렉서(lexer)

파서(parser)

추상구문트리(AST, Abstract Syntax Tree)
내부 객체 시스템

평가기(evaluator)

 

 

어휘분석

소스코드로 어떤 작업을 하려면 코드를 더 접근하기 쉬운형태로 변환해야하는데 이렇게 할 때 다음과 같이 두 단계에 걸쳐서 표현법을 바꾸려고 한다. 

 

소스코드를 토큰열로 바꾸는 것을 렉싱(lexing)이라고 부르며 이 행위는 lexer가 수행한다. 토큰은 그 자체로 쉽게 분류할 수 있는 작은 자료구조다. 이 토큰을 파서에 입력하고 파서는 토큰열을 추상구문트리(Abstract Syntax Tree)로 바꾼다.

과정은 다음과 같다. 

 

1. 소스코드를 렉서에 입력한다.

let x = 5 + 5;

 

2. 렉서는 소스코드를 다음과 같은 토큰 열로 바꾼다. 

[
LET,
IDENTIFIER("x"),
EQUAL_SIGN,
INTEGER(5),
PLUS_SIGN,
INTEGER(5),
SEMICOLON
]

 

 

토큰 정의하기

첫 번째로 할 일은 렉서가 만드는 결과물인 토큰을 정의하는 것이다.
처음에는 토큰을 몇 개 지정한 뒤 렉서가 확장할 때마다 토큰도 확장한다.

먼저 렉싱할 내용의 소스코드는 다음과 같다.

let five = 5;
let ten = 10;

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

let result = add(five, ten);

렉서나 파서는 숫자가 5인지 10인지 중요하지 않다. 그냥 숫자라는 것을 알면된다. 이것도 변수이름에 똑같이 적용된다. 

변수이름은 "식별자"라고 부른다. 그리고 식별자 처럼 보이지만 식별자가 아닌 단어가 있다. 이런 단어를 예약어(keywords)라고 부른다. 

위와 같은 특성을 따져봤을 때 토큰에는 "타입"속성이 필요하다. 타입 정보가 있어야 정수와 특수문자 "]"등을 구별할 수 있다. 그리고 토큰 자체의 문자값을 갖고있을 필드가 필요하다 예를 들면 5나 10인지에 대한 정보를 저장할 변수가 필요하다는 뜻이다.

 

토큰 구조체는 다음과 같다.

type TokenType string
type Token struct {
	Type    TokenType
	Literal string
}

위 코드에서  TokenType의 타입을 string으로 정의했다.이렇게 함으로써 서로 다른 여러 값을  TokenType으로 필요한 만큼 정의해서 사용할 수 있다.  

 

위와 같은 원리로 토큰 코드를 작성하면 다음과 같다.

 

token.go

package token

type TokenType string //서로 다른 여러 값을 TokenType으로 필요한만큼 정의해서 사용가능하다.

type Token struct {
	Type    TokenType
	Literal string
}

const (
	ILLEGAL = "ILLEGAL" //어떤 토큰이나 문자를 렉서가 알 수없다는 뜻이다.
	EOF     = "EOF"     //파일의 끝을 말한다.

	//식별자 + 리터럴
	IDENT = "IDENT" // add, foobar, x,y, ...
	INT   = "INT"   //1343456

	//연산자
	ASSIGN   = "="
	PLUS     = "+"
	MINUS    = "-"
	BANG     = "!"
	ASTERISK = "*"
	SLASH    = "/"

	LT = "<"
	GT = ">"

	EQ     = "=="
	NOT_EQ = "!="

	//구분자
	COMMA     = ","
	SEMICOLON = ";"

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

	// Keywords
	FUNCTION = "FUNCTION"
	LET      = "LET"
	TRUE     = "TRUE"
	FALSE    = "FALSE"
	IF       = "IF"
	ELSE     = "ELSE"
	RETURN   = "RETURN"
)

//토큰 리터럴에 맞는 TokenType을 반환할 함수를 정의함

// 식별자가 예약어인지 정의한 함수
var keywords = map[string]TokenType{
	"fn":     FUNCTION,
	"let":    LET,
	"true":   TRUE,
	"false":  FALSE,
	"if":     IF,
	"else":   ELSE,
	"return": RETURN,
}

// 키워드 테이블을 검사해서 주어진 식별자가 예약어인지 아닌지 살펴본다.
// 만약 예약어라면 TokenType 상수를 반환한다.
// 만약 예약어가 아니라면 그냥 token.IDENT를 반환한다.  token.IDENT는 사용자 정의 식별자를 나타내는 TokenType이다.
// 다음 함수를 통해 식별자와 예약어 렉싱을 마무리할 수 있다.
func LookupIdent(ident string) TokenType {
	if tok, ok := keywords[ident]; ok {
		return tok
	}
	return IDENT
}

 

 

렉서

렉서는 렉싱을 수행하는 주체다. 렉서는 소스코드를 입력으로 받고 소스코드를 표현하는 토큰 열을 결과로 출력한다. 

렉서는 입력받은 소스코드를 훑어가면서 토큰을 인식할 때마다 결과를 출력한다. 버퍼도 필요없고 토큰을 저장할 필요도 없다. 토큰을 출력하는 NextToken 메서드 하나면 충분하다. 핵심은 NextToken이다!

다음 lexer.go와 lexer_test.go를 통해 lexer가 어떻게 동작하는지 이해해보자!~

 

 

lexer.go

package lexer

import (
	"monkey/token"
)

// position과 readPosition 모두 입력문자열에 있는 문자에 인덱스로 접근하기 위해 사용된다.
// 입력문자열을 가리키는 포인터가 두 개인 이유는 다음 처리 대상을 알아내려면 입력 문자열에서 다음 문자를 미리 살펴봄과 동시에 현재 문자를 보존할 수 있어야 하기 때문이다.
type Lexer struct {
	input        string
	position     int  //입력에서 현재 위치(현재 문자를 가리킴)
	readPosition int  //입력에서 현재 읽는 위치 (현재 문자의 다음을 가리킴)
	ch           byte //현재 조사하고 있는 문자, 현재문자가 곧 byte 타입을 갖는 ch다.
}

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

// 문자열 input에서 렉서가 현재 보고 있는 위치를 다음으로 이동하기위한 메서드
func (l *Lexer) readChar() {

	//문자열 input의 끝에 도달했는지 확인함
	if l.readPosition >= len(l.input) {
		//끝에 도달했다면 l.ch에 아스키 코드 문자 NUL에 해당하는 0을 넣는다.
		l.ch = 0
	} else {
		//끝에 도달 못했다면 l.input[l.readPosition]으로 접근해서 l.ch에 다음 문자를 저장한다.
		l.ch = l.input[l.readPosition]
	}
	//l.position을 l.readPosition으로 업데이트하고 readPosition은 1 증가시킴
	l.position = l.readPosition
	//l.readPosition은 항상 다음에 읽어야할 위치, l.position은 마지막으로 읽은 위치
	l.readPosition += 1
	//렉서는 유니코드가 아니라 아스키 문자만 지원함, 렉서를 단순화하기 위함
	//유니코드 지원은 독자가 알아서 개선하기..
}

// 렉서의 핵심 함수다.  렉서는 소스코드를 입력받아서 토큰열로 출력해주는 기능이 핵심이다.
func (l *Lexer) NextToken() token.Token {
	//token.go에서 정의한 token
	var tok token.Token

	//공백처리를 위한 함수
	l.skipWhitespace()

	switch l.ch {
	case '=':
		//렉서가 입력에서 ==을 만나면 렉서는 token.EQ 하나를 만드는 게 아니라 token.ASSIGN을 두 개 생성한다.
		//그래서 peekChar 메서드를 사용해야한다.
		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 '+':
		tok = newToken(token.PLUS, l.ch)
	case '-':
		tok = newToken(token.MINUS, 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)
		}
	case '/':
		tok = newToken(token.SLASH, l.ch)
	case '*':
		tok = newToken(token.ASTERISK, l.ch)
	case '<':
		tok = newToken(token.LT, l.ch)
	case '>':
		tok = newToken(token.GT, l.ch)
	case ';':
		tok = newToken(token.SEMICOLON, l.ch)
	case ',':
		tok = newToken(token.COMMA, l.ch)
	case '{':
		tok = newToken(token.LBRACE, l.ch)
	case '}':
		tok = newToken(token.RBRACE, l.ch)
	case '(':
		tok = newToken(token.LPAREN, l.ch)
	case ')':
		tok = newToken(token.RPAREN, l.ch)
	case 0:
		tok.Literal = ""
		tok.Type = token.EOF
	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)
		}
	}

	l.readChar()
	return tok
}

//readChar 함수와 비슷한 기능
//다음에 나올 입력을 미리 살펴본다 = peek
//l.position이나 l.readPosition을 증가시키지 않는다.
func (l *Lexer) peekChar() byte {
	if l.readPosition >= len(l.input) {
		return 0
	} else {
		return l.input[l.readPosition]
	}
}

// 토큰타입과 현재 조사하고 있는 문자를 입력으로 받는다. 반환은 토큰타입으로 반환한다.
func newToken(tokenType token.TokenType, ch byte) token.Token {
	//토큰 타입과 토큰스트링 리터럴로 반환
	return token.Token{Type: tokenType, Literal: string(ch)}
}

// 현재 토큰의 Literal 필드를 채운다.
func (l *Lexer) readIdentifier() string {
	position := l.position
	for isLetter(l.ch) {
		l.readChar()
	}
	return l.input[position:l.position]
}

// 이 책에서 글자란 isLetter 함수가 참으로 판별하는 문자(character)을 뜻한다.
func isLetter(ch byte) bool {
	//_ 문자를 글자로 다루겠다는 뜻이고 식별자와 예약어에 사용하겠다는 뜻
	return 'a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z' || ch == '_'
}

// 공백문자를 통째로 지나가는 함수
func (l *Lexer) skipWhitespace() {
	for l.ch == ' ' || l.ch == '\t' || l.ch == '\n' || l.ch == '\r' {
		l.readChar()
	}
}

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

// 전달받은 byte가 0부터 9사이의 라틴 숫자인지 아닌지 여부만 반환한다.
func isDigit(ch byte) bool {
	return '0' <= ch && ch <= '9'
}

 

lexer_test.go

package lexer

import (
	"testing"

	"monkey/token"
)

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, ""},
	}
	//신규입력
	l := New(input)

	for i, tt := range tests {
		//넥스트 토큰
		tok := l.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)
		}
	}
}

 

 

 

 

첫 번째 REPL(Read Eval Print Loop)

REPL은 "콘솔" 혹은 "대화형(interactive) 모드"라고 부른다. 개념은 모두 같다. REPL은 입력을 읽고(Read) 

인터프리터에 보내 평가하고(Eval), 인터프리터의 결과물을 출력하고(Print) 이런 동작을 반복(Loop)하기 때문에 REPL(Read, Eval, Print, Loop)라고 부른다. 

 

내용은 다음과 같다.

입력 소스코드를 줄 바꿈을 만날 때까지 읽는다. 읽은 행을 렉서 인스턴스에 전달하고 EOF를 만나기 전까지 렉서가 반환하는 결과물인 토큰을 모두 출력한다. 하단의 main.go에서는 사용자가 REPL에 접속했음을 환영하는 메시지를 출력하고 REPL을 시작한다. fmt.Printf 함수와 repl.Start를 참고하면 된다.

 

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.Printf(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.Printf("%+v\n", tok)
		}
	}
}

 

 

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! This is the Monkey programming language!\n",
		user.Username)
	fmt.Printf("Feel free to type in commands\n")
	repl.Start(os.Stdin, os.Stdout)
}

 

그리고 첫 번째 렉싱 파트를 생각하면서 다음 코드를 실행하면 다음과 같다.

 

 

main.go 파일 바이너리로 바꾼다. 

go build main.go 

./main

이후 main 파일을 실행하고 소스코드를 입력하면 다음과 같다.

읽어보면 토큰열로 인식해서 출력함을 알 수 있다.

./main 
Hello robertseo! This is the Monkey programming language!
Feel free to type in commands
>> let add = fn(x,y) {x+y;};       
{Type:LET Literal:let}
{Type:IDENT Literal:add}
{Type:= Literal:=}
{Type:FUNCTION Literal:fn}
{Type:( Literal:(}
{Type:IDENT Literal:x}
{Type:, Literal:,}
{Type:IDENT Literal:y}
{Type:) Literal:)}
{Type:{ Literal:{}
{Type:IDENT Literal:x}
{Type:+ Literal:+}
{Type:IDENT Literal:y}
{Type:; Literal:;}
{Type:} Literal:}}
{Type:; Literal:;}

 

 

 

 

 

출처 : 밑바닥부터 만드는 인터프리터 in Go(책) 

 

소스코드 출처 : (하단 링크를 주소창에 입력하면 다운로드됩니다.)

https://interpreterbook.com/waiig_code_1.3.zip

 

저작자표시

티스토리툴바