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

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

출처: Yes24

---

직전 포스팅에서는 우리만의 파서에 다양한 표현식을 파싱하는 기능을 탑재해보았다. 다만, 마지막에 중위 표현식을 파싱하는 기능을 구현하면서 소스코드를 살펴보는 것만으로 끝냈는데, 이번 포스팅에서는 도식화를 해보면서 소스코드랑 매핑한 후, 구체적으로 우리가 구현한 프랫파서가 어떻게 동작하는지 살펴볼 것이다. 그리고 더 나아가 다른 종류의 표현식도 파싱할 수 있도록 기능을 추가해보자.

1. 프랫(Pratt) 파서의 동작 원리

가장 마지막으로 구현했던 중위 표현식을 파싱하는 동작을 살펴보면서 프랫 파서의 동작 원리를 이해해보자. 파싱할 예제 소스코드는 다음과 같다.

 

1 + 2 + 3;

 

현재 소스코드로 구현하고 있는 Go언어 소스코드에 작성된 구조체를 기준으로 했을 때, 결과적으로 얻을 최종 AST 자료구조를 도식화 해보면 다음과 같다.

 

1 + 2 + 3; 명령문을 AST 자료구조로 도식화 한다면?

 

결론을 살펴보았으니, 이제 이 결론을 도출하는 과정의 흐름을 따라가보자. Go 소스코드에서는 위 AST 자료구조의 더 깊은 뎁스부터 차례대로 구현된다.

 

가장 먼저 위 입력 소스코드를 파싱하는 테스트 코드 부분이다.

 

// parser/parser_test.go

func TestParseInfixExpression(t *testing.T) {
	input := "1 + 2 + 3;"

	l := lexer.New(input)
	p := New(l)
	program := p.ParseProgram()
	checkParserErrors(t, p)
    
    (... 생략 ...)

 

먼저 렉서와 파서를 초기화 하는 부분이 있다. 소스코드로 치면 l := lexer.New(input) 와 p := New(l) 부분이다. 이 부분이 실행됨으로써 파서가 가리키는 토큰 위치는 다음과 같다.

 

curToken은 파서가 바라보는 현재 위치, peekToken은 다음 위치를 의미한다

 

이제 렉싱과 파싱이 실질적으로 실행되는 엔트리 포인트 지점은 바로 p.ParseProgram() 메소드다. 해당 메소드 소스코드를 보자.

 

// parser/parser.go

func (p *Parser) ParseProgram() *ast.Program {
	program := &ast.Program{}
	program.Statements = []ast.Statement{}

	for p.curToken.Type != token.EOF {
		stmt := p.parseStatement()
		if stmt != nil {
			program.Statements = append(program.Statements, stmt)
		}
		p.nextToken()
	}
	return program
}

 

p.curToken이 EOF 토큰이 아니기 때문에 조건에 부합하기 때문에 for-loop에 진입하기 시작한다. 첫 번째 loop를 돌면서 p.parseStatement 메소드를 호출한다. 이제 그러면 parseStatement 메소드의 생김새를 보자.

 

// 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() 
	}
}

 

현재 토큰의 타입에 따라 switch-case 구문을 타면서 어떤 메소드를 호출할지 결정된다. 현재 토큰은 let 문도, return 문도 아니다. 따라서 default 구문을 타게 되어 parseExpressionStatement 메소드를 호출한다. 이제 parseExpressionStatement 메소드의 생김새를 보자.

 

// 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
}

 

표현식 노드를 의미하는 ExpressionStatement 구조체를 초기화한다. 이 때 구조체의 멤버에는 현재 토큰인 1을 담는다. 이 1 이라는 토큰의 타입은 식별자를 의미하는 IDENT 타입이 담겨져 있다.(이 IDENT 토큰이 담겨지는 동작이 실제 수행되는 타이밍은 위에서 렉서를 초기화할 때이다. 소스코드에서 렉서의 NextToken 이라는 메소드를 살펴보자!) 이제 해당 구조체의 Expression 멤버에는 표현식을 파싱하는 결과를 할당하는데, 표현식을 파싱하는 역할을 하는 것은 바로 parseExpression 메소드다. 참고로 해당 메소드에 LOWEST 라는 가장 낮은 연산자 우선순위인 0을 인자로 넘겨준다. 이제 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
}

 

가장 먼저 p.curToken에 매핑되는 전위 연산자 파싱 함수가 있는지 체크한다. p.curToken은 여전히 1이라는 IDENT(식별자) 타입의 토큰이다. 이 토큰에 맞는 전위 연산자 파싱 함수는 존재할까? 존재하는지 보기 위해서는 가장 처음에 파서를 초기화했던 메소드를 살펴보아야 한다.

 

// 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)     // IDENT 토큰에 대한 파싱함수!
	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
}

 

주석 처리로도 해놓았다. IDENT 토큰에 매핑되는 전위 연산자 파싱 함수인 parseIdentifier 라는 메소드를 등록해놓았던 것을 볼 수 있다. 그러면 다시 parseExpression 메소드 소스코드로 돌아가서, IDENT 토큰에 매핑되는 전위 연산자 파싱 함수인 parseIdentifier를 얻게되고, 이 parseIdentifier 메소드를 호출해서 left 라는 변수에 할당하게 된다. 그러면 이제 parseIdentifier 메소드의 생김새를 볼 차례다.

 

// parser/parser.go

func (p *Parser) parseIdentifier() ast.Expression {
	return &ast.Identifier{Token: p.curToken, Value: p.curToken.Literal}
}

 

로직은 매우 간단하다. 단순히 curToken의 토큰인 IDENT와 토큰의 값인 1을 식별자 구조체의 멤버로 할당한 후 식별자 구조체를 반환한다. 그러면 다시 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()

	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
}

 

방금까지해서 leftExp := prefix() 라는 소스코드가 실행되었다. 다음으로 for-loop에 진입할 차례다. peekTokenIs 함수는 예전에 살펴본 메소드인데, 이름에도 알 수 있다시피 파서가 바라보는 다음 위치 토큰인 p.peekToken이 SEMICOLON 토큰인지 확인하는 역할을 한다. 앞에 not 연산자(!)가 붙었기 때문에 결국 다음 위치 토큰이 SEMICOLON이 아닐 경우를 의미한다. 

 

