Go 언어로 간단한 수식 평가기 만들어보기

 

안녕하세요!

 

오늘은 Go 언어의 go 패키지를 활용해 간단한 수식 평가기를 만들어보려고 합니다.

 

평소에 go 패키지를 제대로 써본 적이 없었는데, 요즘 회사 일을 하면서 추상 구문 트리(AST)를 자주 다뤄야 해서 기회가 생겼네요.

 

수식 평가기는 들리기에는 좀 어려울 수 있지만, 대부분 go 패키지의 기능을 활용하면 상당히 간단하답니다.

 

그럼 어떻게 만드는지 하나씩 살펴볼까요?

---

AST(Abstract Syntax Tree)란?

AST란 프로그래밍 언어의 소스 코드를 추상적인 구문 트리로 나타낸 것을 말합니다.

 

코드를 파싱하면 이렇게 트리 형태로 만들어지는데, 각 노드는 코드의 구문 구조(문법적 의미)를 나타냅니다.

 

예를 들어 "x = 1 + 2" 라는 간단한 코드라면, AST는 대략 이런 식으로 구성될 것입니다:

         =
        / \
       x   +
          / \
         1   2

 

루트 노드는 대입 연산을 나타내고, 그 왼쪽 자식은 대입 대상인 x, 오른쪽 자식은 1 + 2 식을 트리로 표현한 것입니다.

 

이렇게 AST를 사용하면 코드의 구문 구조를 쉽게 이해하고 다룰 수 있습니다.

 

컴파일러나 인터프리터, 코드 최적화기, 린터, 코드 생성기 등 다양한 프로그램에서 AST를 활용하고 있죠.

 

이 글에서는 Go 언어의 go/parser 패키지를 이용해 소스 코드 문자열을 AST로 파싱하고 있습니다.

 

생성된 AST를 순회하며 각 노드에 대한 처리를 할 수 있습니다.

---

AST로 파싱하기

먼저 입력된 문자열을 파싱해서 AST를 생성해야 합니다.

 

이번에는 수식을 평가할 것이므로 수식 단위로 파싱하면 되겠죠.

 

파싱에는 parser.ParseExpr 함수를 사용합니다.

 

다음과 같이 사용할 수 있습니다.

expr, err := parser.ParseExpr("1+1") 
if err != nil {
    panic(err)
}

ast.Inspect(expr, func(n ast.Node) bool {
    if n != nil {
        fmt.Printf("%[1]v(%[1]T)\n", n)
    }
    return true
})

 

ast.Inspect 함수는 AST의 노드를 순회하는 함수입니다.

 

이 경우 "1+1"을 파싱하면 다음과 같은 AST를 얻을 수 있습니다.

*ast.BinaryExpr (+)  
├── *ast.BasicLit (1)
└── *ast.BasicLit (1)

 

이렇게 얻은 AST를 평가하면 수식을 계산할 수 있습니다.

 

그렇다면 구체적으로 어떻게 평가할까요?

"1+1" 평가하기

위 예제에서 봤듯이 이항 연산을 수행하는 수식은 ast.BinaryExpr로 표현됩니다.

 

먼저 이항 연산식 "1+1"을 평가해볼까요?

func eval1pls1(expr *ast.BinaryExpr) (int64, error) {
    xLit, ok := expr.X.(*ast.BasicLit)
    if !ok {
        return 0, errors.New("왼쪽 오퍼랜드가 BasicLit가 아님")
    }

    yLit, ok := expr.Y.(*ast.BasicLit) 
    if !ok {
        return 0, errors.New("오른쪽 오퍼랜드가 BasicLit가 아님")
    }

    if expr.Op != token.ADD {
        return 0, errors.New("연산자가 +가 아님")
    }

    x, err := strconv.ParseInt(xLit.Value, 10, 64)
    if err != nil {
        return 0, err
    }

    y, err := strconv.ParseInt(yLit.Value, 10, 64)
    if err != nil {
        return 0, err
    }

    return x + y, nil
}

func main() {
    expr, err := parser.ParseExpr("1+1")
    if err != nil {
        panic(err)
    }

    if be, ok := expr.(*ast.BinaryExpr); ok {
        if v, err := eval1pls1(be); err == nil {
            fmt.Println(v)
        } else {
            fmt.Println("Error:", err)
        }
    }
}

 

parser.Parse가 반환하는 ast.Expr은 인터페이스이므로, 구체적으로 어떤 식인지는 타입 단언(또는 타입 스위치)을 통해 알아내야 합니다.

 

그래서 필요한 ast.BinaryExpr와 좌우 오퍼랜드인 ast.BasicLit를 타입 단언으로 가져오고 있습니다.

 

ast.BasicLit는 기본 리터럴 타입을 나타내는데, 1이나 "kim" 등이 여기에 해당합니다.

 

