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

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

출처: Yes24

---

직전 포스팅에서 우리는 입력된 소스코드 문자열을 토큰화시키는 렉서를 직접 만들고 테스트를 해보았다. 이번 포스팅에서는 이 렉서가 만들어낸 토큰들을 가지고 AST(추상 구문 트리)와 같은 자료구조로 변환을 수행하는 파서(Parser)를 만들어보도록 하자. 해당 챕터는 내용이 길어지기 때문에 몇 개의 포스팅으로 나누어서 게시할 예정이다. 이제 파서를 만들어보는 첫 걸음을 내딛어보자.

1. Parser란 무엇일까?

파서를 만들어보기 전, 우리는 파서라는 것이 무엇이고 어떤 역할을 하는지 알아야 만들어가면서 그 의미를 제대로 이해해볼 수 있을 것이다. 프로그래밍을 해본 경험이 있거나 SQL 쿼리를 작성하거나 하게 되면 한 번쯤은 파싱 에러(Parsing Error)라는 메세지를 접해본 적이 있을 것이다. 파서의 사전적인 정의는 "(주로 문자로 된) 입력 데이터를 받아 파스 트리, 추상 구문트리 등과 같은 계층을 갖는 자료구조로 만들어내는 소프트웨어 컴포넌트"이다. 쉽게 말하면 우리가 이전 포스팅에서 살펴본 렉서가 만들어낸 토큰들을 자료구조로 변환하는 셈이다. 이 변환 과정을 거치면서 파서는 구조화된 표현을 더하기도 하고 구문이 올바른지 검사하기도 한다. 잠시 이전 포스팅에서 사용했던 사진 자료를 다시 가져와보자.

 

파싱은 언제 수행되는 걸까?

 

위 그림을 보면 '파싱'이라는 동작이 수행되는데, 이 '파싱'을 수행하는 주체가 파서임을 알 수 있다. 보편적으로 사용되고 있는 인터프리터, 단적인 예로, Python 프로그래밍 언어에 사용되는 인터프리터를 개발자들이 사용하면서 자신들이 입력한 소스코드가 자료구조로 변환하는 것을 피부에 와닿게 느끼지는 못한다. 대체 왜일까? 그것은 바로 인간인 개발자들은 파서가 만들어낸 자료구조에 익숙하지 않기 때문이다.

 

파서가 만들어내는 자료구조 중 인간인 개발자에게 익숙한 대표적인 예시가 있다. 바로 JSON 파서이다. 대부분의 개발자들은 JSON 이라는 자료구조로 파싱해본 적이 있을 것이다. Python에서는 아래와 같이 JSON String을 JSON 자료구조, 파이썬에서는 딕셔너리 자료구조로 파싱을 해본적이 있을 것이다.

 

# https://www.w3schools.com/python/python_json.asp
import json

# some JSON:
x =  '{ "name":"John", "age":30, "city":"New York"}'

# parse x:
y = json.loads(x)

# the result is a Python dictionary:
print(y["age"])

 

위 소스코드를 한 번이라도 사용해본 적이 있을 것이다. 이러한 JSON 파서도 소스코드에 사용되는 파서와 본질적으로 개념은 같다. 이 '본질적으로 같은 개념'이라 함은 문자열을 입력받아서 어떠한 자료구조로 파싱한다는 점이다. 하지만 JSON 파서는 우리에게 익숙하지만, 소스코드의 파서는 우리에게 익숙하지 않은 이유는 단순히 소스코드의 파서가 만들어내는 자료구조를 우리가 자주 본적이 없을 뿐이다. 

 

따라서, 우리가 JSON 이라는 자료구조를 이해하면 JSON 파서를 이해할 수 있듯이, 소스코드 파서가 만들어내는 자료구조를 이해할 수 있기만 한다면 우리는 소스코드 파서가 어떤 원리로 동작하는지 이해할 수 있게 된다.

 

