close
프로필 배경
프로필 로고

Connecting the dots

Project/밑바닥부터 만드는 인터프리터 in go · 2025. 11. 18. fullscreen 넓게보기

[밑바닥부터 만드는 인터프리터 in go] 2. 파서 동작 원리

파서란?

위키백과에 따르면 컴퓨터 과학에서 파싱(parsing)은 일련의 문자열을 의미있는 토큰(token)으로 분해하고 이들로 이루어진 자료구조를 만드는 과정을 말한다. 자료구조는 파스 트리 또는 추상구문트리일 수 있고, 다른 계층 구조일 수도 있다. 우리가 렉서를 구현하는 과정에서 만들었던 토큰을 어떻게 자료구조로 구성한다는걸까?

 

 

자료구조의 종류

파싱에서 사용할 수 있는 자료구조 중 파스 트리와 추상 구문 트리에 대해 알아보려 한다.

 

Parse Tree란?

파스 트리는 올바른 문장에 대해 트리 구조로 나타낸 것이다.

파스 트리

 

AST(Abstract Syntax Tree)란?

AST는 프로그래밍 언어로 작성된 소스 코드의 추상 구문 구조의 트리이다.

추상 구문 트리(AST)

 

차이점은?

파스 트리는 입력의 모든 것(모든 토큰과 문법 규칙)을 포함하지만, AST는 의미만 추출한다. 파서는 파스 트리를 내부적으로 구성하지만, 최종 결과는 AST로 변환한다.

 

 

왜 '트리' 구조일까?

수많은 자료구조 중 왜 트리일까? 다른 자료구조를 사용할 수 있지 않을까?

 

리스트로는 안 될까?

 

"5 + 3 * 2"를 계산한다고 가정해보자. 우리는 곱셈을 먼저 계산해야 한다. 이런걸 보통 우선순위라고 한다. 리스트로는 우선순위를 어떻게 표현해야 할까?

 

 

시도 1) 순서대로 처리

for i := 0; i < len(tokens); i++ {
	// 순서대로 계산
}

 

1. tokens[0] + tokens[2] = 5 + 3 = 8
2. 8 * tokens[4] = 8 * 2 = 16


결과: 16

 

우선순위가 무시되어 계산된다.

 

 

시도 2) 우선순위 규칙 추가

이번에는 "*" 를 먼저 찾아서 처리해보자.

 

 

그런데 문제가 하나 있다. 계산 결과를 어디에 저장해야 할까? 리스트 중간은 어떻게 수정하지? 만약 "*"이 여러 개가 있다면?

 

 

시도 3) 괄호를 추가하면?

 

만약 리스트에 괄호를 추가한다면, 우선순위를 알 수 있을 것 같다. 근데 괄호 안을 먼저 계산한다는 걸 어떻게 알 수 있을까? 인덱스를 하나씩 찾아다니며 발견해야 할까? 괄호가 중첩될 경우는 어떻게 고려해야 할까? 괄호의 짝은 어떻게 찾지?

 

 

시도 4) 중첩된 표현식

 

표현식이 중첩되었을 경우, 처리 단계는 아래와 같다.

 

1단계: 인덱스 3의 * 처리

2단계: 인덱스 7의 * 처리

3단계: 인덱스 1의 + 처리

4단계: 인덱스 5의 + 처리

 

각 단계마다 리스트 구조가 계속 변하고 있다. 이를 어떻게 추적하지?

 

 

계층 표현 불가

if (x < 5) {
    if (y < 3) {
        return 1;
    }
}

 

최종적으로 리스트는 중첩 계층, 즉 "소속 관계"를 표현할 수 없다.

 

 

추상 구문 트리 변환 과정

리스트로 소속 관계를 표현할 수 없다는 것을 알았으니, 이번에는 트리로 표현해보자.

 

1) 코드 작성

let x = 5;

 

2) 토큰

[LET] [IDENT] [ASSIGN] [INT] [SEMICOLON]

 

3) AST

Program
    |
    | __ LetStatement
               | __ Name: Identifier
               |            | __ value: "x"
               |
               | __ Value: IntegerLiteral
                            | __ value: 5

 

 

변환 과정

Step 1 - 토큰 스트림

 

Step 2 - Let 발견 -> parseLetStatement

LetStatement 노드 생성

LetStatement {
	Token: LET
	Name: nil
	Value: nil
}

 

Step 3 - IDENT 읽기

 

Identifier 노드 생성

LetStatement {
	Token: LET
	Name: Identifier {
    	Value: "x"
        }
	Value: nil
}

 

Step 4 - ASSIGN 확인 후 넘어감

 