그리고 이제 드디어 인자로 받은 연산자 우선순위인 precedence를 활용할 차례다. 현재 precedence에는 LOWEST 값이 들어있다. 그리고 peekPrecedence 메소드를 호출함으로써 현재 파서가 바라보는 다음 위치 토큰의 연산자 우선순위를 반환받고, 이 2개의 연산자 우선순위 값을 비교한뒤 만약 다음 위치 토큰의 연산자 우선순위가 크다면 for-loop 구문을 타도록 한다.

 

그러면 다음 위치 토큰은 무엇일까? 여전히 현재 파서가 바라보는 토큰의 위치 상태는 다음과 같다.

 

curToken은 파서가 바라보는 현재 위치, peekToken은 다음 위치를 의미한다

 

즉, 다음 위치의 토큰인 peekToken는 연산자 토큰 +(PLUS)을 바라보고 있다. 그리고 이제 이 peekToken에 매핑된 중위 연산자 표현식을 파싱하는 메소드를 찾아보자. PLUS 토큰에 맞는 파싱 메소드는 parseInfixExpression 이다. parseInfixExpression 메소드를 호출하기 이전에 먼저 nextToken() 함수를 호출한다. 이 함수를 호출함에 따라 파서가 바라보는 토큰의 위치가 1칸씩 다음으로 옮겨진다.

 

curToken은 파서가 바라보는 현재 위치, peekToken은 다음 위치를 의미한다

 

토큰의 위치를 옮긴 후 parseInfixExpression 메소드를 이제 호출할 차례다. 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
}

 

parseInfixExpression 메소드는 표현식 하나를 인자로 받는다. 인자 이름이 left 인 것에서 추론할 수 있듯이, left는 중위 연산자를 기준으로 왼쪽에 있는 표현식을 의미한다. 현재 상황에서 left 인자에 담겨 있는 표현식은 아까 위에서 살펴본 1 이라는 식별자 토큰으로 만든 표현식 노드이다. 이 노드를 InfixExpression 구조체의 Left 멤버에 할당한다. 이 순간을 AST 자료구조로 도식화 하면 아래와 같은 상태이다.

 

 

다시 parseInfixExpression 메소드 소스코드로 돌아가보자. 이제 precedence := p.curPrecedence() 부분을 살펴보자. curPrecedence 메소드는 파서가 바라보는 현태 토큰의 연산자 우선순위를 얻게 된다. 현재 토큰은 +(PLUS) 토큰이기 때문에 해당 토큰의 연산자 우선순위 값은 4이다.(각 토큰에 매핑된 연산자 우선순위 상수 값은 parser/parser.go 소스코드의 변수로 정의되어 있으니 참고하자) 참고로, 이 때 또 한번 p.nextToken() 메소드를 호출해서 파서가 바라보는 토큰의 위치를 한 번 더 1칸씩 이동시킨다. 

 

curToken은 파서가 바라보는 현재 위치, peekToken은 다음 위치를 의미한다

 

그리고 이 4라는 연산자 우선순위 값을 parseExpression 메소드의 인자로 넣어서 다시 한번 재귀적으로 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()

	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
}

 

curToken은 현재 2라는 식별자 토큰으로 위치가 옮겨진 상태이다. 이 토큰에 매핑되어 있는 전위 연산자 파싱 함수가 존재하는지 살펴보자. 이 또한 식별자이기 때문에 위에서 1 이라는 토큰에 대해 파싱을 수행할 때랑 똑같다. 이번에는 2라는 식별자 표현식에 대해 파싱을 수행하는 함수를 살펴보는 부분은 중복되니 생략하겠다. 바로 for-loop 구문으로 가보자. 

 

peekToken은 +(PLUS)인 상태이다. 이 토큰은 SEMICOLON 토큰이 아니기 때문에 for-loop로 들어가기 위한 첫 번째 조건은 만족한다. 하지만 두번째 조건은 만족하지 못한다. 즉, 현재 인자로 전달받은 precedence 값은 4인 상태이다. peekPrecedence 메소드를 호출함으로써 얻는 값도 4이다. 이 두 개의 값은 같기 때문에 for-loop 구문으로 들어가지 않고, 곧바로 return 구문을 만나서 leftExp를 반환하고, 이 leftExp 변수에는 2라는 식별자 토큰을 파싱한 표현식이 담겨 있는 상태이다.

 

parseExpression 메소드가 종료되었으니 이 메소드를 호출한 호출자 메소드인 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
}

 

expression 이라는 구조체의 Right 멤버에 방금 parseExpression 메소드가 반환한 leftExp 변수 즉, 2라는 식별자 토큰을 파싱한 표현식 노드를 할당한다. 결국, 이렇게 되면서 AST 자료구조는 다음과 같이 노드가 추가된다.

 

 

이제 parseInfixExpression 메소드도 모두 끝이 났다. 헷갈리겠지만.. 이 parseInfixExpression 메소드를 호출한 호출자는 다른 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()

	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
}

 

이번 parseInfixExpression 메소드를 호출할 당시에 인자로 넘겨주었던 precednce 값은 LOWEST 였던 것을 기억하는가? 잘 판단이 안된다면 다시 위로 올라가서 천천히 흐름을 따라와보자. 단 번에 이해하지 못해도 괜찮다! 필자도 몇 번씩이나 다시 확인했다!

 

이제 2번쨰 for-loop를 돌 차례다. 그 전에 현재 파서가 바라보는 현재 토큰과 다음 토큰이 무엇인지 리마인드 해보자.

 

curToken은 파서가 바라보는 현재 위치, peekToken은 다음 위치를 의미한다

 

peekToken은 여전히 세미콜론이 아닌 상태이다. 그리고 precedence 값은 여전히 0이고, peekPrecedence 메소드를 호출함으로써 얻는 값 즉, peekToken인 +(PLUS)의 연산자 우선순위 값은 4이다. 여전히 0은 4보다 작기 때문에 이번에도 for-loop를 타는 조건에 부합한다. 

 

또 다시 +(PLUS) 토큰에 매핑된 중위 연산자 파싱 함수인 parseInfixExpression 메소드를 얻는다. 이 메소드를 호출하기 직전 nextToken 먼저 한 번 호출함으로써 토큰의 위치가 1칸씩 또 이동한다.

 

curToken은 파서가 바라보는 현재 위치, peekToken은 다음 위치를 의미한다

 

그리고 이제 parseInfixExpression 메소드를 호출한다. 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
}

 