일반적으로, 소스코드의 파서들이 만들어내는 자료구조로는 구문트리(Syntax Tree) 또는 추상구문트리(Abstract Syntax Tree, AST)라고 부른다. '추상' 이라는 키워드가 붙은 이유는 소스코드에서 보이는 세부 정보(예를 들어, 세미콜론, 줄 바꿈, 공백, 주석, 대괄호, 중괄호, 소괄호, ...들은 구문트리에서 생략되기 때문이다. 이러한 세부정보는 단순히 파서가 AST를 구성할 때, 구성 형태를 알려주는 용도로만 사용될 뿐이다. 또한 이 AST 형식은 모든 파서가 사용하는 공통적인 형식이 있는 것은 아니다. 프로그래밍 언어마다 또는 파서마다 구현체가 약간 씩은 달라진다.

 

이제 파서에 대한 내용을 정리해보자면, 파서는 소스코드 문자열을 입력으로 받아서 소스코드를 표현하는 자료구조(ex. AST, ..)를 만들어낸다. 이 때, 자료구조를 만들어내느 동안 파서는 입력을 분석하게 되는데 이 '분석'이라 함은 입력이 예상 구조에 맞는지 검사하는 것이다. 이 검사하는 과정을 '구문 분석(Syntactic Analysis)'이라고도 한다.

 

참고로, 요즘에는 파서를 우리처럼 직접 생성하는 것보다는 이 파서 자체를 자동으로 생성해주는 파서 제네레이터를 이용하기도 한다. 대표적인 파서 제네레이터로는 yacc, bison, ANTLR 등이 있다. 이 파서 제네레이터는 특정 언어에 대한 공식적인 설명이 주어졌을 때, 출력으로 파서를 생성하는 도구이다. 이 '출력'물은 소스코드인데, 컴파일 또는 인터프리팅되는 코드이다. 이 부분에 대한 깊은 내용은 다루지 않는다. 단지 파서를 직접 생성하는 방법도 있지만 파서 제네레이터라는 별도의 도구를 이용해서 파서를 생성하는 방법도 있다는 점만 알아두도록 하자.

 

파서를 생성하는 방법

 

마지막으로, 파서의 파싱 전략에 대해서도 간단히 알아두자. 파싱 전략에는 크게 아래와 같은 종류로 구분 된다.

 

파싱 전략의 종류

 

우리가 만들 파서의 파싱 전략은 하향식의 재귀적 하향 파싱에서도 하향식 연산자 우선순위 파서를 만들 것이다. 이 파서를 프랫 파서라고도 부른다. 하향식을 사용하는 이유는 AST의 루트 노드를 생성하는 것으로 시작해서 점점 아래쪽으로 파싱해 나간다. 이러한 전략은 처음 파서를 구현하는 사람들에게 자주 권장되는 전략이다. 왜냐하면 재귀적 하향 파서가 구성하는 AST와 그 생성 방식이 사람이 생각하는 방식과 유사하기 때문이다. 따라서 우리는 재귀적 하향 파싱의 하향식 연산자 우선순위 파서를 만들어볼 것이다.

 

이제 간단하게 파서가 무엇이고, 우리가 만들 파서가 어떤 파싱 전략을 가져갈지도 알아보았다. 이제 본격적으로 파서의 기능을 하나씩 구현해보자.

2. let 문 파싱하기

우리만의 파서에 첫번째로 도입해볼 기능은 Monkey 프로그래밍 언어의 let 선언문을 파싱할 수 있도록 하는 것이다. 즉, 아래와 같은 소스코드를 입력으로 받았을 때, 파서가 정확히 파싱을 잘 할 수 있도록 하는 것이 목표이다.

 

let x = 5;
let y = 10;
let add = fn(a, b) {
  return a + b;
};

 

let 문을 정확히 파싱한다는 것은 파서가 let 문이 담고 있는 정보를 정확히 표현하는 AST 자료구조를 만든다는 뜻이다. let 문을 파싱하기 전에 위와 같은 let 문이 어떤 요소들로 구성되어 있는지 파악할 필요가 있다. 그래야 '이 요소들'을 이용해서 AST 자료구조를 구성할 수 있기 때문이다. 

 

위 소스코드는 let 문 3개로 구성된 일련의 명령문이다. 그리고 let 문은 2개의 구성 요소로 구성된다. 하나는 식별자이고, 다른 하나는 표현식이다.

 

빨간색은 식별자, 파란색은 표현식

 

한 줄의 let 명령문은 식별자와 표현식으로 구성된다. 식별자는 빨간색, 표현식은 파란색 글씨이다. 그리고 위 소스코드를 또 2가지 구성요소로도 구분할 수 있다.

 

회색 선, 네모칸은 명령문, 파란색은 표현식

 

위 자료의 회색 선 또는 네모칸을 우리는 1개의 명령문이라고 한다. 그리고 파란색 부분은 표현식이라고 한다. 이 두 개 간의 차이점이 있는데, 명령문은 값을 만들지 않지만, 표현식은 값을 만든다는 것이다. 물론 위의 경우에서 함수 리터럴 부분도 표현식으로 정의하긴 했지만 이를 표현식으로 정의할지 명령문으로 정의할지는 프로그래밍 언어마다 달라진다. 다른 예로, if 구문도 if 구문 내부에서 값을 만들 수 있도록 지원하는 언어라면 if 구문을 표현식으로 정의하게 된다.

 

이제 let문의 구성요소를 살펴보았으니, 우리는 앞으로 AST 자료구조를 만들때 두 가지 유형의 노드를 만들어 사용할  것이다. 하나는 표현식 타입과 하나는 명령문 타입이다. 해당 유형의 노드를 만들기 위해 go 언어에서 interface 라는 문법을 사용할 것이다. 소스코드를 살펴보자.

 

// ast/ast.go
package ast

type Node interface {
	TokenLiteral() string
}

type Statement interface {
	Node
	statementNode()
}

type Expression interface {
	Node
	expressionNode()
}

 

먼저 Node 라는 타입을 정의하고 해당 타입에 TokenLiteral 이라는 메소드를 인터페이스 중 하나로 설정했다. 이제 Node 타입을 갖는 것은 TokenLiteral 이라는 메소드를 반드시 인터페이스를 구현해야 한다. 이렇게 나머지도 Statement, Expression 타입의 인터페이스도 구현했다. Statement는 명령문을, Expression은 표현식에 대한 인터페이스를 의미한다. 이 2개의 인터페이스가 갖는 statementNode() 와 expressionNode() 메소드의 기능은 추후에 소개하기로 하자. 

 

이제 AST 자료구조를 생성하는 시작점 즉, 루트노드를 생성해보도록 하자.

 

// ast/ast.go
type Program struct {
	Statements []Statement
}

func (p *Program) TokenLiteral() string {
	if len(p.Statements) > 0 {
		return p.Statements[0].TokenLiteral()
	} else {
		return ""
	}
}

 

Program 이라는 구조체를 정의했고, 해당 구조체의 멤버로 슬라이스 형태의 Statement 타입의 인터페이스를 정의했다. 즉, 여기에는 이제 여러 개의 명령문들이 들어간다. 일례로, 우리가 위에서 살펴보았던 아래의 let 문들이 들어가는 셈이다. 

 

let x = 5;
let y = 10;
let add = fn(a, b) {
  return a + b;
};

 

다음은 Program 이라는 구조체를 pointer recevier로 하는 메소드인 TokenLiteral을 정의했다. 이 메소드의 역할은 간단하다. Program 이라는 구조체에 명령문들이 들어있으면 가장 첫번째 요소에 있는 Statement 타입 인터페이스의 TokenLiteral 메소드를 재귀적으로 호출하면 된다.(여기서 가장 첫번째 요소로 고정되어 있는 이유는 추후에 알게 된다)

 

AST 생성에 필요한 기초적인 블록인 Program 구조체를 알아보았다. 이제는 정말 let 문을 파싱해보자. 예를 들어, let x = 5; 라는 구문이 있을 때, 어떤 필드가 필요할지 생각해보자. 가장 먼저 x 라는 변수 이름 즉, 식별자를 가리키는 필드가 필요하다. 두 번째로는 등호(=) 오른쪽에 있는 표현식 즉, 5 라는 것을 가리키는 필드가 필요하다. 이 때 주의해야 할 점은 5 라는 리터럴 값 말고도 그 뒤에 무엇인가 더 있는 경우도 커버해야 한다. 예를 들어, let x = 5 * 10 + 12; 이런 식으로도 표현식이 표현될 수 있다. let x = 5 + add(5, 4); 이런 것도 마찬가지이다. 이런 경우도 커버하기 위해서 우리는 (앞서 렉서 구현할 때 자주 살펴보았던) 토큰 필드도 필요하다.

 

따라서, let x = 5; 라는 let 문을 파싱하기 위해서는 [1. 식별자 필드], [2. 표현식 필드], [3. 토큰 필드] 총 3가지가 필요하다. 이를 정의한 소스코드를 살펴보자.

 

// ast/ast.go
package ast

import (
	"monkey/token"
)

type LetStatement struct {
	Token token.Token
	Name  *Identifier
	Value Expression
}

func (ls *LetStatement) statementNode()       {}
func (ls *LetStatement) TokenLiteral() string { return ls.Token.Literal }

type Identifier struct {
	Token token.Token
	Value string
}

func (i *Identifier) expressionNode()      {}
func (i *Identifier) TokenLiteral() string { return i.Token.Literal }

 

가장 먼저 LetStatement 라는 이름의 구조체를 살펴보자. 이름에서 알 수 있듯이 이 구조체가 let 문 1개를 의미한다. 이 구조체가 갖는 멤버들은 총 3가지이다.

 

• Token: [3. 토큰 필드]를 가리키는 필드(복잡한 표현식을 추적하기 위해 필요)
• Name: [1. 식별자]를 가리키는 필드(의 포인터 변수)
• Value: [2. 표현식]을 가리키는 필드

이 LetStatement 구조체는 AST를 구성하는 노드로 들어가면서 명령문에 속하는 노드이기 때문에 Statement 인터페이스를 만족해야 한다. 따라서 statementNode()와 TokenLiteral() 메소드를 인터페이스로 구현하였다.

 

LetStatement 구조체 멤버 중 Name 이라는 멤버는 Identifier 라는 구조체의 포인터 변수로 정의되었다. 이 Identifier 구조체 변수는 무엇인지 위 소스코드에서 살펴보자. 해당 구조체는 Token 멤버와 Value 멤버를 갖는다. 이 구조체에서 주목할 점은 Expression 인터페이스를 만족시키도록 expressionNode()와 TokenLiteral() 메소드를 구현시켰다는 것이다. Identifier 구조체는 '식별자'를 나타내는 것이고, 이는 표현식이 아님에도 왜 표현식이 갖는 노드가 만족시켜야하는 Expression 인터페이스를 구현했을까? 이는 Monkey 언어가 바로 식별자를 선언하고 정의하는 것을 한번에 하여 값을 생성할 수 있기 때문이다. 우리가 계속 예시를 들고 있는 let x = 5; 구문도 식별자를 선언하고 5라는 값을 정의하여 값을 생성한 것이다.

 

지금까지 go 언어로 let 문을 파싱한 결과로 생성되는 AST 자료구조를 도식화하면 아래와 같다.

 

지금까지 만든 AST 자료구조의 도식화

 

이제 파서를 제작하는 소스코드를 살펴보자. 

 

// parser/parser.go
package parser

import (
	"monkey/ast"
	"monkey/lexer"
	"monkey/token"
)

type Parser struct {
	l         *lexer.Lexer
	curToken  token.Token
	peekToken token.Token
}

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

func (p *Parser) nextToken() {
	p.curToken = p.peekToken
	p.peekToken = p.l.NextToken()
}

func (p *Parser) ParseProgram() *ast.Program {
	return nil
}

 

위 소스코드는 렉서를 입력으로 받아서 렉서를 멤버로는 Parser 구조체 변수를 정의하는 것이다. 그리고 주석에도 표시해두었지만 렉서가 토큰화시킨 토큰들을 파서 구조체 멤버인 curToken, peekToken 변수에 최초로 담아내기 위해 2번 nextToken 메소드를 호출한다. 이 nextToken 메소드는 별 것은 아니고, 우리가 이전 포스팅에서 구현한 렉서의 NextToken() 메소드를 호출하는 것이다.(기억이 나지 않는다면 이전 포스팅 참조)

 

그리고 ParseProgram() 이라는 Parser 구조체의 pointer 변수를 receive 하는 메소드는 파싱 후의 결과물인 AST 자료구조를 반환하는 기능을 한다. 지금은 따로 구현한 것이 없기에 곧바로 nil 을 반환하도록 설정했다.

 

렉서를 구현하고 테스트했을 때처럼 파서도 테스트 코드를 작성하고, 우리가 개발하고 있는 파서가 테스트 코드를 통과하는지 살펴보아야 한다. 테스트 코드부터 살펴보자.

 

// parser/parser_test.go
package parser

import (
	"monkey/ast"
	"monkey/lexer"
	"testing"
)

func TestLetStatements(t *testing.T) {
	input := `
let x = 5;
let y = 10;
let foobar = 838383;
`
	// lexer(lexing is not run yet)
	l := lexer.New(input)
	// parser(parsing is not run yet)
	p := New(l)

	program := p.ParseProgram()
	if program == nil {
		t.Fatalf("ParseProgram() returned nill")
	}
	if len(program.Statements) != 3 {
		t.Fatalf("program.Statements does not contain 3 statements. got=%d",
			len(program.Statements))
	}

	tests := []struct {
		expectedIdentifier string
	}{
		{"x"},
		{"y"},
		{"foobar"},
	}

	for i, tt := range tests {
		stmt := program.Statements[i]
		if !testLetStatement(t, stmt, tt.expectedIdentifier) {
			return
		}
	}
}

func testLetStatement(t *testing.T, s ast.Statement, name string) bool {
	if s.TokenLiteral() != "let" {
		t.Errorf("s.TokenLiteral not 'let'. got=%q", s.TokenLiteral())
		return false
	}
    // type assertion(downcast from interface to struct)
	letStmt, ok := s.(*ast.LetStatement)
	if !ok {
		t.Errorf("s not *ast.LetStatement. got=%T", s)
		return false
	}

	if letStmt.Name.Value != name {
		t.Errorf("letStmt.Name.Value not '%s'. got=%s", name, letStmt.Name.Value)
		return false
	}

	if letStmt.Name.TokenLiteral() != name {
		t.Errorf("letStmt.Name.TokenLiteral() not '%s'. got=%s", name, letStmt.Name.TokenLiteral())
		return false
	}
	return true
}

 

input 변수에는 렉싱 및 파싱의 대상이 소스코드 문자열을 정의한다. 그리고 렉서와 파서를 준비한다. tests 변수를 보면 input에 명시한 소스코드 문자열에 맞게끔 x, y , foobar 라는 문자열이 담겨있는 구조체를 정의한다. 즉, 일종의 테스트 기댓값을 미리 사전에 정의하고 우리의 파서가 동작했을 때 기댓값과 일치하는지 보기 위함이다.

 

tests 구조체 길이만큼 루프를 도는데, program 이라는 변수에 정의된 AST 자료구조에 담겨진 명령문 하나씩을 비교하는데 이 때 testLetStatement 함수를 이용해 테스트한다. 이 testLetStatement 함수의 기능을 살펴보자.

 

검사하고 있는 명령문은 Statement 타입에 속하기 때문에 TokenLiteral 메소드가 인터페이스로 구현되어 있을 것이고, 이를 호출함으로써 검사하고 있는 명령문이 'let' 문인지를 먼저 확인한다.

 

다음으로 go 언어에서 Type Assertion 이라는 문법이 등장한다. 즉, 변수 s는 Statement 라는 인터페이스인데, 해당 인터페이스를 LetStatement 라는 이름의 구조체로 downcasting 하는 것이다. 왜냐하면 밑에서 LetStatement 구조체 멤버 변수인 Name에 접근하기 위해서다.

 

LetStatement의 Name 멤버는 Identifier 구조체를 담고 있는데, 먼저 Identifier 구조체의 Value 멤버에 들어있는 값을 확인한다. 이 값에는 식별자(ex. x, y, foobar)가 들어있어야만 한다. 그리고 해당 Identifer 구조체의 TokenLiteral() 메소드를 호출해서 혹시라도 식별자에 표현식이 연결되어 있는지 즉, 토큰이 있는지 확인한다.

 

참고로, 여기서는 LetStatement 구조체의 Value 멤버를 검사하지는 않는데, 추후에 추가될 예정이다. 지금 당장은 let 문 파싱이 동작하는지 여부만 확인하기 위함이라 스킵하였다. 

 

이제 우리만의 파서의 기능을 만들기 위해서 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
}

 

