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

🔊 해당 포스팅은 밑바닥부터 만드는 인터프리터 in go 책을 읽고 개인적인 정리 목적 하에 작성된 글입니다. 본 포스팅에 사용된 자료는 모두 본인이 직접 재구성하여 작성하였음을 알립니다.

이번 포스팅에서는 직전 포스팅까지 해서 만들었던 우리만의 파서에 표현식을 파싱할 수 있는 기능을 탑재해볼 것이다. 코드레벨로 알아보기에 앞서 표현식 파싱이라는 것을 구현할 때 알아두어야할 사전 개념 몇 가지와 고려사항에 대해서 짚고 넘어가보자.

1. 표현식 파싱을 하기 전에..

직전 포스팅에서 구현했던 let 문, return 문 파싱은 let 또는 return 문 다음에 어떤 토큰들이 등장할지 명확했다. 하지만 표현식 파싱은 let, return 문 파싱처럼 쉽게 구현할만큼은 아니며 꽤 까다로운 작업이다.

가장 먼저 표현식을 파싱할 때 고려해야 할 사항은 연산자 우선순위(operator precedence)이다. 수학에서 사칙연산이라는 주제가 있다. 덧셈과 뺄셈은 곱셈과 나눗셈과 같이 등장하게 되면 곱셈과 나눗셈은 덧셈과 뺄셈보다 먼저 계산되어야 한다는 사실은 대부분의 사람들이 알고 있을 것이다. 이러한 원칙이 프로그래밍 언어에서도 당연히 적용되어야 한다. 뿐만 아니라 덧셈과 곱셈이 같이 등장했지만 덧셈 연산에 소괄호로 감싸져 있으면 덧셈이 먼저 수행되어야 한다. 예시는 다음과 같다.

 (5 + 10) * 2

표현식을 파싱할 때 고려해야할 또 다른 사항은 같은 타입의 토큰들이 여러 위치에 나타날 수 있다는 점이다. 예를 들어, 다음과 같은 코드가 있다고 해보자.

-5 - 10
5 * (add(2, 3) + 10)

첫번째 줄의 코드를 보면 먼저 등장하는 - 라는 기호는 전위 연산자를 의미한다. 즉 0에서 -5만큼을 빼는 연산이다. 하지만 뒤의 - 라는 기호는 중위 연산자로서 -5 와 10이라는 두 개의 숫자를 뺄셈하는 역할을 한다. 다음으로 두 번째 줄 코드를 보자. 가장 바깥에 있는 소괄호는 그룹 표현식으로서, 이 소괄호 안에 있는 표현식을 먼저 수행하라는 의미이다. 반면에 add(2, 3)에 있는 소괄호는 add 라는 함수의 호출 연산자로서 호출 표현식에 해당한다. 이렇게 같은 타입의 토큰이라도 여러 위치에 나타나게 될 때 각기의 기능이 달라지는 것을 볼 수 있다. 우리의 파서는 이런 점도 고려하면서 파싱을 수행해야 한다.

그러면 Monkey 프로그래밍 언어를 대상으로 우리만의 파서가 파싱할 수 있는 표현식 예시는 대표적으로 다음과 같다.

# 전위 연산자
-5
!true
!false

# 중위 연산자
5 + 5
5 - 5
5 / 5
5 * 5

# 비교 연산자
foo == bar
foo != bar
foo < bar
foo > bar

# 그룹 표현식
5 * (5 + 5)
((5 + 5) * 5) * 5

# 호출 표현식
add(2, 3)
add(add(2, 3), add(5, 10))
max(5, add(5, (5 * 5)))

# 식별자 표현식
foo * bar / foobar
add(foo, bar)

# 함수 리터럴 표현식
fn(x, y) {return x + y}(5, 5)
(fn(x) { return x }(5) + 10 ) * 10

# if 표현식
let result = if (10 > 5) { true } else { false };

우리는 위와 같은 종류들의 표현식을 파싱할 수 있도록 하기 위해서 하양식 연산자 우선순위 파싱 방법인 프랫 파싱을 사용해볼 것이다. 프랫 파싱의 핵심적인 구상은 "토큰을 파싱함수와 연관시킬 때, 해당 토큰이 중위인지 전위인지에 따라 서로 다른 파싱 함수로 연관시키는 것"이다.

2. AST 노드에 String 메서드 추가하기

본격적인 프랫 파서를 구현하기 전에 디버깅을 쉽게 할 수 있도록 구현한 AST 노드 즉, Node 라는 인터페이스에 String() 메서드를 충족시킬 수 있도록 구성하자. 이 String() 메서드는 AST를 구성하는 노드의 내용물을 출력함으로써 다른 노드와 비교도 하고, 우리가 의도하여 노드를 잘 구성했는지도 살펴볼 수 있다. Node 라는 인터페이스는 기존에 구현했던 let 문, return 문 노드의 인터페이스 뿐만 아니라 식별자 노드인 Identifier, 그리고 이번에 추가로 구현할 표현식 노드에도 추가해주도록 하자.

// ast/ast.go

type Node interface {
	TokenLiteral() string
	String() string
}

(..생략..)