left 인자에 들어가 있는 표현식 노드는 2라는 토큰을 파싱한 식별자 표현식 노드인 상태이다. 이 노드를 InfixExpression 구조체의 Left 멤버에 할당한다. 이 순간에 만들어지는 AST 자료구조 상태는 다음과 같다.

 

 

그리고 현재 토큰인 curToken은 +(PLUS)를 가리키는 상태이고 이 토큰의 연산자의 우선순위 값은 4였다. 그리고 또 한번 nextToken 메소드를 호출해서 토큰의 위치를 한 칸씩 옮긴다.

 

curToken은 파서가 바라보는 현재 위치, peekToken은 다음 위치를 의미한다

 

그리고 parseExpression 메소드를 호출하면서 +(PLUS) 토큰의 연산자 우선순위 값인 4를 인자로 넣어준다. 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
}

 

curToken은 현재 3이라는 식별자 토큰이다. 이 식별자 토큰에 매핑되는 전위 연산자 파싱 함수인 parseIdentifer 메소드를 얻고 호출해서 식별자 표현식 노드를 반환받는다. 이 노드는 leftExp 변수에 할당되었다.

 

그리고 for-loop에 또 진입한다. 이 때는 peekToken이 SEMICOLON이기 때문에 일단 이 조건부터 false 이기 때문에 for-loop를 타지 않는다. 물론 이 세미콜론 조건에 부합한다고 해도 precedence < p.peekPrecedence() 조건은 부합하지 못한다. peekPrecedence 메소드를 호출함으로써 peekToken인 SEMICOLON의 연산자 우선순위는 존재하지 않기 때문에 LOWEST인 0을 반환하게 되면서 현재 precedence 값은 4이지만, peekPrecedence 메소드가 반환하는 값은 0으로 대소 비교 조건을 만족하지 못한다. 따라서 곧바로 3이라는 식별자 토큰을 파싱한 식별자 표현식 노드를 반환한다.

 

이 3이라는 식별자 표현식 노드는 parseInfixExpression 메소드 안에서 expression 구조체의 Right 멤버에 할당된다. 이렇게 해서 최종 적인 AST 자료구조는 다음과 같이 만들어진다.

 

2. Bool 리터럴 파싱하기

이제 프랫 파서의 동작 원리에 대해 알아보았으니, 우리의 파서가 파싱하도록 할 수 있는 몇 가지 표현식을 더 추가해보도록 하자. 가장 먼저 Boolean을 의미하는 Bool 리터럴이다. Monkey 프로그래밍 언어에서 Bool 리터럴은 다음과 같이 소스코드로 표현될 수 있다.

 

true;
false;
let foobar = true;
let barfoo = false;

 

가장 먼저 할 작업은 Bool 리터럴을 담을 AST 노드를 정의하는 것이다. 

 

// ast/ast.go

type Boolean struct {
	Token token.Token
	Value bool
}

func (b *Boolean) expressionNode()      {}
func (b *Boolean) TokenLiteral() string { return b.Token.Literal }
func (b *Boolean) String() string       { return b.Token.Literal }

 

그리고 이 Bool 리터럴을 파싱할 수 있도록 전용 파싱 함수를 map 자료구조에 등록하자. 

 

// parser/parser.go

func New(l *lexer.Lexer) *Parser {
	p := &Parser{
		l:      l,
		errors: []string{},
	}
	(... 생략 ...)
	p.registerPrefix(token.TRUE, p.parseBoolean)
	p.registerPrefix(token.FALSE, p.parseBoolean)

	(... 생략 ...)
	return p
}

 

아직 Bool 리터럴을 실질적으로 파싱하는 함수 즉, parseBoolean 이라는 메소드의 생김새를 본 적이 없다. 이제 parseBoolean 메소드의 생김새를 보자. 

 

// parser/parser.go

func (p *Parser) parseBoolean() ast.Expression {
	return &ast.Boolean{Token: p.curToken, Value: p.curTokenIs(token.TRUE)}
}

 

curTokenIs 라는 함수를 사용했는데, 이전 포스팅에서 소개한 함수다. 어려운 로직은 아니고, 현재 파서가 바라보는 토큰이 인자로 넣어준, 여기서는 TRUE 토큰과 일치하면 true를, 불일치하면 false를 반환하는 매우 간단한 로직을 수행한다.

 

이제 이 Bool 리터럴을 잘 파싱하는지 테스트 하기 위한 테스트 코드를 살펴보자. 이번 테스트 코드를 추가하면서 기존에 작성해왔던 테스트 코드에 새롭게 추가된 메서드가 있다. 그 주인공은 testLiteralExpression 이라는 메서드이다.

 

// parser/parser_test.go

func testLiteralExpression(t *testing.T, exp ast.Expression, expected interface{}) bool {
	switch v := expected.(type) {
	case int:
		return testIntegerLiteral(t, exp, int64(v))
	case int64:
		return testIntegerLiteral(t, exp, v)
	case string:
		return testIdentifier(t, exp, v)
	case bool:
		return testBooleanLiteral(t, exp, v)
	}
	t.Errorf("type of exp not handled. got=%T", exp)
	return false
}

 

처음 보는 Go lang 문법이 등장했다. 우선 먼저 함수의 인자로 interface{} 라고 매우 일반화된 타입의 형식을 정의했다. interface는 go-lang에서 모든 타입을 나타낼 수 있는 최상위 타입을 의미한다. 그래서 해당 형식으로 인자를 받는다는 것은 그 인자에 어떤 타입이라도 올 수 있음을 의미한다. 그리고 그렇게 interface 타입으로 전달받은 인자를 .(type) 이라는 문법을 이용해서 v 라는 변수에 할당한다. 이 .(type) 이라는 문법은 타입 스위치라는 구문으로, interface 라는 매우 일반화된 아팁을 구체적인 특정 타입으로 판별하고 변환하는데 사용한다. 실제로 저 v 라는 변수에는 expected 라는 변수에 담겨 있는 값을 구체적인 타입으로 변환시킨 후의 값이 할당되어 있다.

 

이제 새로운 testBooleanLiteral 메소드를 살펴보자. 크게 별건 없고, testIdentifier 이나 testIntegerLiteral 메소드처럼 특정 AST 노드에 담겨있는 데이터가 Bool 리터럴인지 확인하는 용도이다.

 

// parser/parser_test.go