먼저 Program 이라는 구조체를 빈 구조체로 선언 및 정의했다. 위에서 이야기했다시피 Program 이라는 구조체는 파서가 동작하는 결과물인 AST 자료구조를 의미한다. 그리고 Program 구조체에 Statments 라는 멤버가 있는데, 이 멤버에는 Statement 라는 인터페이스가 슬라이스 형태로 정의되는데, 여기에 여러 개의 명령어가 저장된다. 이 Statements 멤버도 빈 슬라이스로 초기화를 수행했다. 그리고 난 뒤, 현재 토큰이 소스코드의 끝(EOF)이 나오기 전까지 파싱을 수행하고, 파싱이 완료된 명령문 노드는 Statements 멤버 즉, 슬라이스에 추가되어 AST 자료구조를 점점 형성해 나가게 된다.

 

이제 위 소스코드의 p.parseStatement() 함수의 소스코드를 살펴볼 차례다.

 

// parser/parser.go

func (p *Parser) parseStatement() ast.Statement {
	switch p.curToken.Type {
	case token.LET:
		return p.parseLetStatement()
	default:
		return nil
	}
}

 

현재 가리키고 있는 토큰이 무엇인지를 보고, 그 토큰에 맞는 파싱 함수를 또 한번 호출한다. 현재 우리는 let 문만을 파싱하는 것을 기능으로 추가하고 있기 때문에 case 구문에 LET에 대한 조건문만 존재한다. 이제 let 문을 실질적으로 파싱하는 역할을 하는 p.parseLetStatment() 함수의 생김새를 살펴볼 차례다.

 