true와 false는 식별자이기 때문에 ast.BasicLit가 아닌 ast.Ident로 표현된다는 점을 기억하세요.

 

true와 false도 식별자로 사용할 수 있습니다.

 

ast.BasicLit의 Value 필드는 그 리터럴 값을 문자열로 나타낸 것입니다.

 

42, 0x7f, 3.14, 1e-9, 2.4i, 'a', "foo" 등이 있겠네요.

 

문자열의 경우 따옴표로 둘러싸여 있다는 점에 주의하세요.

 

따옴표를 제거하고 싶다면 strconv.Unquote를 사용하면 됩니다.

---

이항 연산식과 리터럴 평가하기

이제 "1+1"은 평가할 수 있게 되었지만, 우리가 만들고자 하는 것은 일반적인 이항 연산식 평가기입니다.

 

따라서 좀 더 일반화할 필요가 있습니다.

 

오퍼랜드가 숫자라는 점과 연산자가 +라는 점을 일반화해야 합니다.

 

그래서 go/constant 패키지에 있는 BinaryOp 함수를 사용하면 이항 연산자를 간단히 평가할 수 있습니다.

 

BinaryOp 함수의 시그니처는 다음과 같습니다.

func BinaryOp(x Value, op token.Token, y Value) Value

 

op는 token.ADD 같은 연산자 토큰을 나타내는데, 이는 ast.BinaryExpr의 Op 필드에서 가져올 수 있습니다.

 

x와 y는 constant.MakeFromLiteral을 사용해서 얻을 수 있겠죠.

 

constant.MakeFromLiteral의 정의는 다음과 같습니다.

func MakeFromLiteral(lit string, tok token.Token, zero uint) Value

 

첫 번째 인자로 ast.BasicLit의 Value 필드를, 두 번째 인자로 ast.BasicLit의 Kind 필드를 넘기면 되겠네요.

 

세 번째 인자는 항상 0을 넘기면 됩니다.

 

위 코드를 다음과 같이 변경할 수 있습니다.

func evalBinaryExpr(expr *ast.BinaryExpr) (constant.Value, error) {
    xLit, ok := expr.X.(*ast.BasicLit)
    if !ok {
        return constant.MakeUnknown(), errors.New("왼쪽 오퍼랜드가 BasicLit가 아님")
    }

    yLit, ok := expr.Y.(*ast.BasicLit)
    if !ok {
        return constant.MakeUnknown(), errors.New("오른쪽 오퍼랜드가 BasicLit가 아님") 
    }

    x := evalBasicLit(xLit)
    y := evalBasicLit(yLit)
    return constant.BinaryOp(x, expr.Op, y), nil
}

func evalBasicLit(expr *ast.BasicLit) constant.Value {
    return constant.MakeFromLiteral(expr.Value, expr.Kind, 0)
}

func main() {
    expr, err := parser.ParseExpr("1+1")
    if err != nil {
        panic(err)
    }

    if be, ok := expr.(*ast.BinaryExpr); ok {
        if v, err := evalBinaryExpr(be); err == nil {
            fmt.Println(v)
        } else {
            fmt.Println("Error:", err)
        }
    }
}

 

이항 연산식 평가 함수를 evalBinaryExpr로, 리터럴 평가 함수를 evalBasicLit로 분리했습니다.

 

"1-1"도 실행할 수 있는지 확인해보세요.

 

"kim"+"kim" 같은 문자열 연산도 잘 동작할 것입니다.

 

constant.MakeUnknown 함수는 에러 발생시 반환할 값을 만듭니다.

 

연산이 실패하면 이 값을 반환하게 되는데, 뒤에서 소개할 eval 함수에 유용하게 쓰입니다.

---

수식 평가하기

이제 이항 연산식을 평가할 수 있게 되었습니다.

 

하지만 진짜 만들고 싶은 건 일반적인 수식 평가기입니다.

 

수식에는 -1 같은 단항 연산식, 1 같은 리터럴, (1+1)*2 같은 괄호 수식도 있습니다.

 

Go 문법에는 함수 호출도 있지만, 지금은 사칙연산만 할 수 있어도 충분할 것 같네요.

 

어떤 종류의 수식인지는 ast.Expr을 구체적 타입으로 바꿔서 알 수 있고, 그 종류에 따라 처리를 분기하면 되겠습니다.

 

위에서 만든 이항 연산식 평가기를 조금만 일반화해볼까요?

 

먼저 수식(ast.Expr)을 평가하는 함수를 만들어봅시다.