func (p *Program) String() string {
	var out bytes.Buffer

	for _, s := range p.Statements {
		out.WriteString(s.String())
	}
	return out.String()
}

func (i *Identifier) String() string       { return i.Value }

func (ls *LetStatement) String() string {
	var out bytes.Buffer

	out.WriteString(ls.TokenLiteral() + " ")
	out.WriteString(ls.Name.String())
	out.WriteString(" = ")
	if ls.Value != nil {
		out.WriteString(ls.Value.String())
	}
	out.WriteString(";")
	return out.String()
}

func (rs *ReturnStatement) String() string {
	var out bytes.Buffer

	out.WriteString(rs.TokenLiteral() + " ")
	if rs.ReturnValue != nil {
		out.WriteString(rs.ReturnValue.String())
	}
	out.WriteString(";")
	return out.String()
}

func (es *ExpressionStatement) String() string {
	if es.Expression != nil {
		return es.Expression.String()
	}
	return ""
}

3. 프랫 파서 구현하기

이제 본격적으로 프랫 파서를 구현해보자. 앞서 언급했지만 프랫 파서의 핵심은 "토큰 타입과 파싱 함수를 연관 짓는 것"이다. 우리가 가장 먼저 할 일은 전위(prefix) 파싱 함수와 중위(infix) 파싱 함수를 그에 맞는 토큰과 연관 짓는 일이다.

먼저 우리는 전위 또는 중위 파싱과 연관된 토큰이 호출할 대상인 전위, 중위 파싱 함수 타입을 정의해보자.

// parser/parser.go

type (
	prefixParseFn func() ast.Expression
	infixParseFn func(ast.Expression) ast.Expression
)

prefixParseFn 이라는 타입의 함수는 이름에서 유추할 수 있다시피 전위 파싱을 수행하는 함수에 해당한다. 이는 아무것도 인자로 받지 않되, 표현식 타입을 반환한다. 반면에 infixParseFn 타입의 함수는 중위 파싱을 수행하며, 표현식 1개를 인자로 전달 받는다. 이 인자로 전달 받는 표현식은 중위 연산자의 좌측에 있는 표현식을 의미한다. 예를 들어, 아래처럼 중위 연산자가 사용되는 소스코드가 있다고 해보자.

2 * 5

그러면 infixParseFn 타입 함수의 인자에는 위 소스코드 기준으로 2 라는 표현식이 인자로 들어가는 셈이다.

이렇게 전위, 중위 파싱 함수 타입을 정의했으니 앞으로 전위 연산자 또는 중위 연산자와 관련된 토큰을 만나면 그에 맞는 파싱 함수를 호출할 수 있도록 해주자. 우리는 이를 위해 Parser 구조체에 다음과 같은 map 자료구조를 추가하자.

// parser/parser.go

type Parser struct {
	l         *lexer.Lexer
	errors    []string
	
	curToken  token.Token
	peekToken token.Token
	
	prefixParseFns map[token.TokenType]prefixParseFn
	infixParseFns map[token.TokenType]infixParseFn
}

그리고 이 map 자료구조에 특정 토큰과 특정 파싱 함수가 저장될 수 있게 해주는 함수도 같이 정의해보자.

// parser/parser.go

func (p *Parser) registerPrefix(tokenType token.TokenType, fn prefixParseFn) {
	p.prefixParseFns[tokenType] = fn
}

func (p *Parser) registerInfix(tokenType token.TokenType, fn infixParseFn) {
	p.infixParseFns[tokenType] = fn
}

3-1. 식별자 표현식 파싱하기

가장 먼저 구현해볼 기능은 식별자 표현식을 파싱하는 것이다. 다시 한번 식별자 표현식이란 어떤 소스코드를 의미하는지 리마인드 해보자.

foobar;
add(foobar, barfoo);
foobar + barfoo;
if (foobar) {
   (...생략...)
}

식별자 표현식을 잘 파싱하는지 테스트하는 코드부터 살펴보자.

// parser/parser_test.go

func TestIdentifierExpression(t *testing.T) {
	input := "foobar;"

	l := lexer.New(input)
	p := New(l)
	// run lexing and parsing
	program := p.ParseProgram()

	if len(program.Statements) != 1 {
		t.Fatalf("program.Statements does not contain 1 statements. got=%d", len(program.Statements))
	}
	// type assertion: downcast from interface to struct that satisfies `Statement` interface
    stmt, ok := program.Statements[0].(*ast.ExpressionStatement)  // `[0]`은 유일한 명령문이 담겨있는지 확인하기 위함
	if !ok {
		t.Fatalf("program.Statements[0] is not ast.ExpressionStatement. got=%T", stmt)
	}

	ident, ok := stmt.Expression.(*ast.Identifier)
	if !ok {
		t.Fatalf("stmt.Expression is not ast.Identifier. got=%T", ident)
	}
	if ident.Value != "foobar" {
		t.Errorf("ident.Value not %s. got=%s", "foobar", ident.Value)
	}
	if ident.TokenLiteral() != "foobar" {
		t.Errorf("ident.TokenLiteral() not %s. got=%s", "foobar", ident.TokenLiteral())
	}
}