// parser/parser.go

func (p *Parser) parseLetStatement() *ast.LetStatement {
	stmt := &ast.LetStatement{Token: p.curToken}
	
	if !p.expectPeek(token.IDENT) {
		return nil
	}
	
	stmt.Name = &ast.Identifier{Token: p.curToken, Value: p.curToken.Literal}
	
	if !p.expectPeek(token.ASSIGN) {
		return nil
	}
	
	// This time, it is skipped !
	for !p.curTokenIs(token.SEMICOLON) {
		p.nextToken()
	}
	
	return stmt
}

 

let 문을 파싱하는 것이기 때문에 가장 먼저 사전에 정의해놓은 let 문 노드를 생성할 LetStatment 라는 구조체를 정의한다. 이 때 LetStatement 구조체의 Token 멤버에는 현재 토큰인 LET 토큰을 할당하며 선언 및 정의한다. 

 

그리고 p.expectPeek() 라는 함수를 이용해서 IDENT 토큰 즉, 식별자 토큰이 let 토큰 다음에 있을 것을 기대한다. 만약 식별자 토큰이 등장하지 않는다면 nil 을 반환한다. 그러면 expectPeek 함수가 무슨 역할을 하는지 한 번 살펴보자.

 

// parser/parser.go

func (p *Parser) expectPeek(t token.TokenType) bool {
	if p.peekTokenIs(t) {
		p.nextToken()
		return true
	} else {
		return false
	}
}

 