func testBooleanLiteral(t *testing.T, exp ast.Expression, value bool) bool {
	bo, ok := exp.(*ast.Boolean)
	if !ok {
		t.Errorf("exp not *ast.Boolean. got=%T", exp)
		return false
	}
	if bo.Value != value {
		t.Errorf("bo.Value not %t. got=%t", value, bo.Value)
		return false 
	}
	if bo.TokenLiteral() != fmt.Sprintf("%t", value) {
		t.Errorf("bo.TokenLiteral not %t. got=%s", value, bo.TokenLiteral())
		return false
	}
	
	return true
}

3. 그룹 표현식 파싱하기

다음으로 파싱해볼 것은 그룹 표현식이다. 그룹 표현식으로 인해서 그룹이 만들어지면 연산 우선순위에 변동이 생기고, 이에 따라 표현식이 평가되는 순서가 달라진다. 대표적으로 사칙 연산 안에서의 그룹 표현식을 사용한 예시다.

 

(5 + 5) * 10;

 

연산자 자체만 보면 곱셈이 덧셈보다 우선순위가 높지만, 덧셈이 그룹 표현식 소괄호 안에 감싸져 있기 때문에 이런 경우 덧셈이 곱셈보다 높은 우선순위를 갖는다. 이 그룹 표현식 파싱을 테스트 하는 코드는 TestOperatorPrecedenceParsing 이라는 테스트 함수에 아래의 예제 입력을 추가해보자.

 

// parser/parset_test.go

func TestOperatorPrecedenceParsing(t *testing.T) {
	tests := []struct {
		input    string
		expected string
	}{
		(... 생략 ...)
		{
			"1 + (2 + 3) + 4",
			"((1 + (2 + 3)) + 4)",
		},
		{
			"(5 + 5) * 2",
			"((5 + 5) * 2)",
		},
		{
			"2 / (5 + 5)",
			"(2 / (5 + 5))",
		},
		{
			"(5 + 5) * 2 * (5 + 5)",
			"(((5 + 5) * 2) * (5 + 5))",
		},
		{
			"-(5 + 5)",
			"(-(5 + 5))",
		},
		{
			"!(true == true)",
			"(!(true == true))",
		},
	}

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

		actual := program.String()
		if actual != tt.expected {
			t.Errorf("expected=%q, got=%q", tt.expected, actual)
		}
	}

 

이제 그룹 표현식을 파싱하는 함수를 등록하고, 작성해주어야 한다. 생각보다 엄청 간단하다. 먼저 파싱 함수를 등록하자.

 

// parser/parser.go

func New(l *lexer.Lexer) *Parser {
	p := &Parser{
		l:      l,
		errors: []string{},
	}
	(... 생략 ...)
	p.registerPrefix(token.LPAREN, p.parseGroupedExpression)

	(... 생략 ...)
	return p
}

 

그리고 parseGroupedExpression 이라는 메소드의 생김새를 보자.

 

// parser/parser.go

func (p *Parser) parseGroupedExpression() ast.Expression {
	p.nextToken()
	
	exp := p.parseExpression(LOWEST)
	
	if !p.expectPeek(token.RPAREN) {
		return nil
	}
	return exp
}

 

먼저 현재 파서가 바라보는 토큰이 왼쪽 소괄호일 것이기 때문에 토큰의 위치를 한 번 옮겨준다. 그리고 우선순위 연산자 값을 0 즉, LOWEST로 준 뒤 파싱을 수행토록 한다. 이 순간 재귀적으로 파싱이 호출되게 된다. 이렇게 재귀적으로 파싱 호출이 완료된 다음 파서가 바라보는 다음 토큰의 위치가 오른쪽 소괄호라면 해당 표현식을 return 하게 된다. 이 때 바로 그룹 표현식 파싱이 완료되는 것이다.

4. 조건 표현식 파싱하기

다음은 조건 표현식을 파싱할 차례다. Monkey 언어에서도 if-else 구문이 가능하도록 만들어보자. Monkey 언어에서의 if-else 구문 사용법은 다음과 같다.

 

if (x > y) {
  return x;
} else {
  return y;
}

 

물론 위처럼 else 구문까지 활용할 수도 있지만, else를 사용하지 않을 수도 있다. 예시는 다음과 같다.

 

if (x > y) {
  return x;
}

 

if-else 조건식은 표현식이다. 이 말은 if-else 구문에서 값을 만들어낸다는 뜻이다. 위 소스코드도 x 와 y 라는 값을 만들어낸다고 할 수 있다. 따라서 if-else 조건식이 갖는 구조는 다음과 같다.

 

if (<CONDITION>) <CONSEQUENCE> else <ALTENATIVE>

 

위 구조 중에서 <CONSEQUNECE> 와 <ALTENATIVE>는 중괄호로 포현되는 블록문을 갖는다. 이른바 body 블록을 갖는다. 이제 if-else 조건식의 구조를 살펴보았으니 파싱이 가능하도록 우리만의 파서를 구현해보자. 

 

가장 먼저 if-else 조건 표현식을 나타내는 AST 노드를 정의하자.

 

// ast/ast.go

type IfExpression struct {
	Token token.Token
	Condition Expression
	Consequence *BlockStatement
	Alternative *BlockStatement
}

func (ie *IfExpression) expressionNode()      {}
func (ie *IfExpression) TokenLiteral() string { return ie.Token.Literal }
func (ie *IfExpression) String() string {
	var out bytes.Buffer
	
	out.WriteString("if")
	out.WriteString(ie.Condition.String())
	out.WriteString(" ")
	out.WriteString(ie.Consequence.String())
	
	if ie.Alternative != nil {
		out.WriteString("else ")
		out.WriteString(ie.Alternative.String())
	}
	return out.String()
}

 

새로운 IfExpression 이라는 이름의 구조체를 정의했다. 해당 구조체는 4개의 멤버를 갖는데, 하나는 다른 구조체들과 동일하게 Token 값을 갖는다. 그리고 3개의 멤버는 직전에 알아본 if-else 조건 표현식의 구조로 살펴보았던 3가지 구성요소를 갖는다. 첫 번째는 조건식을 의미하는 Condition이다. 이 Condition은 표현식에 해당하기 때문에 Expression 인터페이스를 타입으로 명시했다. 그리고 Consequence와 Alternative는 BlockStatement 라는 처음보는 타입의 포인터 변수를 타입으로 명시했다. 이 2개를 블록을 갖는 구문이기 때문에 이 타입을 명시했다. 그러면 이제 BlockStatment가 무슨 타입인지 구체적으로 볼 차례다.

 