테스트 코드는 이전과 작성한 것과 크게 다르지 않다. 테스트 코드의 해석은 독자에게 맡기려고 한다. 천천히 읽어보면서 그동안 배운 내용을 복습하는 것도 좋다. 현재 위 테스트 코드를 실행하면 당연히 실패한다. 왜냐하면 우리는 아직 식별자 표현식을 실질적으로 파싱하는 로직을 작성하지 않았기 때문이다. 이제 본격적으로 작성해보자.

가장 먼저 특정 토큰에 따라 switch-case 구문으로 분기해서 특정 구문을 파싱하도록 하는 함수에 식별자 표현식 분기를 추가해보도록 하자.

// parser/parser.go

func (p *Parser) parseStatement() ast.Statement {
	switch p.curToken.Type {
	case token.LET:
		return p.parseLetStatement()
	case token.RETURN:
		return p.parseReturnStatement()
	default:
		return p.ParseExpressionStatement()  // 새로 추가된 함수
	}
}

위 소스코드를 보면 ParseExpressionStatment 라는 새로운 함수가 추가되었다. 이 함수의 역할을 또 살펴보자.

// parser/parser.go

func (p *Parser) parseExpressionStatement() *ast.ExpressionStatement {
	stmt := &ast.ExpressionStatement{Token: p.curToken}
	stmt.Expression = p.parseExpression(LOWEST)
	
	if p.peekTokenIs(token.SEMICOLON) {
		p.nextToken()
	}
	return stmt
}

위 함수는 ExpressionStatment 라는 구조체를 초기화하고, 해당 구조체의 Token 멤버에 퍼서가 바라보고 있는 현재 토큰 즉, IDENT 이라는 토큰을 넣어준다. 그리고 해당 구조체의 Expression 멤버에 표현식을 실질적으로 파싱하는 역할을 하는 parseExpression 함수를 호출한다. 이 때, LOWEST 라는 인자를 넣어주는데, 이 LOWEST는 바로 다음으로 살펴볼 연산자 우선순위 중 가장 낮은 연산순위를 의미한다.

연산자 우선순위를 정의해보자.

// parser/parser.go

const (
	_ int = iota
	LOWEST
	EQUALS         // ==
	LESSGREATER    // < >
	SUM            // +
	PRODUCT        // *
	PREFIX         // !
	CALL           // 호출 연산자로서의 소괄호(ex. add())
)

Go 언어에는 iota라는 Enumerator가 존재한다. 이 iota를 사용하면 위의 경우 0에서부터 시작해서 1씩 증가하는 양의 정수를 부여할 수 있게 된다. 결국, LOWEST는 1이고 아래로 내려갈수록 1씩 증가하여 CALL은 7이 부여된다. 이는 연산자 우선순위를 의미하며 값이 높을수록 연산자 우선순위가 높다. 고로, 직전 소스코드에서 parseExpression 함수의 인자에 LOWEST를 넘겨준 것은 가장 낮은 연산자 우선순위를 넘겨준 것인 셈이다.

이제 parseExpression 함수의 로직을 살펴보자.

// parser/parser.go

func (p *Parser) parseExpression(precedence int) ast.Expression {
	prefix := p.prefixParseFns[p.curToken.Type]
	if prefix == nil {
		return nil
	}
	leftExp := prefix()  // call `prefixParseFn`
	
	return leftExp
}

아까 정의했던 토큰과 전위 파싱함수로 구성된 map 자료구조에서 현재 토큰 타입에 맞는 전위 파싱 함수를 가져와서 해당 함수를 호출한다. 이 호출하는 전위 파싱 함수의 생김새를 아직은 살펴보지는 않았지만 leftExp 변수에는 분명 파싱된 표현식 노드가 존재할 것이다.

방금 호출한 전위 파싱 함수의 생김새를 살펴보기 위해서 map 자료구조에 토큰과 그에 맞는 전위 파싱 함수를 등록해보자.

// parser/parser.go

func New(l *lexer.Lexer) *Parser {
	p := &Parser{
		l:      l,
		errors: []string{},
	}
	// 현재 초기 token 값은 빈 문자이기 때문에, curToken, peekToken에 토큰을 담으려면 2번 수행
	p.nextToken()
	p.nextToken()

	// 전위 파싱 함수와 그에 맞는 식별자 토큰을 등록
	p.prefixParseFns = make(map[token.TokenType]prefixParseFn)
	p.registerPrefix(token.IDENT, p.parseIdentifier)
	return p
}

// ast.Expression 이라는 인터페이스를 ast.Identifier 구조체가 충족하기 때문에 이처럼 표현 가능
func (p *Parser) parseIdentifier() ast.Expression {
	return &ast.Identifier{Token: p.curToken, Value: p.curToken.Literal}
}

렉서를 인자로 넣어 파서를 반환하는 New 함수에서 map 자료구조를 초기화하고, 전위 파싱 함수와 그에 맞는 IDENT(식별자) 토큰을 저장한다. 그리고 이 때 전위 파싱 함수인 parseIdentifer 함수는 단지 Identifer 구조체의 포인터 변수를 반환한다.