이번엔 또 peekTokenIs 라는 함수가 등장했다. 그러면 또 peekTokenIs 함수 생김새를 보자.

 

// parser/parser.go

func (p *Parser) peekTokenIs(t token.TokenType) bool {
	return p.peekToken.Type == t
}

 

peekTokenIs 함수는 현재 토큰의 다음 위치에 있는 토큰이 해당 함수의 인자로 들어온 토큰과 동일하다면 true를 반환한다. 이제 다시 expectPeek 함수로 돌아가보면, expectPeek 함수의 인자로 들어온 토큰이 다음 위치에 있는 토큰과 일치한다면 현재 위치를 다음 토큰이 있는 위치로 옮긴 후 true를 리턴한다.(주목할 점은 이 '현재 위치를 다음 토큰이 있는 위치로 옮기는' 함수인 p.nextToken() 함수를 호출하는 순간 렉서의 NextToken() 함수를 호출해서 렉싱을 수행한다!!) 이제 다시 위로 올라가서 parseLetStatement() 함수에서 p.expectPeek(token.IDENT) 함수를 해석해보자. 결국, 이 함수는 다음 위치에 있는 토큰이 식별자 토큰이라면 true를, 그렇지 않으면 false를 반환하는 것이다. 그런데 앞에 not 연산(!)이 있으므로 if 구문을 타는 경우는 다음 위치에 있는 토큰이 식별자 토큰이 아닐 경우이다. 결국, 이 함수가 의미하는 바는 let 문 다음에 식별자가 반드시 와야 할 것임을 암시하고, 만약 식별자가 등장하지 않는다면 nil을 반환하도록 한 것이다.

 