// ast/ast.go

type BlockStatement struct {
	Token      token.Token
	Statements []Statement
}

func (bs *BlockStatement) statementNode()       {}
func (bs *BlockStatement) TokenLiteral() string { return bs.Token.Literal }
func (bs *BlockStatement) String() string {
	var out bytes.Buffer
	
	for _, s := range bs.Statements {
		out.WriteString(s.String())
	}
	
	return out.String()
}

 

BlockStatment 라는 구조체는 슬라이스 형태의 여러 개의 Statment 인터페이스를 가질 수 있는 Statments 라는 멤버를 갖는다. 이 Statment는 1개의 명령문을 뜻한다. 다시 말해, BolckStatement는 여러 개의 명령문을 갖는다. 이유는 다음과 같은 구문이 가능하기 때문이다.

 

if (x > y) {
  z = x + y;
  return z
} else {
  z = x * y;
  return z
}

 

위처럼 하나의 블록 안에는 2개 이상의 명령문으로 구성될 수 있기 때문이다. 자, 이제 조건 표현식을 파싱하기 위한 노드 정의는 모두 마쳤다. 이제 테스트 코드를 살펴보자.

 

// parser/parser_test.go

func TestIfExpression(t *testing.T) {
	input := `if (x < y) { x }`
	
	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", 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.IfExpression)
	if !ok {
		t.Fatalf("stmt is not ast.IfExpression. got=%T", stmt.Expression)
	}
	
	if !testInfixExpression(t, exp.Condition, "x", "<", "y") {
		return 
	}
	
	if len(exp.Consequence.Statements) != 1 {
		t.Errorf("consequence is not 1 statements. got=%d\n", len(exp.Consequence.Statements))
	}
	
	consequence, ok := exp.Consequence.Statements[0].(*ast.ExpressionStatement)
	if !ok {
		t.Fatalf("Statements[0] is not ast.ExpressionStatement. got=%T", exp.Consequence.Statements[0])
	}
	
	if !testIdentifier(t, consequence.Expression, "x") {
		return 
	}
	
	if exp.Alternative != nil {
		t.Errorf("exp.Alternative.Statements was not nil. got=%+v", exp.Alternative)
	}
    
 func TestIfElseExpression(t *testing.T) {
	input := `if (x < y) { x } else { y }`

	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 %d statements. got=%d\n",
			1, 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.IfExpression)
	if !ok {
		t.Fatalf("stmt.Expression is not ast.IfExpression. got=%T", stmt.Expression)
	}

	if !testInfixExpression(t, exp.Condition, "x", "<", "y") {
		return
	}

	if len(exp.Consequence.Statements) != 1 {
		t.Errorf("consequence is not 1 statements. got=%d\n",
			len(exp.Consequence.Statements))
	}

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

	if !testIdentifier(t, consequence.Expression, "x") {
		return
	}

	if len(exp.Alternative.Statements) != 1 {
		t.Errorf("exp.Alternative.Statements does not contain 1 statements. got=%d\n",
			len(exp.Alternative.Statements))
	}

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

	if !testIdentifier(t, alternative.Expression, "y") {
		return
	}
}

 

크게 테스트 코드 구조가 변한 것은 없다. 단지 방금 우리가 새롭게 정의한 if-else 조건식 AST 노드를 검증하기 위해 어떤 구조체의 어떤 멤버에 접근해서 검증하는지 정도만 바뀌었다.

 

이제 다음으로 할 작업은 실질적인 파싱을 수행할 함수를 정의하고 등록하는 것이다. 

 

// parer/parser.go

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

 

if-else 조건 표현식을 파싱하는 함수인 parseIfExpression 메서드를 등록했다. 이 때, 전위표현식에 등록한 것을 볼 수 있는데, 이유는 if-else 조건 표현식은 if 라는 키워드가 가장 먼저 등장하기 때문이다. 이제 parseIfExpression 메소드가 어떻게 생겼는지 볼 차례다.

 

// parser/parser.go

func (p *Parser) parseIfExpression() ast.Expression {
	expression := &ast.IfExpression{Token: p.curToken}
	
	if !p.expectPeek(token.LPAREN) {
		return nil
	}
	
	p.nextToken()
	expression.Condition = p.parseExpression(LOWEST)
	
	if !p.expectPeek(token.RPAREN) {
		return nil
	}
	
	if !p.expectPeek(token.LBRACE) {
		return nil
	}
	
	expression.Consequence = p.parseBlockStatement()
	
	if p.peekTokenIs(token.ELSE) {
		p.nextToken()
		
		if !p.expectPeek(token.LBRACE) {
			return nil
		}
		
		expression.Alternative = p.parseBlockStatement()
	}
	
	return expression
}

 

먼저 IfExpreession 이라는 구조체를 할당 및 선언을 수행한다. 이 때의 curToken 값은 if 라는 키워드이다. 만약 다음 토큰 즉, peekToken 값이 <CONDITION>의 시작인 왼쪽 소괄호일 경우에만 계속 로직을 수행하도록 한다. 이 때, expectPeek 메소드를 호출하면서 curToken, peekToken을 하나씩 옮긴다는 사실을 잊지말자! 왼쪽 소괄호인지 검사가 끝난 후, 다시 한번 curToken, peekToken을 하나씩 이동시킨다. 이제 curToken은 왼쪽 소괄호 다음에 있는 첫번째 토큰에 있을 것이다. 이 시점에 조건식 즉, <CONDITION>을 파싱하기 위해 이전에 살펴보았던 parseExpression 메소드를 호출한다. 이 때, 연산자 우선순위는 가장 낮은 값이 LOWEST를 지정해 넘긴다. 이렇게 <CONDITION> 파싱이 끝났으면 다음으로는 if의 body 블록을 파싱할 차례다. 만약 성공적으로 <CONDITION> 파싱이 끝났다면 curToken은 오른쪽 소괄호의 직전 토큰 위치에 있을 것이다.

 

이제 다음 토큰이 오른쪽 소괄호인지 검사한다. 이 때도 마찬가지로 expectPeek 메소드를 호출함으로써 curToken, peekToken을 하나씩 옮긴다. 그리고 또 한번 expectPeek 메소드를 호출해 한칸씩 또 옮긴다. 물론 이번에 expectPeek 메소드는 다음 토큰이 body 블록의 시작을 의미하는 왼쪽 중괄호인지를 검사한다. 이렇게 되면 curToken의 위치는 왼쪽 중괄호에 위치한다.

 