개인적으로 go-lang의 문법적으로 궁금했던 점은 Identifier 구조체 포인터 변수를 반환하는데, 왜 함수 시그니처에는 ast.Expression 인터페이스를 명시했나 궁금했다. 결국에는 반환하는 결과물을 구체적인 타입에 종속시키지 않고 추상화된 방식 즉, 호출자 입장에서 parseIdentifer 함수 말고도 다른 종류의 파싱 함수를 호출할 때 동일한 인터페이스로 호출이 가능하도록 만들어 주기 위함이였다. 아직 go-lang에 익숙하진 않아 어색하지만 적응해 나가는 시간이 필요할 듯 하다.

자, 이제 식별자 표현식을 파싱할 수 있는 기본적인 준비가 되었다. 아까 위에서 살펴본 테스트 코드를 아래처럼 실행해보자. 테스트 결과가 통과하면 잘 따라온 것이다.

go test ./parser

3-2. 정수 리터럴 표현식 파싱하기

다음으로 파서가 파싱할 표현식은 정수 리터럴 표현식이다. 정수 리터럴은 값 자체를 생성하기 때문에 표현식에 해당한다. 예시는 다음과 같다.

5;

위의 경우는 정수 리터럴만 존재하지만, 아래처럼 정수 리터럴이 다른 표현식과 섞여 존재할 수도 있다.

let x = 5; # `5`가 정수 리터럴
add(5, 10); # `5` 와 `10`이 정수 리터럴
5 + 5 + 5; # `5`라는 숫자 각각이 정수 리터럴

이번에도 테스트 코드를 먼저 살펴보자. 이 테스트 코드는 앞으로 우리가 구현할 정수 리터럴 표현식을 파서가 잘 파싱하는지 점검하기 위한 코드이다.

// parser/parser_test.go

func TestIntegerLiteralExpression(t *testing.T) {
	input := "5;"

	l := lexer.New(input)
	p := New(l)
	program := p.ParseProgram()
	checkParserErrors(t, p)
	
	if len(program.Statements) != 1 {
		t.Fatalf("program.Statements does not contain 1 statements. got=%d", program.Statements)
	}
	// type assertion: downcast from interface to struct(`ExpressionStatement`) that satisfies `Statement` interface
	stmt, ok := program.Statements[0].(*ast.ExpressionStatement)
	if !ok {
		t.Fatalf("program.Statements[0] is not ast.ExpressionStatement. got=%T", program.Statements[0])
	}
	// type assertion: downcast from interface(`Expression`) to struct(`IntegerLiteral`) that satisfies `Expression` interface
	literal, ok := stmt.Expression.(*ast.IntegerLiteral)
	if literal.Value != 5 {
		t.Errorf("literal.Value not %d. got=%d", 5, literal.Value)
	}
	if literal.TokenLiteral() != "5" {
		t.Errorf("literal.TokenLiteral not %s. got=%s", "5", literal.TokenLiteral())
	}
}

식별자 표현식을 테스트하는 코드와 거의 유사하되 약간 다른점이 있다. 바로 정수 리터럴 표현식을 나타내는 구조체로 type assertion 하는 부분이다. 아직은 IntegerLiteral 이라는 구조체를 우리가 정의하지는 않았다. 바로 다음에 정의할 것이다. 어쨌건 IntegerLiteral 이라는 구조체로 다운캐스팅을 수행한 후, 해당 구조체의 Value 멤버에 들어있는 값과 TokenLiteral() 메소드를 호출함으로써 반환되는 문자열을 비교한다. 이 때 주목할 점은 이전과 다르게 이번에는 Value 멤버에 들어있는 값이 문자가 아닌 실제 숫자인지를 비교한다는 점이다.

이제 IntegerLiteral 구조체를 아래처럼 정의해보자.

// ast/ast.go

type IntegerLiteral struct {
	Token token.Token
	Value int64
}

func (il *IntegerLiteral) expressionNode()      {}
func (il *IntegerLiteral) TokenLiteral() string { return il.Token.Literal }
func (il *IntegerLiteral) String() string { return il.Token.Literal }

IntegerLiteral 구조체 역시 2개의 멤버를 갖는데, 특이한 점은 Value 멤버의 타입이 문자열이 아닌 int64로 정의되었다. 이제 이 Value 멤버에는 정수 리터럴이 표현하는 문자가 갖는 실제 값 즉, 정수값을 담을 것이다.

이제 정수 리터럴에 대해서 실질적인 파싱을 수행하는 함수를 정의해야 한다. 아래 코드를 보자.

// parser/parser.go

func (p *Parser) parseIntegerLiteral() ast.Expression {
	lit := &ast.IntegerLiteral{Token: p.curToken}

	// `base = 0`: 문자열 접두사에 따라 자동으로 진법을 판단하여 정수로 변환
	value, err := strconv.ParseInt(p.curToken.Literal, 0, 64)
	if err != nil {
		msg := fmt.Sprintf("could not parse %q as integer", p.curToken.Literal)
		p.errors = append(p.errors, msg)
		return nil
	}
	lit.Value = value
	return lit
}

핵심 로직은 문자열은 정수형으로 변환하기 위해 strconv.ParseInt 함수를 사용했고, 변환 후, IntegerLiteral 구조체의 Value 멤버에 변환된 정수 값을 할당했다는 점이다.