Step 5 - Value 파싱 (parseExpression)

Identifier 노드 생성

LetStatement {
	Token: LET
	Name: Identifier { "x" }
	Value: IntegerLiteral {
    	Value: 5
    	}
}

 

Step 6 - 최종 AST

Program
    |
    | __ LetStatement
               | __ Name: Identifier
               |            | __ value: "x"
               |
               | __ Value: IntegerLiteral
                            | __ value: 5

 

 

프랫 파서 (연산 우선순위 구현)

프랫 파서란?

프랫 파서(Pratt Parser)는 1973년 Vaughan Pratt가 고안한 파싱 기법이다. 하향식 파서의 일종으로, Top-Down Operator Precedence Parser라고도 불린다.

 

 

하향식 파서 vs 상향식 파서

하향식 파서

하향식 파서는 위에서 아래로 진행되며, 재귀 하강 파서라고도 불린다.

 

상향식 파서

상향식 파서는 아래에서 위로 진행되며, LR 파서라고도 불린다.

 

이처럼 플랫 파서에는 2가지 종류의 파서가 있는데, 해당 책에서는 하향식 파서를 활용해 파서를 구현한다.

 

 

프랫 파서가 왜 필요할까?

입력값이 "1 + 2 * 3"이 들어온다고 가정해보자. 이를 왼쪽에서 오른쪽으로 읽으면 "(1 + 2) * 3 = 9"이다. 하지만 정답은 "1 + (2 * 3) = 7"이다. 이처럼 '*'의 우선순위(7)가 '+'의 우선순위(5)보다 높으므로, 우선순위가 더 높은 '*'를 먼저 처리해야 한다.

 

 

전위표현식과 중위표현식

프랫 파서에서 전위표현식과 중위표현식 처리는 중요한 핵심 중 하나이다. 프랫 파서는 전위 표현식과 중위표현식을 어떻게 파싱할까?

 

 

전위 표현식 (Prefix Expression)

전위표현식은 연산자가 피연산자 앞에 위치하는 것을 말한다.

 

예시

-5
!true
!false
-x

 

 

전위 표현식 파싱

먼저 전위표현식 파싱 방법에 대해 알아보자. 아래와 같이 입력이 들어왔을 때, 어떻게 파싱이 될까?

 

입력값

-5

 

토큰

[MINUS: "-"] [INT: 5]

 

Step 1 - parseExpression() 호출

prefix 함수를 발견하면 parseExpression()이 parsePrefixExpression()을 호출한다.

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
}

 

Step 2 - 연산자 저장

operator = "-"

 

Step 3 - 오른쪽 파싱

p.nextToken()
parseExpression(PREFIX) 호출
→ 현재 토큰: 5
→ parseIntegerLiteral() 호출
→ return 5

 

Step 4 - AST 생성

return PrefixExpression {
    operator: "-"
    right: 5
}

 

최종 AST

 

중위 표현식 (Infix Expression)

중위표현식은 연산자가 피연산자 사이에 위치하는 것을 말한다.

 

예시

5 + 3
x * y
a - b
10 / 2

 

 

중위 표현식 파싱

 

입력값

5 + 3

 

토큰

[INT: 5] [PLUS: +] [INT: 3]

 

Step 1) prefix 파싱

int 함수를 발견하면 parseExpression()이 parseIntegerLiteral()을 호출한다.

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

	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
}

 

Step 2) infix 확인

다음 토큰이 '+'이므로 Infix 처리를 진행한다.

 

Step 3) infix 처리

infix 함수를 발견하면 parseExpression()이 parseInfixExpression()을 호출한다.

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

	precedence := p.curPrecedence()
	p.nextToken()
	expression.Right = p.parseExpression(precedence)

	return expression
}
 
 

Step 4) 오른쪽 파싱

p.nextToken()을 호출한 이후, parseExpression(5)를 호출한다.

 

int 함수를 발견하면 parseExpression()이 parseIntegerLiteral()을 호출한다.

 
 

Step 5) AST 생성

return InfixExpression {
    left: 5
    operator: "+"
    right: 3
}
 
 

최종 AST

 

 

LBP와 RBP

Binding Power란?

프랫 파서의 핵심은 Binding Power이다. 연산자가 피연산자를 끌어당기는 힘을 숫자로 표현한 것이다.

 

 

LBP (Left Binding Power)

LBP는 "왼쪽 피연산자와 얼마나 강하게 결합하는가?"를 의미한다.

 

var precedences = map[token.TokenType]int{
    token.PLUS:     5,  // + 의 LBP
    token.ASTERISK: 7,  // * 의 LBP
}


실제 동작