계속 parseLetStatement() 함수 로직을 살펴보자. 방금 설명한 if 구문을 타지 않았으면 현재 위치에는 식별자 토큰이 담겨 있는 상태이다. 그렇기 때문에 이제 LetStatement 구조체의 Name 멤버가 Identifer 구조체를 정의한다. 이 Identifer 구조체는 식별자를 의미하므로, 현재 위치의 토큰과 리터럴 값을 할당한다.

 

다음으로 !p.expectPeek(token.ASSIGN) 구문을 보자. 우린 이미 expectPeek 함수의 역할을 살펴보았으므로, 바로 자연스럽게 이해할 수 있다. not 연산까지 포함해서 !p.expectPeek(token.ASSIGN) 을 해석한다고 하면, 해당 if 구문을 타는 경우는 다음 토큰이 등호(=) 토큰이 등장하지 않을 경우이다. 

 

그리고 마지막으로 p.curTokenIs 라는 함수가 등장한다. 이 함수의 생김새도 살펴보자.

 

// parser/parser.go

func (p *Parser) curTokenIs(t token.TokenType) bool {
	return p.curToken.Type == t
}

 

curTokenIs 함수는 peekTokenIs 함수와 거의 동일하다. 다만, 현재 토큰을 살펴보는지, 다음 토큰을 살펴보는지의 차이일 뿐이다. 이 curTokenIs 함수를 사용하는 구문인 !p.curTokenIs(token.SEMICOLON) 을 보면 세미콜론을 만날 때 까지 for 루프를 돌면서 계속 nextToken 함수를 호출한다 .

 

