[새김 언어 제작기] Part 2 - 파서의 함정들 (feat. 연산자와 출력 함수)

들어가며

Part 1에서 한글 토큰화에 성공했다.

https://jihyun-devstory.tistory.com/90

[새김 언어 제작기] Part 1 - 한글 처리 (feat. 유니코드와 렉서)

 

이제 이 토큰들을 실제로 실행 가능한 프로그램으로 만들어야 한다. 이번 편에서는 파서와 평가기를 구현하며 마주친 2가지 주요 문제를 다룬다.

 

1. >= 연산자 쪼개짐 문제
2. 출력 함수 설계 문제

 

---

 

초기 Parser 정의

우선 기존에 만들었던 인터프리터 코드를 참고해, 정의했던 토큰 범위를 동작시키기 위한 ast(추상 구문 트리)와 parser를 정의했다. 해당 내용은 이전 시리즈에서 자세히 다루었다.

 

https://jihyun-devstory.tistory.com/83

[밑바닥부터 인터프리터 만들기 with go] 2. 파서 구현하기

 

ast.go

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

type Statement interface {
	Node
	statementNode()
}

type Expression interface {
	Node
	expressionNode()
}

type Program struct {
	Statements []Statement
}

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

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

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

	return out.String()
}

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

func (variable *VariableStatement) statementNode() {}

func (variable *VariableStatement) TokenLiteral() string {
	return variable.Token.Literal
}

func (variable *VariableStatement) String() string {
	var out bytes.Buffer

	out.WriteString(variable.Token.Literal + " ")
	out.WriteString(variable.Name.String())
	out.WriteString(" = ")

	if variable.Value != nil {
		out.WriteString(variable.Value.String())
	}

	out.WriteString(";")
	return out.String()
}

type ExpressionStatement struct {
	Token token.Token
	Expression Expression
}

func (expression *ExpressionStatement) statementNode() {}

func (expression *ExpressionStatement) TokenLiteral() string {
	return expression.Token.Literal
}

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

type Identifier struct {
	Token token.Token
	Value string
}

func (identifier *Identifier) expressionNode() {}

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

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

type IntegerLiteral struct {
	Token token.Token
	Value int64
}

func (integerLiteral *IntegerLiteral) expressionNode() {}

func (integerLiteral *IntegerLiteral) TokenLiteral() string {
	return integerLiteral.Token.Literal
}

func (integerLiteral *IntegerLiteral) String() string {
	return integerLiteral.Token.Literal
}

 

parser.go

 

type Parser struct {
	lexer *lexer.Lexer
	errors []string

	currentToken token.Token
	peekToken token.Token
}

func New(lexer *lexer.Lexer) *Parser {
	parser := &Parser{
		lexer: lexer,
		errors: []string{},
	}

	parser.nextToken()
	parser.nextToken()

	return parser
}

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

	for parser.currentToken.Type != token.EOF {
		statement := parser.parseStatement()
		if statement != nil {
			program.Statements = append(program.Statements, statement)
		}
		parser.nextToken()
	}

	return program
}

func (parser *Parser) nextToken() {
	parser.currentToken = parser.peekToken
	parser.peekToken = parser.lexer.NextToken()
}

func (parser *Parser) parseStatement() ast.Statement {
	switch parser.currentToken.Type {
	case token.VARIABLE:
		return parser.parseVariableStatement()
	default:
		return parser.parseExpressionStatement()
	}
}

func (parser *Parser) parseVariableStatement() *ast.VariableStatement {
	statement := &ast.VariableStatement{Token: parser.currentToken}

	if !parser.expectPeek(token.IDENT) {
		return nil
	}

	statement.Name = &ast.Identifier{
		Token: parser.currentToken,
		Value: parser.currentToken.Literal,
	}

	if !parser.expectPeek(token.ASSIGN) {
		return nil
	}

	parser.nextToken()

	statement.Value = parser.parseIntegerLiteral()

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

	return statement
}

func (parser *Parser) parseExpressionStatement() *ast.ExpressionStatement{
	statement := &ast.ExpressionStatement{Token: parser.currentToken}
	statement.Expression = parser.parseExpression()

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

	return statement
}

func (parser *Parser) parseExpression() ast.Expression {
	switch parser.currentToken.Type {
	case token.IDENT:
		return &ast.Identifier{
			Token: parser.currentToken,
			Value: parser.currentToken.Literal,
		}
	case token.INT:
		return parser.parseIntegerLiteral()
	default:
		return nil
	}
}