1 + 2 * 3

 

Step 1 - '+' 발견

LBP(+) = 5
-> '2'를 끌어당길 수 있는가?
-> 다음 연산자 '*' 확인 필요

 

 

Step 2 - '*' 확인

LBP(*) = 7 > LBP(+) = 5
-> '*'가 결합도가 더 강하다.
- '2'는 '*'에게 끌려감

 

 

RBP (Right Binding Power)

RBP는 오른쪽 표현식을 어디까지 읽을지를 의미한다.


실제 동작

1 + 2 * 3

 

Step 1 - '+' 처리

parseExpression(5) ← RBP = 5
"5보다 높은 우선순위만 계속 읽어라"

 

 

Step 2 - '2' 읽음

다음: * (우선순위 7)
7 > 5? YES → 계속!


Step 3 - '*' 처리

parseExpression(7) ← RBP = 7
"7보다 높은 우선순위만 계속 읽어라"

 

Step 4 - '3' 읽음

다음: EOF (우선순위 -1)
-1 > 7? NO → 중단!

 

 

재귀 호출

아래 코드를 살펴보면 파서 클래스 내에서 재귀 호출을 빈번하게 사용하는 것을 확인할 수 있다.

 

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 (p *Parser) parseInfixExpression(left ast.Expression) ast.Expression {
	expression := &ast.InfixExpression{
		Token:    p.curToken,
		Operator: p.curToken.Literal,
		Left:     left,
	}

	precedence := p.curPrecedence()
	p.nextToken()
	expression.Right = p.parseExpression(precedence) // 재귀 호출

	return expression
}

func (p *Parser) parseExpression(precedence int) ast.Expression {
	defer untrace(trace("parseExpression"))

	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
}

 

이외에도 parseBlockStatement와 parseIfExpression에서 재귀 호출을 사용하고 있다.

 

왜 재귀 호출을 사용할까?

1. 중첩 구조 처리

입력값

(1 + (2 * (3 + 4)))

 

위와 같이 중첩 구조의 입력값이 들어왔을 때, 재귀 없이 처리하는 것은 불가능하다.

 

parseExpression
    → parseGroupedExpression
        → parseExpression // 1 + ...
            → parseInfixExpression
                → parseExpression // (2 * ...)
                    → parseGroupedExpression
                        → parseExpression // 2 * ...
                            // ... 계속

 

 

2. 우선순위 처리

입력값

1 + 2 * 3

 

또한 위와 같이 입력값이 들어왔을 때, 재귀를 통해 우선순위를 처리할 수 있다.

 

parseExpression(0) // + 레벨
    → parseExpression(5) // * 레벨
        → parseExpression(7) // 리프 노드

 

 

정리

파서 구현 과정에서 세 가지 핵심을 확인했다.

 

1. 트리 구조의 필요성

- 리스트는 순서만 표현

- 트리는 계층과 우선순위를 표현

- "소속 관계"를 나타낼 수 있음

 

2. 프랫 파서의 핵심

- 우선순위를 숫자로 표현

- 재귀 호출 시 우선순위 전달

- 높은 우선순위가 더 깊이 파싱됨

 

3. 재귀의 이해

- 우선순위 = 깊이

- precedence가 "문지기"

- 아래에서 위로 트리 구성

 

파서는 토큰의 평면적 나열을 계층적 구조로 변환한다. 이 계층 구조(AST)가 있어야 비로소 코드를 실행할 수 있다.

 

 

전체 코드

ast.go

더보기 
type Node interface {
	TokenLiteral() string
	String() string
}

// 문장 노드를 나타내는 인터페이스 (let, return 등)
type Statement interface {
	Node
	statementNode()
}

// 표현식 노드를 나타내는 인터페이스 (변수, 리터럴, 연산 등)
type Expression interface {
	Node
	expressionNode()
}

// AST의 루트 노드로 모든 문장들을 포함
type Program struct {
	Statements []Statement
}

// Program의 첫 번째 문장의 토큰 리터럴을 반환
func (p *Program) TokenLiteral() string {
	if len(p.Statements) > 0 {
		return p.Statements[0].TokenLiteral()
	} else {
		return ""
	}
}

// Program을 문자열로 변환하여 반환
func (p *Program) String() string {
	var out bytes.Buffer

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

	return out.String()
}

// let 문장을 나타내는 노드 (let x = 5;)
type LetStatement struct {
	Token token.Token
	Name  *Identifier
	Value Expression
}

// LetStatement가 Statement 인터페이스를 만족하도록 하는 마커 메서드
func (ls *LetStatement) statementNode() {}