그런데 위 소스코드를 보면 파서가 예상치 못한 토큰이 등장하거나 했을 때 현재는 에러를 따로 내뱉지 않고 있다. 그러므로 에러를 반환하도록 추가해보자.

 

// parser/parser.go

type Parser struct {
	l         *lexer.Lexer
	curToken  token.Token
	peekToken token.Token
	errors    []string
}

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

func (p *Parser) Errors() []string {
	return p.errors
}

func (p *Parser) peekError(t token.TokenType) {
	msg := fmt.Sprintf("expected next token to be %s, got %s instead", t, p.peekToken.Type)
	p.errors = append(p.errors, msg)
}

func (p *Parser) expectPeek(t token.TokenType) bool {
	if p.peekTokenIs(t) {
		p.nextToken()
		return true
	} else {
		p.peekError(t)
		return false
	}
}

 

지금까지 작성했던 코드에 에러 메세지를 담도록 구조체 멤버에 추가했다. 이제 테스트 코드에 해당 에러를 내뱉는 로직을 아래처럼 반영해보자. 아래 코드는 반영된 코드 일부만 작성했다.

 

// parser/parser_test.go

func TestLetStatements(t *testing.T) {
	input := `
let x = 5;
let y = 10;
let foobar = 838383;
`
	// lexer(lexing is not run yet)
	l := lexer.New(input)
	// parser(parsing is not run yet)
	p := New(l)

	program := p.ParseProgram()
	checkParserErrors(t, p)
	if program == nil {
		t.Fatalf("ParseProgram() returned nill")
	}
	...(생략)...
}

func checkParserErrors(t *testing.T, p *Parser) {
	errors := p.Errors()
	if len(errors) == 0 {
		return
	}

	t.Errorf("parser has %d errors", len(errors))
	for _, msg := range errors {
		t.Errorf("parser error: %q", msg)
	}
	t.FailNow()
}

 

이제 아래처럼 일부러 에러를 내뱉도록 인풋 소스코드 문자열을 아래처럼 수정한 후, 테스트 코드를 수행해보자.

 

// parser/parser_test.go