이제 이렇게 작성한 정수 리터럴을 파싱하는 함수를 특정 토큰과 그 토큰에 맞는 파싱함수가 담겨있는 map 자료구조에 등록하기만 하면 된다. 아래와 같이 말이다.

// parser/parser.go

func New(l *lexer.Lexer) *Parser {
	(... 생략 ...)
    
	p.prefixParseFns = make(map[token.TokenType]prefixParseFn)
	p.registerPrefix(token.IDENT, p.parseIdentifier)
	p.registerPrefix(token.INT, p.parseIntegerLiteral)  // 새롭게 토큰과 파싱함수를 등록!
	return p
}

3-3. 전위 연산자 표현식 파싱하기

다음으로 살펴볼 부분은 전위 연산자, 그리고 그 전위 연산자와 함께 등장하는 표현식을 파싱할 차례다. 전위 연산자는 피연산자 1개를 갖는다. 그리고 이 피연산자를 가지고 표현식을 형성하는데, 아래와 같은 구조로 표현식이 만들어진다.(참고로 해당 책에서는 - 또는 ! 라는 전위 연산자만 파싱할 수 있도록 되어 있다. 기본적으로 + 연산자와 같은 것에 대한 파싱 기능이 제공되지는 않는다)

# 구조
<전위 연산자><표현식>

# 예시
-5;
!foobar;
!myFunc(2);
-add(5, 5);

이번에도 전위 연산자 표현식 파싱이 잘 동작하는지 테스트하는 테스트 코드부터 살펴보자.

// parser/parser_test.go

func TestParsingPrefixExpression(t *testing.T) {
	prefixTests := []struct {
		input        string
		operator     string
		integerValue int64
	}{
		{"!5;", "!", 5},
		{"-15;", "-", 15},
	}

	for _, tt := range prefixTests {
		l := lexer.New(tt.input)
		p := New(l)
		program := p.ParseProgram()
		checkParserErrors(t, p)

		if len(program.Statements) != 1 {
			t.Fatalf("program.Statements does not contain 1 statements. got=%d", len(program.Statements))
		}

		stmt, ok := program.Statements[0].(*ast.ExpressionStatement)
		if !ok {
			t.Fatalf("program.Statements[0] is not ast.ExpressionStatement. got=%T", program.Statements[0])
		}

		exp, ok := stmt.Expression.(*ast.PrefixExpression)
		if !ok {
			t.Fatalf("stmt is not ast.PrefixExpression. got=%T", stmt.Expression)
		}
		if exp.Operator != tt.operator {
			t.Fatalf("exp.Operator is not '%s'. got=%s", tt.operator, exp.Operator)
		}
		if !testIntegerLiteral(t, exp.Right, tt.IntegerValue) {
			return
		}
	}
}

func testIntegerLiteral(t *testing.T, il ast.Expression, value int64) bool {
	integ, ok := il.(*ast.IntegerLiteral)
	if !ok {
		t.Errorf("il not *ast.IntegerLiteral. got=%T", il)
		return false
	}
	if integ.Value != value {
		t.Errorf("integ.Value not %d. got=%d", value, integ.Value)
		return false
	}
	if integ.TokenLiteral() != fmt.Sprintf("%d", value) {
		t.Errorf("integ.TokenLiteral not %d. got=%s", value, integ.TokenLiteral())
		return false
	}
	return true
}

위 테스트 코드에서 아직 선언이 안된 것들이 있는 상태이다. 예를 들어, PrefixExpression 라는 구조체는 아직 정의가 안되어있지만, 이 구조체는 전위 연산자 표현식에 대한 정보를 담고 있는 구조체이다. 이제 이 PrefixExpression 이라는 구조체를 정의해보자.

// ast/ast.go

type PrefixExpression struct {
	Token token.Token
	Operator string 
	Right Expression
}

func (pe *PrefixExpression) expressionNode()      {}
func (pe *PrefixExpression) TokenLiteral() string { return pe.Token.Literal }
func (pe *PrefixExpression) String() string {
	var out bytes.Buffer
	
	out.WriteString("(")
	out.WriteString(pe.Operator)
	out.WriteString(pe.Right.String())
	out.WriteString(")")
	
	return out.String()
}

PrefixExpression 구조체는 크게 3가지 멤버를 가진다. 첫번째는 다른 구조체랑 동일하게 토큰 멤버를 가진다. 그리고 Operator는 연산자를 의미한다. 전위 연산자로는 -, ! 가 있다. 이 연산자 문자 자체가 들어간다. 그리고 Right 라는 멤버가 있는데, 이는 전위 연산자의 위치를 기준으로 오른쪽에 있는 표현식을 의미한하며 Expression 이라는 인터페이스 타입으로 선언되었다. PrefixExpression 구조체도 어쨌건 AST 노드로 구성되어야 하기 때문에 다른 구조체처럼 인터페이스를 충족시키기 위해 위에서 3가지 메소드를 정의했다.

여기서 잠시, parseExpression 메소드에 한 가지 추가적인 로직울 추가해보도록 하자. 이 추가된 로직은 전위 연산자 함수를 찾지 못했을 때 디버깅하기 쉽도록 콘솔에 메세지를 내뱉도록 한다.