// LetStatement의 토큰 리터럴을 반환
func (ls *LetStatement) TokenLiteral() string { return ls.Token.Literal }

// LetStatement를 문자열로 변환하여 반환
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()
}

// return 문장을 나타내는 노드
type ReturnStatement struct {
	Token       token.Token
	ReturnValue Expression
}

// ReturnStatement가 Statement 인터페이스를 만족하도록 하는 마커 메서드
func (rs *ReturnStatement) statementNode() {}

// ReturnStatement의 토큰 리터럴을 반환
func (rs *ReturnStatement) TokenLiteral() string { return rs.Token.Literal }

// ReturnStatement를 문자열로 변환하여 반환
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()
}

// 표현식으로 이루어진 문장을 나타내는 노드
type ExpressionStatement struct {
	Token      token.Token
	Expression Expression
}

// ExpressionStatement가 Statement 인터페이스를 만족하도록 하는 마커 메서드
func (es *ExpressionStatement) statementNode() {}

// ExpressionStatement의 토큰 리터럴을 반환
func (es *ExpressionStatement) TokenLiteral() string { return es.Token.Literal }

// ExpressionStatement를 문자열로 변환하여 반환
func (es *ExpressionStatement) String() string {
	if es.Expression != nil {
		return es.Expression.String()
	}
	return ""
}

// 식별자(변수명)를 나타내는 노드
type Identifier struct {
	Token token.Token
	Value string
}

// Identifier가 Expression 인터페이스를 만족하도록 하는 마커 메서드
func (i *Identifier) expressionNode() {}

// Identifier의 토큰 리터럴을 반환
func (i *Identifier) TokenLiteral() string { return i.Token.Literal }

// Identifier를 문자열로 변환하여 반환
func (i *Identifier) String() string {
	return i.Value
}

// 정수 리터럴을 나타내는 노드 (5, 10, 100)
type IntegerLiteral struct {
	Token token.Token
	Value int64
}

// IntegerLiteral이 Expression 인터페이스를 만족하도록 하는 마커 메서드
func (il *IntegerLiteral) expressionNode() {}

// IntegerLiteral의 토큰 리터럴을 반환
func (il *IntegerLiteral) TokenLiteral() string { return il.Token.Literal }

// IntegerLiteral을 문자열로 변환하여 반환 ("5")
func (il *IntegerLiteral) String() string {
	return il.Token.Literal
}

// 전위 연산 표현식을 나타내는 노드 (-5, !true)
type PrefixExpression struct {
	Token    token.Token
	Operator string
	Right    Expression
}

// PrefixExpression이 Expression 인터페이스를 만족하도록 하는 마커 메서드
func (pe *PrefixExpression) expressionNode() {}

// PrefixExpression의 토큰 리터럴을 반환
func (pe *PrefixExpression) TokenLiteral() string { return pe.Token.Literal }

// PrefixExpression을 문자열로 변환하여 반환 ((-5), (!true))
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()
}

// 중위 연산 표현식을 나타내는 노드 (5 + 3, x * y)
type InfixExpression struct {
	Token    token.Token
	Left     Expression
	Operator string
	Right    Expression
}

// InfixExpression이 Expression 인터페이스를 만족하도록 하는 마커 메서드
func (ie *InfixExpression) expressionNode() {}

// InfixExpression의 토큰 리터럴을 반환
func (ie *InfixExpression) TokenLiteral() string { return ie.Token.Literal }

// InfixExpression을 문자열로 변환하여 반환 ((5 + 3), (x * y))
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()
}

// 불리언 리터럴을 나타내는 노드 (true, false)
type Boolean struct {
	Token token.Token
	Value bool
}

// Boolean이 Expression 인터페이스를 만족하도록 하는 마커 메서드
func (b *Boolean) expressionNode() {}

// Boolean의 토큰 리터럴을 반환
func (b *Boolean) TokenLiteral() string {
	return b.Token.Literal
}

// Boolean을 문자열로 변환하여 반환 ("true", "false")
func (b *Boolean) String() string {
	return b.Token.Literal
}

// if 표현식을 나타내는 노드 (if (x < y) { x } else { y })
type IfExpression struct {
	Token token.Token
	Condition Expression
	Consequence *BlockStatement
	Alternative *BlockStatement
}

// IfExpression이 Expression 인터페이스를 만족하도록 하는 마커 메서드
func (ie *IfExpression) expressionNode() {}

// IfExpression의 토큰 리터럴을 반환
func (ie *IfExpression) TokenLiteral() string {
	return ie.Token.Literal
}

// IfExpression을 문자열로 변환하여 반환
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()
}