그리고 난 뒤, 이 시점에 <CONSEQUENCE> 를 파싱하기 위해 parseBlockStatement 메소드를 호출한다. 이제 parseBlockStatement 메소드의 로직을 살펴보자.

 

// parser/parser.go

func (p *Parser) parseBlockStatement() *ast.BlockStatement {
	block := &ast.BlockStatement{Token: p.curToken}
	block.Statements = []ast.Statement{}
	
	p.nextToken()
	
	for !p.curTokenIs(token.RBRACE) && !p.curTokenIs(token.EOF) {
		stmt := p.parseStatement()
		if stmt != nil {
			block.Statements = append(block.Statements, stmt)
		}
        p.nextToken()
	}
	return block
}

 

사실 위 소스코드 로직은 우리에게 낯설지는 않다. 바로 파서 관련 첫 번째 포스팅에서 살펴보았던 ParseProgram 이라는 이름의 메소드랑 생김새가 매우 비슷하다.

 

다만 차이점은 curTokenIs 라는 메소드로 body 블록의 끝을 의미하는 오른쪽 중괄호가 나올때까지 계속 for-loop를 수행하면서 명령문들을 파싱하는 것이다.

 

이렇게 해서 if-else 조건문 표현식 파싱이 모두 끝이났다. 해당 목차 초반에 작성했던 테스트 코드를 수행하면 잘 통과되는 것을 볼 수 있다.

5. 함수 리터럴 파싱하기

다음은 함수 리터럴에 대한 파싱이다. 함수 리터럴은 말 그대로 함수를 정의한 표현식이다. Monkey 언어에서의 소스코드 예시는 다음과 같다.

 

fn(x, y) {
  return x + y;
}

fn() {
  return foobar + barfoo;
}

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

fn() {
  return fn(x, y) { return x > y; };
}

myFunc(x, y, fn(x, y) { return x > y; });

 

위처럼 함수 리터럴을 정의하는 방식은 여러가지이다. 함수 리터럴 자체만 정의할 수도 있고, 함수 리터럴 안에서도 파라미터가 없을 경우 또는 여러 개일 경우가 있다. 또한 함수 리터럴을 즉시 어떤 변수에 할당할 수도 있고, 함수 리터럴 안에 또 다른 함수 리터럴을 중첩 상태로 정의할 수도 있다. 마지막으로 함수 리터럴을 다른 함수의 인자로 넣을 수도 있다.

 

우리는 함수 리터럴을 파싱하기 위해 2가지 포인트에 집중해야 한다. 첫 번째는 파라미터 리스트이다. 어떤 함수는 파라미터를 1개만 받거나 2개 이상을 받거나 또는 아예 받지 않을 수도 있다. 두 번째는 함수의 몸체인 body 블록 부분이다. 이 블록 부분은 직전 목차에서 살펴본 if-else 구문의 body 블록문을 파싱할 때 사용하던 메소드를 그대로 사용한다. 즉, 함수 리터럴을 표현식으로 정의한 뒤, 함수 리터럴을 파싱하는 로직을 수행하는 함수만 작성해 제공하면 된다. 그래서 함수 리터럴 표현식의 구조는 다음과 같다.

 

fn <PARAMETERS> <BLOCKSTATEMENT>

 

이제 하나씩 살펴보자. 가장 먼저 해볼 부분은 함수 리터럴을 AST 노드로서 정의하는 것이다. 

 

// ast/ast.go

type FunctionLiteral struct {
	Token      token.Token
	Parameters []*Identifier
	Body       *BlockStatement
}

func (fl *FunctionLiteral) expressionNode()      {}
func (fl *FunctionLiteral) TokenLiteral() string { return fl.Token.Literal }
func (fl *FunctionLiteral) String() string {
	var out bytes.Buffer
	
	params := []string{}
	for _, p := range fl.Parameters {
		params = append(params, p.String())
	}
	
	out.WriteString(fl.TokenLiteral())
	out.WriteString("(")
	out.WriteString(strings.Join(params, ", "))
	out.WriteString(") ")
	out.WriteString(fl.Body.String())
	
	return out.String()
}

 

함수 리터럴을 AST 노드로 표현하기 위해 FunctionLiteral 이라는 새로운 구조체를 정의했다. 이 구조체는 3개의 멤버를 갖는데, 하나는 늘 그랬듯이 Token, 그리고 함수의 파라미터를 의미하는 Parameters이다. 파라미터는 식별자로 정의되고 파라미터가 0개 이상일 수 있기 때문에 슬라이스 형태로 정의했다. 그리고 함수의 블록을 의미하는 Body가 멤버로서 존재한다.

 

이번에도 테스트 코드에 대한 코드 블록을 먼저 언급한다. 로직 자체는 그동안의 테스트 코드랑 역시 다르지 않기 때문에 스윽 한 번 읽어보도록 하자. 별다른 설명은 하지 않겠다.

 

// paresr/parser_test.go

func TestFunctionLiteralParsing(t *testing.T) {
	input := `fn(x, y) { x + y; }`

	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 %d statements. got=%d\n",
			1, 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])
	}

	function, ok := stmt.Expression.(*ast.FunctionLiteral)
	if !ok {
		t.Fatalf("stmt.Expression is not ast.FunctionLiteral. got=%T",
			stmt.Expression)
	}

	if len(function.Parameters) != 2 {
		t.Fatalf("function literal parameters wrong. want 2, got=%d\n",
			len(function.Parameters))
	}

	testLiteralExpression(t, function.Parameters[0], "x")
	testLiteralExpression(t, function.Parameters[1], "y")

	if len(function.Body.Statements) != 1 {
		t.Fatalf("function.Body.Statements has not 1 statements. got=%d\n",
			len(function.Body.Statements))
	}

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

	testInfixExpression(t, bodyStmt.Expression, "x", "+", "y")
}

 

이제 함수 리터럴 표현식을 파싱하기 위한 토큰에 맞는 파싱 함수를 등록하고 정의해보자.

 

// parer/parser.go

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

 

새로운 함수인 parseFunctionLiteral 메소드를 보자.

 

// parser/parser.go