// parser/parser.go

func (p *Parser) parseExpression(precedence int) ast.Expression {
	prefix := p.prefixParseFns[p.curToken.Type]
	if prefix == nil {
		p.noPrefixParseFnError(p.curToken.Type)
		return nil
	}
	leftExp := prefix() // call `prefixParseFn`

	return leftExp
}

func (p *Parser) noPrefixParseFnError(t token.TokenType) {
	msg := fmt.Sprintf("no prefix parse function for %s found", t)
	p.errors = append(p.errors, msg)
}

그러면 이제 전위 연산자 표현식에 대한 실질적인 파싱을 수행하는 함수를 작성해보자. 그리고 이 파싱 함수를 토큰과 그 토큰에 맞는 파싱 함수가 저장되어 있는 map 자료구조에 등록시켜보자.

// parser/parser.go

func (p *Parser) parsePrefixExpression() ast.Expression {
	expression := &ast.PrefixExpression{
		Token: p.curToken,
		Operator: p.curToken.Literal,
	}
	
	p.nextToken()
	
	expression.Right = p.parseExpression(PREFIX)
	return expression
}

func New(l *lexer.Lexer) *Parser {
	(... 생략 ...)

	p.prefixParseFns = make(map[token.TokenType]prefixParseFn)
	p.registerPrefix(token.IDENT, p.parseIdentifier)
	p.registerPrefix(token.INT, p.parseIntegerLiteral)
	p.registerPrefix(token.BANG, p.parsePrefixExpression)  // 전위 연산자 `!` 추가
	p.registerPrefix(token.MINUS, p.parsePrefixExpression) // 전위 연산자 `-` 추가
	return p
}

위 소스코드에서 특이한 점은 parsePrefixExpression 함수 내부에서 nextToken 함수를 한 번 호출한다는 점이다. 왜 호출할까? 이유부터 말하면 전위 연산자 오른쪽에 있는 표현식으로 토큰 위치를 옮기기 위함이다. 즉, nextToken 함수를 호출하기 전까지의 curToken은 전위 연산자(! 혹은 -)일 것이다. 하지만 전위 연산자가 등장하면 반드시 오른쪽에 표현식이 등장하기 마련이다. 따라서 이 오른쪽에 있는 표현식으로 현재 위치를 옮기기 위해 nextToken 함수를 한 번만 호출하는 것이다. 그리고 난 뒤에 parseExpression 함수로 오른쪽의 표현식을 파싱한다.

다만, 여기서 parseExpression 함수의 인자로 전달되는 PREFIX 즉, 전위 연산자의 우선순위 값이 구체적으로 어떻게 동작하는지는 아직 알아보지 못했다. 이는 바로 다음 목차인 중위 연산자에서 살펴볼 예정이다.

3-4. 중위 연산자 표현식 파싱하기

마지막으로 중위 연산자 표현식을 파싱하는 기능을 추가해보자. Monkey 프로그래밍 언어에서 중위 표현식의 예시 소스코드는 다음과 같다.

2 + 2;
2 - 2;
2 * 2;
2 / 2;
2 > 2;
2 < 2;
2 == 2;
2 != 2;

위 소스코드의 패턴에서 보면 알겠지만 중위 연산자 표현식은 다음과 같은 구조를 갖는다.

<왼쪽 피연산자> <중위 연산자> <오른쪽 피연산자>

역시나 이번에도 중위 연산자 표현식을 잘 파싱하는지 테스트하는 테스트 코드부터 살펴보자.

// parser/parser_test.go

func TestParsingInfixExpressions(t *testing.T) {
	infixTests := []struct {
		input string
		leftValue int64
		operator string
		rightValue int64
	}{
		{"2 + 2;", 2, "+", 2},
		{"2 - 2;", 2, "-", 2},
		{"2 * 2;", 2, "*", 2},
		{"2 / 2;", 2, "/", 2},
		{"2 > 2;", 2, ">", 2},
		{"2 < 2;", 2, "<", 2},
		{"2 == 2;", 2, "==", 2},
		{"2 != 2;", 2, "!=", 2},
	}
	
	for _, tt := range infixTests {
		l := lexer.New(tt.input)
		p := New(l)
		program := p.ParseProgram()
		checkParserErrors(t, p)
		
		if len(program.Statements) != 1 {
			t.Fatalf("program.Statements does not contain 1 statements. got=%d", len(program.Statements))
		}
		
		stmt, ok := program.Statements[0].(*ast.ExpressionStatement)
		if !ok {
			t.Fatalf("program.Statements[0] is not ast.ExpressionStatement. got=%T", program.Statements[0])
		}
		
		exp, ok := stmt.Expression.(*ast.InfixExpression)
		if !ok {
			t.Fatalf("stmt is not ast.InfixExpression. got=%T", stmt.Expression)
		}
		
		if !testIntegerLiteral(t, exp.Left, tt.leftValue) {
			return
		}
		if exp.Operator != tt.operator {
			t.Fatalf("exp.Operator is not '%s'. got=%s", tt.operator, exp.Operator)
		}
		if !testIntegerLiteral(t, exp.Right, tt.rightValue) {
			return
		}
	}
}