// 블록 문장을 나타내는 노드 ({ x; y; })
type BlockStatement struct {
	Token token.Token
	Statements []Statement
}

// BlockStatement가 Statement 인터페이스를 만족하도록 하는 마커 메서드
func (bs *BlockStatement) statementNode() {}

// BlockStatement의 토큰 리터럴을 반환
func (bs *BlockStatement) TokenLiteral() string {
	return bs.Token.Literal
}

// BlockStatement를 문자열로 변환하여 반환
func (bs *BlockStatement) String() string {
	var out bytes.Buffer

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

	return out.String()
}

// 함수 리터럴을 나타내는 노드 (fn(x, y) { x + y; })
type FunctionLiteral struct {
	Token token.Token
	Parameters []*Identifier
	Body *BlockStatement
}

// FunctionLiteral이 Expression 인터페이스를 만족하도록 하는 마커 메서드
func (fl *FunctionLiteral) expressionNode() {}

// FunctionLiteral의 토큰 리터럴을 반환
func (fl *FunctionLiteral) TokenLiteral() string {
	return fl.Token.Literal
}

// FunctionLiteral을 문자열로 변환하여 반환 (fn(x, y) { x + y; })
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()
}

// 함수 호출 표현식을 나타내는 노드 (add(1, 2))
type CallExpression struct {
	Token token.Token
	Function Expression
	Arguments []Expression
}

// CallExpression이 Expression 인터페이스를 만족하도록 하는 마커 메서드
func (ce *CallExpression) expressionNode() {}

// allExpression의 토큰 리터럴을 반환
func (ce *CallExpression) TokenLiteral() string {
	return ce.Token.Literal
}

// CallExpression을 문자열로 변환하여 반환 (add(1, 2))
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()
}

 

ast_test.go

더보기 
func TestString(t *testing.T) {
	program := &Program{
		Statements: []Statement{
			&LetStatement{
				Token: token.Token{Type: token.LET, Literal: "let"},
				Name: &Identifier{
					Token: token.Token{Type: token.IDENT, Literal: "myVar"},
					Value: "myVar",
				},
				Value: &Identifier{
					Token: token.Token{Type: token.IDENT, Literal: "anotherVar"},
					Value: "anotherVar",
				},
			},
		},
	}

	if program.String() != "let myVar = anotehrVar;" {
		t.Errorf("program.String() wrong. got=%q", program.String())
	}
}

 

parser.go

더보기 
const (
	_ int = iota
	LOWEST
	EQUALS      // ==
	LESSGREATER // > 또는 <
	SUM         // +
	PRODUCT     // *
	PREFIX      // -X 또는 !X
	CALL        // myFunction(X)
)

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

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

// 토큰을 읽어 AST를 생성하는 파서
type Parser struct {
	l      *lexer.Lexer
	errors []string

	curToken  token.Token
	peekToken token.Token

	prefixParseFns map[token.TokenType]prefixParseFn
	infixParseFns  map[token.TokenType]infixParseFn
}

// 렉서를 받아 새로운 파서를 생성하고 초기화
func New(l *lexer.Lexer) *Parser {
	p := &Parser{
		l:      l,
		errors: []string{},
	}

	p.nextToken()
	p.nextToken()

	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.registerPrefix(token.TRUE, p.parseBoolean)
	p.registerPrefix(token.FALSE, p.parseBoolean)
	p.registerPrefix(token.LPAREN, p.parseGroupedExpression)
	p.registerPrefix(token.IF, p.parseIfExpression)
	p.registerPrefix(token.FUNCTION, p.parseFunctionalLiteral)

	p.infixParseFns = make(map[token.TokenType]infixParseFn)
	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)
	p.registerInfix(token.LPAREN, p.parseCallExpression)

	return p
}

// 현재 토큰을 다음 토큰으로 전진
func (p *Parser) nextToken() {
	p.curToken = p.peekToken
	p.peekToken = p.l.NextToken()
}

// 현재 토큰이 주어진 타입과 일치하는지 확인
func (p *Parser) curTokenIs(t token.TokenType) bool {
	return p.curToken.Type == t
}

// 다음 토큰이 주어진 타입과 일치하는지 확인
func (p *Parser) peekTokenIs(t token.TokenType) bool {
	return p.peekToken.Type == t
}

// 다음 토큰이 기대하는 타입이면 토큰을 전진시키고 true 반환
func (p *Parser) expectPeek(t token.TokenType) bool {
	if p.peekTokenIs(t) {
		p.nextToken()
		return true
	} else {
		p.peekError(t)
		return false
	}
}

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) noPrefixParseFnError(t token.TokenType) {
	msg := fmt.Sprintf("no prefix parse function for %s found", t)
	p.errors = append(p.errors, msg)
}