func (p *Parser) parseFunctionLiteral() ast.Expression {
	lit := &ast.FunctionLiteral{Token: p.curToken}
	
	if !p.expectPeek(token.LPAREN) {
		return nil
	}
	lit.Parameters = p.parseFunctionParameters()
	
	if !p.expectPeek(token.LBRACE) {
		return nil
	}
	
	lit.Body = p.parseBlockStatement()
	return lit
}

 

방금 정의한 함수 리터럴을 AST 노드로 표현하기 위한 FunctionLiteral 구조체를 정의한다. curToken은 현재 fn 토큰이다. expectPeek 메소드를 호출함으로써 peekToken이 왼쪽 소괄호인지 확인하면서 맞다면 curToken, peekToken을 한 칸씩 옮긴다. 그러면 curToken은 이제 왼쪽 소괄호를 가리키고 있다. 이 순간에 함수 리터럴의 파라미터 리스트를 파싱하기 위해 parseFunctionParameters 메소드를 호출한다. parseFunctionParameters 메소드로 또 이동해보자.

 

// parser/parser.go

func (p *Parser) parseFunctionParameters() []*ast.Identifier {
	identifiers := []*ast.Identifier{}

	if p.peekTokenIs(token.RPAREN) {
		p.nextToken()
		return identifiers
	}
	p.nextToken()

	ident := &ast.Identifier{Token: p.curToken, Value: p.curToken.Literal}
	identifiers = append(identifiers, ident)

	for p.peekTokenIs(token.COMMA) {
		p.nextToken()
		p.nextToken()
		ident := &ast.Identifier{Token: p.curToken, Value: p.curToken.Literal}
		identifiers = append(identifiers, ident)
	}

	if !p.expectPeek(token.RPAREN) {
		return nil
	}
	return identifiers
}

 

현재 curToken은 왼쪽 소괄호인 상태이다. 만약 다음 토큰이 오른쪽 소괄호인지를 확인한다. 즉, 바로 다음 토큰이 오른쪽 소괄호라는 것은 파라미터가 아무것도 없음을 의미한다. 그러므로 그 즉시 토큰을 한칸씩 옮긴 뒤 빈 슬라이스를 반환한다. 

 

다음 토큰이 오른쪽 소괄호가 아니라면 nextToken 메소드를 호출해서 토큰을 한 칸씩 옮긴다. 즉, 현재 curToken은 첫번째 파라미터 식별자에 가 있을 것이다. 이를 Identifier 구조체 하나를 선언 및 정이를 수행한다. 그리고 슬라이스에 이 구조체를 하나 append 한다.

 

그리고 난 뒤, 다음 토큰이 컴마(,)인 경우 계속 for-loop의 body 블록을 탄다.(컴마인 이유는 파라미터 구분자를 컴마로 구분하기 때문이다) 블록 안에서는 nextToken 2번을 호출해서 curToken이 두 번째 파라미터 식별자로 옮기도록 한다. 예를 들어, 파라미터가 fn(x, y, z) 이런 식으로 있다고 가정해보자. 만약 nextToken을 한 번만 호출할 경우에는 curToken이 x뒤의 컴마(,)에 위치할 것이다. 그러므로 nextToken을 한번 더 호출해주어서 curToken이 y라는 두 번째 파라미터 식별자로 위치하도록 해준다.

 

이렇게 두 번째 파라미터 식별자에 대해서 Identifier 구조체를 만들고 또 슬라이스에 추가한다. 이러한 과정을 다음 토큰에 컴마가 나오지 않을 때까지 계속 반복한다. 이 for-loop가 종료되고 난 뒤, 다음 토큰이 오른쪽 소괄호일 경우 그동안 append 했던 슬라이스를 반환하도록 한다.

 

이제 다시 parseFunctionParameters를 호출했던 호출자 함수인 parseFunctionLiteral도 돌아와보자.

 

// parser/parser.go

func (p *Parser) parseFunctionLiteral() ast.Expression {
	lit := &ast.FunctionLiteral{Token: p.curToken}
	
	if !p.expectPeek(token.LPAREN) {
		return nil
	}
	lit.Parameters = p.parseFunctionParameters()
	
	if !p.expectPeek(token.LBRACE) {
		return nil
	}
	
	lit.Body = p.parseBlockStatement()
	return lit
}

 

FunctionLiteral 구조체의 Parmeters 멤버에 파라미터들을 할당하는 것까지 수행했다. 이제 함수 리터럴의 body 블록을 파싱할 차례다. 여기는 직전 목차인 if-else 조건 표현식의 body 블록을 파싱했을 때랑 동일하다. 다음 토큰이 왼쪽 중괄호가 나오는지 확인하고, 나온다면 parseBlockStatement 메소드를 호출해서 body 블록의 명령문들을 파싱한다.

6. 함수 호출 표현식 파싱하기

이제 대망의 마지막 기능을 파싱에 추가해볼 차례다. 바로 함수 호출 표현식이다. 함수 호출 표현식의 예제는 다음과 같다.

 

add(2, 3)

add(2 + 2, 3 * 3 * 3)

 

소스코드에서 add는 식별자이다. 이 식별자 add에는 add 라는 함수를 정의한 함수 리터럴이 바인딩되어 있다. 그래서 추후에 배울 평가하는 과저에서 식별자 add는 평가 시 함수를 반환하게 된다. 즉 파서가 소스코드를 읽어내려가면서 add 라는 식별자는 지나가버리고 add를 함수 리터럴로 대체하게 된다. 예를 들어, 위 소스코드의 add(2, 3)은 아래처럼 add가 함수 리터럴로 대체된다.

 

# add가 함수 리터럴로 대체
fn(x, y) { x + y; }(2, 3)

 

또한 함수 리터럴을 함수 호출의 인자로 사용할 수도 있다. 

 

myFunc(2, 3, fn(x, y) { x + y; });

 

그래서 함수 호출 표현식의 구조는 다음과 같다.

 

<EXPRESSION>(<EXPRESSION>, <EXPRESSION>, ... , <EXPRESSION>)

 

이제 함수 호출 표현식을 AST 노드로 표현해보자. 

 

// ast/ast.go

type CallExpression struct {
	Token      token.Token
	Function   Expression
	Arguments  []Expression
}

func (ce *CallExpression) expressionNode()      {}
func (ce *CallExpression) TokenLiteral() string { return ce.Token.Literal }
func (ce *CallExpression) String() string {
	var out bytes.Buffer
	
	args := []string{}
	for _, a := range ce.Arguments {
		args = append(args, a.String())
	}
	
	out.WriteString(ce.Function.String())
	out.WriteString("(")
	out.WriteString(strings.Join(args, ", "))
	out.WriteString(")")
	
	return out.String()
}

 