테스트 코드 자체는 전위 표현식 테스트 코드와 거의 유사하다. 다만, 중위 연산자 표현식에 사용되는 중위 연산자가 2개의 피연산자를 갖는 이항 연산자이다 보니, 연산자를 기준으로 왼쪽, 오른쪽에 있는 각 표현식을 검증하는 if 구문만 추가되었을 뿐이다.

위 테스트 코드에서 못보던 구조체가 나타나기 시작했다. 바로 ast.InfixExpression 이다. 이제 이 구조체를 정의해보자. 이 구조체 역시 AST 노드로 표현되어야 하므로 마찬가지로 Expression 인터페이스를 충족시켜보자.

// ast/ast.go

type InfixExpression struct {
	Token token.Token
	Left Expression
	Operator string
	Right Expression
}

func (ie *InfixExpression) expressionNode()      {}
func (ie *InfixExpression) TokenLiteral() string { return ie.Token.Literal }
func (ie *InfixExpression) String() string {
	var out bytes.Buffer
	
	out.WriteString("(")
	out.WriteString(ie.Left.String())
	out.WriteString(" "+ ie.Operator +" ")
	out.WriteString(ie.Right.String())
	out.WriteString(")")
	
	return out.String()
}

InfixExpression 구조체의 멤버를 보면 전위 표현식을 나타내는 구조체인 PrefixExpression과 달리 Left 멤버가 추가되었음을 볼 수 있다.

이제 우리는 중위 연산자 표현식이 등장했을 때, 파싱해줄 로직을 작성해보도록 하자. 가장 먼저 작성할 코드는 중위 연산자를 파싱하는 파싱 함수를 정의하고 등록시켜야 한다. 다만, 이 때 주의할 점은 어떤 연산자 토큰을 만났을 때 전위 연산자 파싱 함수를 가져올 것인지, 중위 연산자 파싱 함수를 가져올 것인지 잘 판단해야 한다. 단적인 예로, - 연산자가 등장했을 때 하나의 명령문 내에 서로 다른 기능을 하는 파싱 함수를 가져와야 할 때가 있다.

-5 - 3;

가장 앞에 있는 - 는 분명 전위 연산자이고, 이를 파싱할 때는 전위 연산자 파싱 함수를 가져와야 한다. 하지만 가운데에 있는 - 는 중위 연산자이고, 중위 연산자 파싱 함수를 가져와야 한다. 바로 이런 경우를 잘 구분해주어야 한다는 것이다. 밑에서 소개하겠지만 이러한 구분은 연산자 우선순위를 활용할 것이다. 따라서 특정 연산자의 우선순위를 저장하는 map 자료구조를 새롭게 하나 정의해보자.

// parser/parser.go

var precedences = map[token.TokenType]int {
	token.EQ: EQUALS,
	token.NOT_EQ: EQUALS,
	token.LT: LESSGREATER,
	token.GT: LESSGREATER,
	token.PLUS: SUM,
	token.MINUS: SUM,
	token.SLASH: PRODUCT,
	token.ASTERISK: PRODUCT,
}

위 map 자료구조의 value에 해당하는 값은 [3-1] 목차에서 상수로 정의한 각 연산자의 우선순위 값이다. 이로써 특정 토큰에 대한 우선순위 값을 매겨논 셈이다. 예를 들어, == 와 != 토큰은 같은 우선순위이고, > 와 < 가 같은 우선순위, + 와 -가, * 와 /가 서로 같은 우선순위이다.

그리고 연산자 우선순위 관련하여 유틸성 함수를 2가지를 정의할 것이다. 이는 파서가 바라보고 있는 토큰, 그리고 그 다음의 토큰에 매핑되는 연산자 우선순위를 반환하는 함수이다.

// parser/parser.go

func (p *Parser) peekPrecedence() int {
	if p, ok := precedences[p.peekToken.Type]; ok {
		return p
	}
	return LOWEST
}

func (p *Parser) curPrecedence() int {
	if p, ok := precedences[p.curToken.Type]; ok {
		return p
	}
	return LOWEST
}

위 소스코드의 로직은 매우 간단하니 설명은 따로 하지 않겠다. 그 다음은 파서를 초기화할 때 각 중위 연산자 토큰에 맞는 파싱 함수를 등록하자.

// parser/parser.go