// 전체 프로그램을 파싱하여 AST를 생성
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
}

// 현재 토큰의 타입에 따라 적절한 문장 파싱 함수 호출
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()
	}
}

// let 문장을 파싱하여 LetStatement 노드 생성 (let x = 5;)
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
	}
	
	p.nextToken()

	stmt.Value = p.parseExpression(LOWEST)

	if p.peekTokenIs(token.SEMICOLON) {
		p.nextToken()
	}

	return stmt
}

// return 문장을 파싱하여 ReturnStatement 노드 생성 (return 5;)
func (p *Parser) parseReturnStatement() *ast.ReturnStatement {
	stmt := &ast.ReturnStatement{Token: p.curToken}

	p.nextToken()

	stmt.ReturnValue = p.parseExpression(LOWEST)

	if p.peekTokenIs(token.SEMICOLON) {
		p.nextToken()
	}

	return stmt
}

// 표현식 문장을 파싱하여 ExpressionStatement 노드 생성 (x + 5;)
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
}

// 주어진 우선순위로 표현식을 파싱 (프랫 파서의 핵심)
func (p *Parser) parseExpression(precedence int) ast.Expression {
	defer untrace(trace("parseExpression"))

	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
}

// 다음 토큰의 우선순위를 반환
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
}

// 식별자를 파싱하여 Identifier 노드 생성 (x, foo)
func (p *Parser) parseIdentifier() ast.Expression {
	return &ast.Identifier{Token: p.curToken, Value: p.curToken.Literal}
}

// 정수 리터럴을 파싱하여 IntegerLiteral 노드 생성
func (p *Parser) parseIntegerLiteral() ast.Expression {
	lit := &ast.IntegerLiteral{Token: p.curToken}

	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
}

// 전위 연산 표현식을 파싱하여 PrefixExpression 노드 생성 (-5, !true)
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
}

// 중위 연산 표현식을 파싱하여 InfixExpression 노드 생성 (5 + 3, x * y)
func (p *Parser) parseInfixExpression(left ast.Expression) ast.Expression {
	expression := &ast.InfixExpression{
		Token:    p.curToken,
		Operator: p.curToken.Literal,
		Left:     left,
	}

	precedence := p.curPrecedence()
	p.nextToken()
	expression.Right = p.parseExpression(precedence)

	return expression
}

// 불리언 리터럴을 파싱하여 Boolean 노드 생성 (true, false)
func (p *Parser) parseBoolean() ast.Expression {
	return &ast.Boolean{Token: p.curToken, Value: p.curTokenIs(token.TRUE)}
}

// 괄호로 묶인 표현식을 파싱 ((5 + 5))
func (p *Parser) parseGroupedExpression() ast.Expression {
	p.nextToken()

	exp := p.parseExpression(LOWEST)

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

	return exp
}

// if-else 표현식을 파싱하여 IfExpression 노드 생성
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
}

// 블록 문장을 파싱하여 BlockStatement 노드 생성 ({ x; y; })
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
}

// 함수 리터럴을 파싱하여 FunctionLiteral 노드 생성 (fn(x, y) { x + y; })
func (p *Parser) parseFunctionalLiteral() 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
}

// 함수 매개변수 목록을 파싱 ((x, y, z))
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
}

// 함수 호출 표현식을 파싱하여 CallExpression 노드 생성 (add(1, 2))
func (p *Parser) parseCallExpression(function ast.Expression) ast.Expression {
	exp := &ast.CallExpression{Token: p.curToken, Function: function}
	exp.Arguments = p.parseCallArguments()
	return exp
}

// 함수 호출 인자 목록을 파싱 ((1, 2, 3))
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
}

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
}

 

parser_test.go

더보기 
func TestLetStatements(t *testing.T) {
	tests := []struct {
		input        string
		expectedIdentifier     string
		expectedValue interface{}
	}{
		{"let x = 5;", "x", 5},
		{"let y = true;", "y", true},
		{"let foobar = y;", "foobar", "y"},
	}	

	for _, tt := range tests {
		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 := program.Statements[0]
		if !testLetStatement(t, stmt, tt.expectedIdentifier) {
			return
		}

		val := stmt.(*ast.LetStatement).Value
		if !testLiteralExpression(t, val, tt.expectedValue) {
			return
		}
	}
}