func TestLetStatements(t *testing.T) {
	input := `
let x 5;
let = 10;
let 838383;
`
(...생략...)

 

go test ./parser

 

그러면 다음과 같이 콘솔에 출력이 된다.

 

 

메세지를 보면 등호(=) 토큰을 예상했지만 INT 토큰이 등장했다고 메세지가 나왔다. 이는 위 인풋에서 let x 5; 이 부분에서 파싱 에러가 발생한 것이다. 나머지 메세지는 스스로 한 번 생각해보자.

3. return 문 파싱하기

직전 목차까지의 내용을 학습하면서 우리만의 파서가 let 문을 파싱할 수 있도록 기능을 완성했다. 위에서 구현했던 주요 로직을 토대로 return 문을 파싱해보도록 하자. 우리의 파서가 파싱할 대상인 Monkey 언어의 return 문 예시는 다음과 같다.

 

return 5;
return 10;
return add(15);

 

위 예시코드를 보는 것처럼 return 문의 규칙은 return 이라는 토큰와 표현식, 그리고 세미콜론 형식으로 이루어져 있다.

 

먼저 return 문을 파싱해서 노드로 생성하기 위해 return 구문 노드 구조체를 정의해보자.

 

// ast/ast.go

type ReturnStatement struct {
	Token       token.Token
	ReturnValue Expression
}

func (rs *ReturnStatement) statementNode()       {}
func (rs *ReturnStatement) TokenLiteral() string { return rs.Token.Literal }

 

ReturnStatement 라는 이름의 구조체로 정의했고, 멤버는 return 이라는 토큰을 담을 Token 이라는 멤버와 표현식을 담을 ReturnValue 멤버를 가진다. 그리고 ReturnStatement도 노드의 일종이기 때문에 statementNode() 라는 메소드와 TokenLiteral() 메소드를 정의함으로써 인터페이스를 충족시켰다.

 

이제 다음으로는 return 문을 파싱하기 위한 테스트 코드부터 작성해보자. 그리고 난 뒤에는 테스트 코드에 정의되어 있는 return 문을 파싱하는 함수를 하나씩 살펴보자.

 

// parser/parset_test.go

func TestReturnStatements(t *testing.T) {
	input := `
return 5;
return 10;
return add(15);
`
	l := lexer.New(input)
	p := New(l)

	program := p.ParseProgram()
	checkParserErrors(t, p)

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

	for _, stmt := range program.Statements {
		returnStmt, ok := stmt.(*ast.ReturnStatement) // type assertion: downcast from interface to struct
		if !ok {
			t.Errorf("stmt not *ast.ReturnStatement. got=%T", stmt)
			continue
		}
		if returnStmt.TokenLiteral() != "return" {
			t.Errorf("returnStmt.TokenLiteral not 'return'. got=%s", returnStmt.TokenLiteral())
		}
	}
}

 

로직 자체는 이전에 let 문을 테스트하는 코드와 동일하다. 파싱을 수행하는 트리거는 program := p.ParseProgram() 라인에서 실행된다. 그러면 우리는 이전에 정의했던 p.ParseProgram() 함수에다가도 return 문을 파싱할 수 있도록 수정해주어야 한다. 다시 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.parseStatement() 라는 함수가 호출된다. 그러면 또 우리는 이 함수를 따라가보자.

 

// parser/parser.go

func (p *Parser) parseStatement() ast.Statement {
	switch p.curToken.Type {
	case token.LET:
		return p.parseLetStatement()
	default:
		return nil
	}
}

 

parseStatement() 함수는 현재 위와 같은 생김새를 갖고 있다. 이전에 우리가 작성했던 것처럼 아직은 let 문만 파싱할 수 있도록 되어 있다. 여기에다가 우리는 return 문도 파싱할 수 있도록 추가해주도록 하자.

 

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

 

parseReturnStatement() 라는 함수가 추가되었다. 이번에는 parseReturnStatement() 함수의 생김새를 볼 차례다.

 

// parser/parser.go

func (p *Parser) parseReturnStatement() *ast.ReturnStatement {
	stmt := &ast.ReturnStatement{Token: p.curToken}
	
	p.nextToken()
	
	// This time, it is skipped !
	for !p.curTokenIs(token.SEMICOLON) {
		p.nextToken()
	}
	return stmt
}

 

ReturnStatement 구조체를 정의하는데, 해당 구조체의 Token 멤버에 RETURN 토큰(p.curToken)이 담아준다. 그리고 parseLetStatement() 함수와는 다르게 먼저 p.nextToken() 함수를 호출해주어서 현재 위치를 다음 토큰으로 옮겨준다. 즉, 현재 위치는 return 토큰에 있는데, 이 위치를 return 다음에 있는 표현식으로 옮긴다는 의미이다. 

 

그리고 parseLetStatement() 함수와 마찬가지로 아직은 표현식을 파싱하는 로직을 추가하는 단계는 아니기 때문에 parseReturnStatement() 함수에서도 세미콜론(;) 토큰을 마주할 때까지 계속 토큰을 다음 위치로 옮긴다. 여기까지의 로직을 테스트하기 위해서 테스트 코드를 실행시켜보자.

 

go test ./parser

 

콘솔에 테스트 결과가 ok로 나오면 완성된 것이다. 아직 우리가 만든 파서가 표현식을 파싱할 수 있는 기능은 없는 상태지만, let 문과 return 문을 파싱할 수는 있는 기능까지 갖추었다. 이제 다음 포스팅에서 표현식도 파싱할 수 있는 기능을 탑재해보도록 하자.