func evalExpr(expr ast.Expr) (v constant.Value, rerr error) {
    defer func() {
        if r := recover(); r != nil {
            v, rerr = constant.MakeUnknown(), fmt.Errorf("%v", r)
        }
    }()

    switch e := expr.(type) {
    case *ast.BinaryExpr:
        return evalBinaryExpr(e)  
    case *ast.BasicLit:
        return constant.MakeFromLiteral(e.Value, e.Kind, 0), nil
    }

    return constant.MakeUnknown(), errors.New("알 수 없는 노드")
}

 

evalExpr 함수는 ast.Expr을 받아서 타입에 따라 처리를 분기합니다.

 

여기서는 이항 연산식과 리터럴만 처리할 수 있도록 했습니다.

 

defer에서 recover하는 이유는 constant 패키지의 BinaryOp 등이 타입이 맞지 않으면 에러를 반환하지 않고 패닉을 일으키기 때문입니다.

 

이제 evalBinaryExpr 함수에서 호출하던 evalBasicLit도 evalExpr에 맡기도록 하죠.

func evalBinaryExpr(expr *ast.BinaryExpr) (constant.Value, error) {
    x, err := evalExpr(expr.X)
    if err != nil {
        return constant.MakeUnknown(), err
    }

    y, err := evalExpr(expr.Y)
    if err != nil {
        return constant.MakeUnknown(), err
    }

    return constant.BinaryOp(x, expr.Op, y), nil
}

 

이제 evalExpr에 처리 가능한 타입을 계속 추가하면 됩니다.

 

필요해 보이는 것들을 추가하면 evalExpr는 다음과 같이 됩니다.

func evalExpr(expr ast.Expr) (v constant.Value, rerr error) {
    defer func() {
        if r := recover(); r != nil {
            v, rerr = constant.MakeUnknown(), fmt.Errorf("%v", r)
        }
    }()

    switch e := expr.(type) {
    case *ast.ParenExpr:
        return evalExpr(e.X)
    case *ast.BinaryExpr:
        return evalBinaryExpr(e)
    case *ast.UnaryExpr:
        return evalUnaryExpr(e)
    case *ast.BasicLit:
        return constant.MakeFromLiteral(e.Value, e.Kind, 0), nil
    case *ast.Ident:
        return evalIdent(e)
    }

    return constant.MakeUnknown(), errors.New("알 수 없는 노드")
}

 

ast.ParenExpr은 괄호로 둘러싸인 수식으로, 그냥 안의 수식(ParenExpr.X)을 평가하면 됩니다.

 

ast.UnaryExpr은 단항 연산자 수식을 표현하는 타입으로, ast.BinaryExpr처럼 evalUnaryExpr 함수를 만들어 처리합니다.

func evalUnaryExpr(expr *ast.UnaryExpr) (constant.Value, error) {
    x, err := evalExpr(expr.X)
    if err != nil {
        return constant.MakeUnknown(), err
    }

    return constant.UnaryOp(expr.Op, x, 0), nil
}

 

사칙연산과는 관련 없지만, true와 false도 처리할 수 있게 해볼까요?

 

true나 false가 오면 ast.Ident로 처리해야 하므로 evalIdent 함수를 만듭시다.

func evalIdent(expr *ast.Ident) (constant.Value, error) {
    switch {
    case expr.Name == "true":
        return constant.MakeBool(true), nil
    case expr.Name == "false":
        return constant.MakeBool(false), nil
    }

    return constant.MakeUnknown(), errors.New("알수 없는 식별자")
}

 

true와 false는 이름이 "true"와 "false"인 식별자로 인식되므로, 위와 같이 처리하면 됩니다.

 

이제 대부분 완성된 것 같지만, true와 false를 처리할 수 있게 되면서 문제가 하나 생겼네요.

 

constant.BinaryOp에서는 &&나 >= 같은 관계 연산자를 다룰 수 없습니다.

 

대신 constant.Compare를 사용해야 합니다.

 

그래서 evalBinaryExpr 함수를 다음과 같이 수정해야 합니다.

func evalBinaryExpr(expr *ast.BinaryExpr) (constant.Value, error) {
    x, err := evalExpr(expr.X)
    if err != nil {
        return constant.MakeUnknown(), err
    }

    y, err := evalExpr(expr.Y)
    if err != nil {
        return constant.MakeUnknown(), err
    }

    switch expr.Op {
    case token.EQL, token.NEQ, token.LSS, token.LEQ, token.GTR, token.GEQ:
        return constant.MakeBool(constant.Compare(x, expr.Op, y)), nil
    }

    return constant.BinaryOp(x, expr.Op, y), nil
}

 

이제 수식을 평가하는 evalExpr 함수가 완성되었습니다.

 

마지막으로 이것을 래핑하는 eval 함수를 만들어 사용하기 편하게 해볼까요?

func eval(e string) (string, error) {
    expr, err := parser.ParseExpr(e)
    if err != nil {
        return "", err
    }

    v, err := evalExpr(expr)
    if err != nil {
        return "", err
    }

    return v.String(), nil
}