func TestReturnStatements(t *testing.T) {
	input := `
	return 5;
	return 10;
	return 993322;
	`

	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)
		if !ok {
			t.Errorf("stmt not *ast.ReturnStatement. got=%T", stmt)
			continue
		}
		if returnStmt.TokenLiteral() != "return" {
			t.Errorf("returnStmt.TokenLiteral not 'return', got %q", returnStmt.TokenLiteral())
		}
	}
}

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

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

	if len(program.Statements) != 1 {
		t.Fatalf("program has not enough 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])
	}

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

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 has not enough 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])
	}

	literal, ok := stmt.Expression.(*ast.IntegerLiteral)
	if !ok {
		t.Fatalf("exp not *ast.IntegerLiteral. got=%T", stmt.Expression)
	}
	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())
	}
}

func TestParsingPrefixExpressions(t *testing.T) {
	prefixTests := []struct {
		input        string
		operator     string
		value interface{}
	}{
		{"!5;", "!", 5},
		{"-15", "-", 15},
		{"!true;", "!", true},
		{"!false", "!", false},
	}

	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 %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.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 !testLiteralExpression(t, exp.Right, tt.value) {
			return
		}
	}
}

func TestParsingInfixExpressions(t *testing.T) {
	infixTests := []struct {
		input      string
		leftValue  interface{}
		operator   string
		rightValue interface{}
	}{
		{"5 + 5;", 5, "+", 5},
		{"5 - 5;", 5, "-", 5},
		{"5 * 5;", 5, "*", 5},
		{"5 / 5;", 5, "/", 5},
		{"5 > 5;", 5, ">", 5},
		{"5 < 5;", 5, "<", 5},
		{"5 == 5;", 5, "==", 5},
		{"5 != 5;", 5, "!=", 5},
		{"true == true", true, "==", true},
		{"true != false", true, "!=", false},
		{"false == false", false, "==", false},
	}

	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 %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.InfixExpression)
		if !ok {
			t.Fatalf("exp is not as.InfixExpression. got=%T", stmt.Expression)
		}

		if !testLiteralExpression(t, exp.Left, tt.leftValue) {
			return
		}

		if exp.Operator != tt.operator {
			t.Fatalf("exp.Opreator is not '%s'. got=%s", tt.operator, exp.Operator)
		}

		if !testLiteralExpression(t, exp.Right, tt.rightValue) {
			return
		}

		if !testInfixExpression(t, stmt.Expression, tt.leftValue, tt.operator, tt.rightValue) {
			return
		}
	}
}

func TestOperatorPrecedenceParsing(t *testing.T) {
	tests := []struct {
		input string
		expected string
	}{
		{
			"-a * b",
			"((-a) * b)",
		},
		{
			"!-a",
			"(!(-a))",
		},
		{
			"a + b + c",
			"((a + b) + c)",
		},
		{
			"a + b - c",
			"((a + b) - c)",
		},
		{
			"a * b * c",
			"((a * b) * c)",
		},
		{
			"a * b / c",
			"((a * b) / c)",
		},
		{
			"a + b / c",
			"(a + (b / c))",
		},

		{
			"a + b * c + d / e - f",
			"(((a + (b * c)) + (d / e)) - f)",
		},
		{
			"3 + 4; -5 * 5",
			"(3 + 4)((-5) * 5)",
		},
		{
			"5 > 4 == 3 < 4",
			"((5 > 4) == (3 < 4))",
		},
		{
			"5 < 4 != 3 > 4",
			"((5 < 4) != (3 > 4))",
		},
		{
			"3 + 4 * 5 == 3 * 1 + 4 * 5",
			"((3 + (4 * 5)) == ((3 * 1) + (4 * 5)))",
		},
		{
			"true",
			"true",
		},
		{
			"false",
			"false",
		},
		{
			"3 > 5 == false",
			"((3 > 5) == false)",
		},
		{
			"3 < 5 == true",
			"((3 < 5) == true)",
		},
		{
			"1 + (2 + 3) + 4",
			"((1 + (2 + 3)) + 4)",
		},
		{
			"(5 + 5) * 2",
			"((5 + 5) * 2)",
		},
		{
			"2 / (5 + 5)",
			"(2 / (5 + 5))",
		},
		{
			"-(5 + 5)",
			"(-(5 + 5))",
		},
		{
			"!(true == true)",
			"(!(true == true))",
		},
		{
			"a + add(b * c) + d",
			"((a + add((b * c))) + d)",
		},
		{
			"add(a, b, 1, 2 * 3, 4 + 5, add(6, 7 * 8))",
			"add(a, b, 1, (2 * 3), (4 + 5), add(6, (7 * 8)))",
		},
		{
			"add(a + b + c * d / f + g)",
			"add((((a + b) + ((c * d) / f)) + g))",
		},
	}

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

func TestBooleanExpression(t *testing.T) {
	tests := []struct {
		input           string
		expectedBoolean bool
	}{
		{"true;", true},
		{"false;", false},
	}

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

		if len(program.Statements) != 1 {
			t.Fatalf("program has not enough 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])
		}

		boolean, ok := stmt.Expression.(*ast.Boolean)
		if !ok {
			t.Fatalf("exp not *ast.Boolean. got=%T", stmt.Expression)
		}
		if boolean.Value != tt.expectedBoolean {
			t.Errorf("boolean.Value not %t. got=%t", tt.expectedBoolean,
				boolean.Value)
		}
	}
}

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 %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", 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 TestFunctionalLiteralParsing(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")
}