CallExpression 이라는 새로운 구조체는 3개의 멤버를 갖는다. 첫 번째는 토큰, 두 번째는 Function 이라는 멤버인데, 표현식을 의미하는 Expression 인터페이스 타입으로 정의되었다. 그리고 Arguments는 여러 개의 표현식으로 구성되어 있는 것을 의미해서 슬라이스 형태이 Expression 인터페이스 타입으로 정의되었다. 이제 테스트 코드를 보자.

 

// parser/parser_test.go

func TestCallExpressionParsing(t *testing.T) {
	input := "add(1, 2 * 3, 4 + 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 %d statements. got=%d\n",
			1, len(program.Statements))
	}

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

	exp, ok := stmt.Expression.(*ast.CallExpression)
	if !ok {
		t.Fatalf("stmt.Expression is not ast.CallExpression. got=%T",
			stmt.Expression)
	}

	if !testIdentifier(t, exp.Function, "add") {
		return
	}

	if len(exp.Arguments) != 3 {
		t.Fatalf("wrong length of arguments. got=%d", len(exp.Arguments))
	}

	testLiteralExpression(t, exp.Arguments[0], 1)
	testInfixExpression(t, exp.Arguments[1], 2, "*", 3)
	testInfixExpression(t, exp.Arguments[2], 4, "+", 5)
}

 

함수 호출 표현식을 파싱하기 위해서는 파싱 함수를 추가하되 새로운 토큰을 추가하지는 않는다. 왜냐하면 기존에 있던 토큰들을 사용하기 때문이다. 예를 들어, add(2, 3) 과 같은 함수 호출 표현식을 파싱한다고 해보자. add는 식별자이기 때문에 기존에 식별자에 대한 토큰을 정의했었다. 그리고 바로 다음에 등장하는 왼쪽 소괄호도 기존에 사용했던 토큰이다. 다만, 이 왼쪽 소괄호를 기준으로 중위 표현식 파싱 함수를 추가해야 한다. 

 

다시 회고해보자. 우리는 왼쪽 소괄호 일명 LPAREN 이라는 토큰에 대해서 추가했던 파싱 함수가 있다. 바로 이 포스팅의 3번 목차에서 살펴본 그룹 표현식에서다. 하지만 이번에 함수 호출 표현식을 파싱하기 위해서는 LPAREN 이라는 토큰에 대해서 중위 표현식을 파싱하는 함수를 추가해야 한다. 따라서 아래와 같이 파서를 초기화할 때, LPAREN 토큰에 대한 중위 표현식 파싱 함수를 추가해보자.

 

// parser/parser.go

func New(l *lexer.Lexer) *Parser {
	p := &Parser{
		l:      l,
		errors: []string{},
	}
        p.prefixParseFns = make(map[token.TokenType]prefixParseFn)
	(... 생략 ...)
    
	p.registerPrefix(token.LPAREN, p.parseGroupedExpression)
    
	(... 생략 ...)

	p.infixParseFns = make(map[token.TokenType]infixParseFn)
 
	(... 생략 ...)
	p.registerInfix(token.LPAREN, p.parseCallExpression)
	return p
}

 

새로운 메소드인 parseCallExpression을 살펴보자.

 

// parser/parser.go

func (p *Parser) parseCallExpression(function ast.Expression) ast.Expression {
	exp := &ast.CallExpression{Token: p.curToken, Function: function}
	exp.Arguments = p.parseCallArguments()
	return exp
}

 

특이하게 Expression 인터페이스 즉, 표현식인 함수를 인자로 넘겨주는 것을 볼 수 있다. 이는 아까 말했던 add 라는 식별자가 미리 파싱된 것을 의미한다. 그리고 parseCallArguments 메소드를 호출해서 함수 호출의 인자에 명시되어 있는 0개 이상의 표현식들을 파싱한다. 이제 parseCallArguments 메소드의 생김새를 보자.

 

// parser/parser.go

func (p *Parser) parseCallArguments() []ast.Expression {
	args := []ast.Expression{}

	if p.peekTokenIs(token.RPAREN) {
		p.nextToken()
		return args
	}
	
	p.nextToken()
	args = append(args, p.parseExpression(LOWEST))
	
	for p.peekTokenIs(token.COMMA) {
		p.nextToken()
		p.nextToken()
		args = append(args, p.parseExpression(LOWEST))
	}
	
	if !p.expectPeek(token.RPAREN) {
		return nil
	}
	return args
}

 

현재 curToken은 왼쪽 소괄호인 상태이다. 다음 토큰인 peekToken이 오른쪽 소괄호가 아닌 경우 로직을 계속 타도록 하는데, 먼저 nextToken을 호출해서 토큰의 위치를 한 칸씩 옮겨준다. 그리고 난 뒤 옮겨진 curToken에 있는 표현식을 파싱하기 위해 parseExpression을 호출한다. 그리고 난 뒤 함수 호출의 다음 인자를 파싱하기 위해 다음 토큰이 컴마가 등장하지 않을 때까지 계속적으로 표현식 파싱을 수행하고, args 라는 슬라이스 변수에 담아낸다.

 

그리고 for-loop 구문을 빠져 나와 다음 토큰이 오른쪽 소괄호이면 즉시 args 슬라이스를 반환한다.

 

그런데 이렇게만 해서 테스트 코드를 수행하면 통과하지 않는다. 왜냐하면 현재 함수 호출 표현식의 왼쪽 소괄호 중위 연산자에 대한 연산자 우선순위가 설정되지 않았기 때문이다. 함수 호출 표현식의 왼쪽 소괄호 중위 연산자의 우선순위는 가장 높다. 따라서 아래처럼 가장 높은 우선순위 연산자를 지정한 후 테스트 코드를 다시 실행하면 테스트가 잘 통과하는 것을 볼 수 있다.

 

// 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,
	token.LPAREN:   CALL,     // 함수 호출 표현식의 중위 연산자에 대한 우선순위 설정
}

---

이렇게 해서 파서의 모든 기능 구현이 끝났다. 다음 포스팅 부터는 파서와 렉서가 만든 AST 자료구조를 평가(Evaluation) 하는 방법에 대해서 알아보도록 하자.