---

REPL 만들기

이제 수식 평가 함수가 있으니, REPL을 만들어볼까요?

 

여기서 만들 REPL은 수식을 입력받고, 입력되면 그 수식을 평가해서 결과를 보여주는 식이 될 것입니다.

 

표준 입력(os.Stdin)에서 bufio.Scanner를 사용해 한 줄씩 읽는 코드를 작성해봅시다.

 

"bye"를 입력하면 REPL을 종료할 수 있게 할 거예요.

func repl(r io.Reader) {
    s := bufio.NewScanner(r)
    for {
        fmt.Print(">")
        if !s.Scan() {
            break
        }

        l := s.Text()
        switch {
        case l == "bye":
            return
        default:
            r, err := eval(l)
            if err != nil {
                fmt.Println("Error:", err)
                continue
            }
            fmt.Println(r)
        }
    }

    if err := s.Err(); err != nil {
        fmt.Println("Error:", err)
    }
}

 

잘 만들어졌나요? 지금까지 작성한 전체 코드를 한번 보시죠.

package main

import (
    "bufio"
    "errors"
    "fmt"
    "go/ast"
    "go/constant"
    "go/parser"
    "go/token"
    "io"
    "os"
)

func eval(e string) (string, error) {
    expr, err := parser.ParseExpr(e)
    if err != nil {
        return "", err
    }

    v, err := evalExpr(expr)
    if err != nil {
        return "", err
    }

    return v.String(), nil
}

func evalExpr(expr ast.Expr) (v constant.Value, rerr error) {
    defer func() {
        if r := recover(); r != nil {
            v, rerr = constant.MakeUnknown(), fmt.Errorf("%v", r)
        }
    }()

    switch e := expr.(type) {
    case *ast.ParenExpr:
        return evalExpr(e.X)
    case *ast.BinaryExpr:
        return evalBinaryExpr(e)
    case *ast.UnaryExpr:
        return evalUnaryExpr(e)
    case *ast.BasicLit:
        return constant.MakeFromLiteral(e.Value, e.Kind, 0), nil
    case *ast.Ident:
        return evalIdent(e)
    }

    return constant.MakeUnknown(), errors.New("알 수 없는 노드")
}

func evalBinaryExpr(expr *ast.BinaryExpr) (constant.Value, error) {
    x, err := evalExpr(expr.X)
    if err != nil {
        return constant.MakeUnknown(), err
    }

    y, err := evalExpr(expr.Y)
    if err != nil {
        return constant.MakeUnknown(), err
    }

    switch expr.Op {
    case token.EQL, token.NEQ, token.LSS, token.LEQ, token.GTR, token.GEQ:
        return constant.MakeBool(constant.Compare(x, expr.Op, y)), nil
    }

    return constant.BinaryOp(x, expr.Op, y), nil
}

func evalUnaryExpr(expr *ast.UnaryExpr) (constant.Value, error) {
    x, err := evalExpr(expr.X)
    if err != nil {
        return constant.MakeUnknown(), err
    }

    return constant.UnaryOp(expr.Op, x, 0), nil
}

func evalIdent(expr *ast.Ident) (constant.Value, error) {
    switch {
    case expr.Name == "true":
        return constant.MakeBool(true), nil
    case expr.Name == "false":
        return constant.MakeBool(false), nil
    }

    return constant.MakeUnknown(), errors.New("알 수 없는 식별자")
}

func repl(r io.Reader) {
    s := bufio.NewScanner(r)
    for {
        fmt.Print(">")
        if !s.Scan() {
            break
        }

        l := s.Text()
        switch {
        case l == "bye":
            return
        default:
            r, err := eval(l)
            if err != nil {
                fmt.Println("Error:", err)
                continue
            }
            fmt.Println(r)
        }
    }

    if err := s.Err(); err != nil {
        fmt.Println("Error:", err)
    }
}

func main() {
    repl(os.Stdin)
}

---

마무리

120줄도 채 안 되는 코드로 꽤 성능 좋은 수식 평가 REPL을 만들었네요.

 

Go에서는 복소수도 사용할 수 있어서, 방금 만든 REPL에서도 복소수를 다룰 수 있답니다.

 

만약 evalExpr에 변수(ast.Ident)나 함수 호출(ast.CallExpr) 평가 처리를 추가한다면, 더 강력한 것을 만들 수 있겠죠.

 

정말 go 패키지를 사용하면 의외로 간단히 만들 수 있더라고요.

 

대단한 패키지네요.

 

그렇다고 해서 이걸 실제 업무에서 쓸 수 있을지는 의문이 들 수 있겠네요.

 

하지만 활용 방안을 잘 생각해보면 충분히 쓸 수 있을 거예요.

 

어떤 용도로 써먹을지 한번 고민해보시기 바랍니다.