func TestFunctionalParameterParsing(t *testing.T) {
	tests := []struct {
		input string
		expectedParams []string
	}{
		{input: "fn() {};", expectedParams: []string{}},
		{input: "fn(x) {};", expectedParams: []string{"x"}},
		{input: "fn(x, y, z) {};", expectedParams: []string{"x", "y", "z"}},
	}

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

		stmt := program.Statements[0].(*ast.ExpressionStatement)
		function := stmt.Expression.(*ast.FunctionLiteral)

		if len(function.Parameters) != len(tt.expectedParams) {
			t.Errorf("length parameters wrong. wnat %d, got=%d\n", len(tt.expectedParams), len(function.Parameters))
		}

		for i, ident := range tt.expectedParams {
			testLiteralExpression(t, function.Parameters[i], ident)
		}
	}
}

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

func testLetStatement(t *testing.T, stmt ast.Statement, name string) bool {
	if stmt.TokenLiteral() != "let" {
		t.Errorf("s.TokenLiteral not 'let'. got=%q", stmt.TokenLiteral())
		return false
	}
	letStmt, ok := stmt.(*ast.LetStatement)
	if !ok {
		t.Errorf("s not *ast.LetStatement. got=%T", stmt)
		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
}

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
}

func testIdentifier(t *testing.T, exp ast.Expression, value string) bool {
	ident, ok := exp.(*ast.Identifier)
	if !ok {
		t.Errorf("exp not *ast.Identifier. got=%T", exp)
		return false
	}

	if ident.Value != value {
		t.Errorf("ident.Value not %s. got=%s", value, ident.Value)
		return false
	}

	if ident.TokenLiteral() != value {
		t.Errorf("ident.TokenLiteral not %s. got=%s", value, ident.TokenLiteral())
		return false
	}
	return true
}

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
}

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", expected)
	return false
}

func testInfixExpression(t *testing.T, exp ast.Expression, left interface{}, operator string, right interface{}) bool {
	opExp, ok := exp.(*ast.InfixExpression)
	if !ok {
		t.Errorf("exp is not ast.InfixExpression. got=%T(%s)", exp, exp)
		return false
	}

	if !testLiteralExpression(t, opExp.Left, left) {
		return false
	}

	if opExp.Operator != operator {
		t.Errorf("exp.Operator is not '%s'. got=%q", operator, opExp.Operator)
		return false
	}

	if !testLiteralExpression(t, opExp.Right, right) {
		return false
	}

	return true
}

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

 

 

참고 자료

https://ko.wikipedia.org/wiki/%ED%8C%8C%EC%8A%A4_%ED%8A%B8%EB%A6%AC

 

파스 트리 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 파스 트리(parse tree), 파싱 트리(parsing tree)[1], 어원 트리(derivation tree), 구체적인 구문 트리(concrete syntax tree)는 올바른 문장에 대해 트리 구조로 나타낸 것을 말한

ko.wikipedia.org

 

https://ko.wikipedia.org/wiki/%EC%B6%94%EC%83%81_%EA%B5%AC%EB%AC%B8_%ED%8A%B8%EB%A6%AC

 

추상 구문 트리 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 유클리드 호제법을 사용하여 다음의 코드를 나타낸 추상 구문 트리: while b ≠ 0 if a > b a := a − b else b := b − a return a 컴퓨터 과학에서 추상 구문 트리(abstract sy

ko.wikipedia.org

 

아래 링크를 클릭하면 책의 전체 코드를 다운받을 수 있다.

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

저작자표시 (새창열림)

'Project > 밑바닥부터 만드는 인터프리터 in go' 카테고리의 다른 글

[밑바닥부터 만드는 인터프리터 in go] 3. 평가기 동작 원리  (0) 2025.11.19
[밑바닥부터 만드는 인터프리터 in go] 1. 렉서 동작 원리  (0) 2025.11.16
Project/밑바닥부터 만드는 인터프리터 in go 관련 글
더 보기

티스토리툴바