func (parser *Parser) parseIntegerLiteral() ast.Expression {
	integerLiteral := &ast.IntegerLiteral{Token: parser.currentToken}

	value, err := strconv.ParseInt(parser.currentToken.Literal, 0, 64)
	if err != nil {
		message := fmt.Sprintf("could not parse %q as integer", parser.currentToken.Literal)
		parser.errors = append(parser.errors, message)
		return nil
	}

	integerLiteral.Value = value

	return integerLiteral
}

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

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

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

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

 

parser_test.go

func TestVariableStatements(t *testing.T) {
    input := `
	변수 생년월일 = 20010101;
	변수 나이 = 25;
	`
    
    l := lexer.New(input)
    p := New(l)
    
    program := p.ParseProgram()
    checkParserErrors(t, p)
    
    if len(program.Statements) != 2 {
        t.Fatalf("program.Statements does not contain 2 statements. got=%d",
            len(program.Statements))
    }
    
    tests := []struct {
        expectedIdentifier string
    }{
        {"생년월일"},
        {"나이"},
    }
    
    for i, tt := range tests {
        stmt := program.Statements[i]
        if !testVariableStatement(t, stmt, tt.expectedIdentifier) {
            return
        }
    }
}

func testVariableStatement(t *testing.T, s ast.Statement, name string) bool {
    if s.TokenLiteral() != "변수" {
        t.Errorf("s.TokenLiteral not '변수'. got=%q", s.TokenLiteral())
        return false
    }
    
    varStmt, ok := s.(*ast.VariableStatement)
    if !ok {
        t.Errorf("s not *ast.VariableStatement. got=%T", s)
        return false
    }
    
    if varStmt.Name.Value != name {
        t.Errorf("varStmt.Name.Value not '%s'. got=%s", name, varStmt.Name.Value)
        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()
}

 

---

 

문제 1 - 연산자 쪼개짐

조건문을 구현하기 위해 비교 연산자를 추가하던 중, 문제가 발생했다.

 

입력: 점수 >= 90
원하는 토큰: 점수, >=, 90
실제 토큰: 점수, >, =, 90

 

'>=' 연산자가 '>' 와 '=' 로 쪼개지는 문제였다.

 

원인 분석

렉서가 한 글자씩 읽기 때문에 발생한 문제였다.

case '>':
    tok = newToken(token.GT, '>') // 여기서 토큰 반환
    // 다음 문자 '='를 확인하지 못함

 

미리 읽기 구현

"다음 글자를 미리 봐야겠다"는 생각이 들었다. 그래야 '>=' 또는 '<='가 들어왔을 때 이를 읽을 수 있기 때문이다.

func (lexer *Lexer) peekChar() rune {
    if lexer.readPosition >= len(lexer.input) {
        return 0
    }
    return lexer.input[lexer.readPosition]
}

 

이제 NextToken() 함수에서 다음 문자를 확인할 수 있다.

case '>':
    if lexer.peekChar() == '=' {
        ch := lexer.character
        lexer.readChar()
        tok = token.Token{
            Type: token.GTE,
            Literal: string(ch) + string(lexer.character),
        }
    } else {
        tok = newToken(token.GT, lexer.character)
    }

 

실행 결과

입력: 점수 >= 90
토큰: 점수, >=, 90

 

---

 

2자 연산자 추가

같은 방식으로 '<=', '==', '!=' 연산자도 구현했다.

case '<':
    if lexer.peekChar() == '=' {
        ch := lexer.character
        lexer.readChar()
        tok = token.Token{Type: token.LTE, Literal: "<="}
    } else {
        tok = newToken(token.LT, lexer.character)
    }

case '=':
    if lexer.peekChar() == '=' {
        ch := lexer.character
        lexer.readChar()
        tok = token.Token{Type: token.EQ, Literal: "=="}
    } else {
        tok = newToken(token.ASSIGN, lexer.character)
    }

case '!':
    if lexer.peekChar() == '=' {
        ch := lexer.character
        lexer.readChar()
        tok = token.Token{Type: token.NOT_EQ, Literal: "!="}
    } else {
        tok = newToken(token.BANG, lexer.character)
    }

 

---

 

문제 2 - 출력 함수 설계

첫 번째 시도 - 키워드로 등록

출력 기능을 구현하기 위해 출력을 키워드로 등록했다.

const (
    VARIABLE = "VARIABLE"
    IF = "IF"
    PRINT = "PRINT" // 키워드로 추가
)

var keywords = map[string]TokenType{
    "변수": VARIABLE,
    "만약": IF,
    "출력": PRINT,
}

 

하지만 파서에서 오류가 발생했다.

no prefix parse function for PRINT found

 

원인 분석

문제를 분석한 결과, 키워드와 함수의 차이를 이해하지 못했던 것이 원인이었다.

"변수" → statement (문)
"만약" → statement (문)
"출력" → expression (식), 함수 호출!

 

출력(메시지)는 함수 호출이므로 expression으로 처리되어야 한다. 하지만 키워드로 등록하면 파서가 statement로 인식하려 해서 prefix parse function을 찾지 못한 것이다.

 

---

 

두 번째 시도 - 내장 함수로 변경

위 내용을 통해 "출력은 함수다"라는 점을 알게 되었다. 따라서 내장 함수(builtin function)로 재설계했다.

 

1. 토큰 추가

const (
    // 기존 토큰들
    STRING = "STRING" // 문자열 토큰 추가
)

// keywords에서 "출력" 제거
var keywords = map[string]TokenType{
    "변수": VARIABLE,
    "만약": IF,
    "아니면": ELSE,
    "참": TRUE,
    "거짓": FALSE,
    "함수": FUNCTION,
    "반환": RETURN,
    // "출력": PRINT, 삭제
}

 

2. 렉서 수정 (문자열 지원)

func (lexer *Lexer) NextToken() token.Token {
    var tok token.Token

    lexer.skipWhitespace()

    switch lexer.character {
    // 기존 케이스들
    
    case '"': // 문자열 처리 추가
        tok.Type = token.STRING
        tok.Literal = lexer.readString()
        return tok
    }

    lexer.readChar()
    return tok
}

func (lexer *Lexer) readString() string {
    position := lexer.position + 1
    for {
        lexer.readChar()
        if lexer.character == '"' || lexer.character == 0 {
            break
        }
    }
    return string(lexer.input[position:lexer.position])
}

 

3. AST 노드 추가

// StringLiteral - 문자열 리터럴
type StringLiteral struct {
	Token token.Token
	Value string
}

func (stringLiteral *StringLiteral) expressionNode() {}

func (stringLiteral *StringLiteral) TokenLiteral() string {
	return stringLiteral.Token.Literal
}

func (stringLiteral *StringLiteral) String() string {
	return stringLiteral.Token.Literal
}

 

4. 파서 수정

func New(lexer *lexer.Lexer) *Parser {
    parser := &Parser{
        lexer: lexer,
        errors: []string{},
    }

    parser.nextToken()
    parser.nextToken()

    parser.prefixParseFns = make(map[token.TokenType]prefixParseFn)
    parser.infixParseFns = make(map[token.TokenType]infixParseFn)

    parser.registerPrefix(token.INT, parser.parseIntegerLiteral)
    parser.registerPrefix(token.IDENT, parser.parseIdentifier)
    parser.registerPrefix(token.STRING, parser.parseStringLiteral) // 추가
    // 나머지 코드들

    return parser
}

func (parser *Parser) parseStringLiteral() ast.Expression {
    return &ast.StringLiteral{
        Token: parser.currentToken,
        Value: parser.currentToken.Literal,
    }
}

 

 

5. Object 추가

const (
    INTEGER_OBJ = "INTEGER"
    BOOLEAN_OBJ = "BOOLEAN"
    NULL_OBJ = "NULL"
    ERROR_OBJ = "ERROR"
    RETURN_VALUE_OBJ = "RETURN_VALUE"
    FUNCTION_OBJ = "FUNCTION"
    STRING_OBJ = "STRING" // 추가
    BUILTIN_OBJ = "BUILTIN" // 추가
)

// 문자열 객체
type String struct {
    Value string
}

func (s *String) Type() ObjectType { return STRING_OBJ }
func (s *String) Inspect() string  { return s.Value }

// 내장 함수
type BuiltinFunction func(args ...Object) Object

type Builtin struct {
    Fn BuiltinFunction
}

func (b *Builtin) Type() ObjectType { return BUILTIN_OBJ }
func (b *Builtin) Inspect() string  { return "builtin function" }

 

6. 평가기 수정

// 내장 함수 정의
var builtins = map[string]*object.Builtin{
    "출력": &object.Builtin{
        Fn: func(args ...object.Object) object.Object {
            for _, arg := range args {
                fmt.Println(arg.Inspect())
            }
            return NULL
        },
    },
}

// Eval() 함수에 문자열 처리 추가
func Eval(node ast.Node, environment *object.Environment) object.Object {
    switch node := node.(type) {
    // 기존 케이스들
    
    case *ast.StringLiteral:  // 추가!
        return &object.String{Value: node.Value}
    
    // 나머지 케이스들
    }

    return NULL
}

// evalIdentifier() 함수에 내장 함수 조회 추가
func evalIdentifier(node *ast.Identifier, environment *object.Environment) object.Object {
    // 변수 조회
    if val, ok := environment.Get(node.Value); ok {
        return val
    }
    
    // 내장 함수 조회
    if builtin, ok := builtins[node.Value]; ok {
        return builtin
    }
    
    return newError("identifier not found: " + node.Value)
}

// applyFunction() 함수에 내장 함수 처리 추가
func applyFunction(fn object.Object, arguments []object.Object) object.Object {
    switch fn := fn.(type) {
    
    case *object.Function:  // 사용자 정의 함수
        extendedEnv := extendFunctionEnv(fn, arguments)
        evaluated := Eval(fn.Body, extendedEnv)
        return unwrapReturnValue(evaluated)
    
    case *object.Builtin:  // 내장 함수
        return fn.Fn(arguments...)
    
    default:
        return newError(fmt.Sprintf("not a function: %s", fn.Type()))
    }
}

 

테스트

func TestStringLiteral(t *testing.T) {
    input := `"안녕하세요"`
    
    evaluated := testEval(input)
    str, ok := evaluated.(*object.String)
    if !ok {
        t.Fatalf("object is not String. got=%T (%+v)", evaluated, evaluated)
    }
    
    if str.Value != "안녕하세요" {
        t.Errorf("String has wrong value. got=%q", str.Value)
    }
}

func TestBuiltinFunctions(t *testing.T) {
    tests := []struct {
        input    string
        expected interface{}
    }{
        {`출력(25)`, nil},
        {`출력("안녕")`, nil},
    }
    
    for _, tt := range tests {
        testEval(tt.input)
    }
}

 

위와 같이 코드를 수정했지만, 테스트가 실패했다.

% go test ./evaluator
--- FAIL: TestStringLiteral (0.00s)
    evaluator_test.go:149: String has wrong value. got=""

 

 

렉서의 NextToken()에 문자열 처리를 추가하지 않아 발생한 오류였다.

case '"':
    tok.Type = token.STRING
    tok.Literal = lexer.readString()

 

수정 후 테스트가 통과했다!

% go test ./evaluator
ok github.com/Jihyun3478/saegim-lang/evaluator 0.401s

 

---

 

토큰 타입 설계

구현하면서 토큰 타입 정의에 대한 혼동도 있었다.

 

초기 설계

const (
    PLUS = "PLUS"
    MINUS = "MINUS"
)

 

올바른 설계

const (
    PLUS = "+"
    MINUS = "-"
)

 

이유

• Type: 토큰의 종류 (PLUS, MINUS 등)
• Literal: 실제 문자열 ("+", "-" 등)

type Token struct {
    Type    TokenType // "PLUS"가 아닌 상수
    Literal string // "+"
}

 

 

Type을 "PLUS"로 하면 Literal과 혼동되어 디버깅이 어려워진다. 따라서 위와 같이 수정해야 한다.

 

 

---

 

정리

프로그래밍 언어를 만들면서 우리가 매일 사용하는 >= 연산자, System.out.println() 함수가 얼마나 많은 고민 끝에 설계되었는지 이해하게 되었다. "작동한다"가 아닌 "왜 작동하는가"를 이해할 수 있었다.

 

---

 

다음 편 예고

드디어 기본 기능이 완성되었다! 다음 편에서는 표준어와 충청도 방언을 모두 지원하도록 언어를 확장하는 과정을 소개한다. '새김'은 어떻게 여러 방언을 지원할 수 있었을까?

 

---

 

전체 코드

https://github.com/Jihyun3478/saegim-lang

GitHub - Jihyun3478/saegim-lang: 한글 프로그래밍 언어 '새김' & 충청도 방언 버전 '해볼겨'를 제작했습니