func New(l *lexer.Lexer) *Parser {
	(... 생략 ...)
    
	p.prefixParseFns = make(map[token.TokenType]prefixParseFn)
	p.registerPrefix(token.IDENT, p.parseIdentifier)
	p.registerPrefix(token.INT, p.parseIntegerLiteral)
	p.registerPrefix(token.BANG, p.parsePrefixExpression)
	p.registerPrefix(token.MINUS, p.parsePrefixExpression)
	// 중위 연산자들에 대한 파싱 함수 추가
	p.infixParseFns = make(map[token.TokenType]infixParseFn)
	p.registerInfix(token.MINUS, p.parseInfixExpression)
	p.registerInfix(token.PLUS, p.parseInfixExpression)
	p.registerInfix(token.MINUS, p.parseInfixExpression)
	p.registerInfix(token.SLASH, p.parseInfixExpression)
	p.registerInfix(token.ASTERISK, p.parseInfixExpression)
	p.registerInfix(token.EQ, p.parseInfixExpression)
	p.registerInfix(token.NOT_EQ, p.parseInfixExpression)
	p.registerInfix(token.LT, p.parseInfixExpression)
	p.registerInfix(token.GT, p.parseInfixExpression)
	return p

새로운 메서드가 등장했다. 바로 parseInfixExpression이다. 이 메서드의 생김새를 보자.

// parser/parser.go

func (p *Parser) parseInfixExpression(left ast.Expression) ast.Expression {
	expression := &ast.InfixExpression{
		Token: p.curToken,
		Left: left,
		Operator: p.curToken.Literal,
	}
	
	precedence := p.curPrecedence()
	p.nextToken()
	
	expression.Right = p.parseExpression(precedence)
	return expression
}

이전에 작성한 parsePrefixExpression 메서드 생김새와 거의 유사하다. 차이점은 precedence 라는 변수에다가 현재 토큰의 연산자 우선순위를 반환한다. 여기에서도 nextToken 함수를 호출해서 현재 위치를 다음 토큰으로 옮긴다. 여기서도 이 동작은 왜 수행할까?

parseInfixExpression 메서드를 호출한다는 것은 파서가 현재 바라보는 토큰이 중위 연산자(ex. +, - ..) 토큰이라는 것이다. 그러므로 nextToken 함수를 한 번 호출하게 되면 현재 위치의 토큰이 중위 연산자의 오른쪽에 있는 표현식으로 이동하게 된다. 그리고 난 뒤 parseExpression 함수를 호출해서 InfixExpression 구조체의 Right 멤버에 할당해준다.

아직 끝난 것은 아니다. 중위 연산자 표현식 파싱 기능이 추가됨에 따라 아까 위에서 정의한 parseExpression 메서드의 개선이 필요하다. 현재 parseExpression 메서드의 생김새는 다음과 같다.

// parser/parser.go

func (p *Parser) parseExpression(precedence int) ast.Expression {
	prefix := p.prefixParseFns[p.curToken.Type]
	if prefix == nil {
		p.noPrefixParseFnError(p.curToken.Type)
		return nil
	}
	leftExp := prefix()

	return leftExp
}

현재는 전위 연산자 표현식만 처리할 수 있도록 되어 있는 상태이며 precedence 라는 인자 즉, 연산자 우선순위 값을 활용하지도 않는 상태이다. 중위 연산자 표현식도 처리할 수 있도록 개선한 parseExpression 메서드는 다음과 같다.

// parser/parser.go

func (p *Parser) parseExpression(precedence int) ast.Expression {
	prefix := p.prefixParseFns[p.curToken.Type]
	if prefix == nil {
		p.noPrefixParseFnError(p.curToken.Type)
		return nil
	}
	leftExp := prefix()
	
	for !p.peekTokenIs(token.SEMICOLON) && precedence < p.peekPrecedence() {
		infix := p.infixParseFns[p.peekToken.Type]
		if infix == nil {
			return leftExp
		}
		p.nextToken()
		
		leftExp = infix(leftExp)
	}

	return leftExp
}

연산자 우선순위를 사용해서 for loop를 도는데, 구체적으로 어떻게 동작하는지는 다음 포스팅에서 프랫 파서의 동작 원리를 살펴보면서 이해해보자. 궁금하다면 지금까지 작성한 소스코드에 대한 인풋 예시로 "2 == 2;" 를 넣는다고 가정하고 코드의 흐름을 따라가보자.

'Computer Science' 카테고리의 다른 글

[CS] 나만의 인터프리터를 만들어보자! (2): Parser 만들기 - 첫번째 (0)	2025.03.15
[CS] 나만의 인터프리터를 만들어보자!(1): Lexer 만들기 (2)	2025.03.01
[CS] 여러 가지 문자열 인코딩 방법과 base64 인코딩 (0)	2025.02.16
[CS] SSL/TLS 인증서는 어떻게 등장했을까? (0)	2024.12.19
[Network] 재택근무에서 활용하는 VPN은 어떻게 동작할까? (1)	2024.04.28

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

앎의 공간

[CS] 나만의 인터프리터를 만들어보자! (2): Parser 만들기 - 두번째

1. 표현식 파싱을 하기 전에..

2. AST 노드에 String 메서드 추가하기

3. 프랫 파서 구현하기

3-1. 식별자 표현식 파싱하기

3-2. 정수 리터럴 표현식 파싱하기

3-3. 전위 연산자 표현식 파싱하기

3-4. 중위 연산자 표현식 파싱하기

'Computer Science' 카테고리의 다른 글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

[CS] 나만의 인터프리터를 만들어보자! (2): Parser 만들기 - 두번째

1. 표현식 파싱을 하기 전에..

2. AST 노드에 String 메서드 추가하기

3. 프랫 파서 구현하기

3-1. 식별자 표현식 파싱하기

3-2. 정수 리터럴 표현식 파싱하기

3-3. 전위 연산자 표현식 파싱하기

3-4. 중위 연산자 표현식 파싱하기

'Computer Science' 카테고리의 다른 글

'Computer Science' Related Articles

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역