이전 글에서 소스 코드source code를 토큰token으로 만들었습니다. 이 토큰으로 소스 코드를 정해진 문법에 따라 해석할 수 있는데, 그런 일을 하는 것을 파서parser라고 부릅니다.

파서는 소스 코드가 문법을 잘 지켰는지 확인합니다. 보통 프로그래밍에서 문법 오류로 실행이 안 된다면, 파서가 그런 사실을 파악했기 때문입니다. 만약 문법을 잘 지켰다면, 파서는 소스 코드를 해석한 결과로서 그 문법 구조를 나타내는 추상 문법 트리abstract syntax tree를 만듭니다.

파서는 여기까지의 역할만 맡습니다. 즉 변수 대입이나, 98/10의 값을 평가하는 동작은 하지 않습니다. 대신 문법 트리는 다음 단계를 위한 인터페이스가 됩니다. 이 트리를 어떤 값으로 바로 평가evaluate하면 인터프리터interpreter라고 부르고, 다른 언어로 코드 생성code generation을 하면 컴파일러compiler라고 부릅니다.

파싱 자체는 이론적으로 방대한 주제이고 다양한 방법이 있습니다. 여기서는 간단한 방법인 프랫 파서Pratt parser를 구현해보겠습니다. 앞으로 소개하는 내용을 통해, 인터프리터나 컴파일러가 어떻게 문법을 검사하는지 알게 될 것입니다.

바인딩 파워: 결합 방향 정하기

파서를 만들기 전에 구체적인 문법을 결정해야 합니다.

우리는 $1+2 \times 3$ 같은 식을 보면, 보통 곱셈부터 먼저 해야한다고 생각합니다. 우리의 프로그래밍 언어에서도 그렇게 만들 것인데, 이것을 두고 곱셈의 우선 순위priority가 더 높다고 할 것입니다. 이런 식으로 다른 연산자operator 또한 정할 것입니다.

여기에 연산자의 결합성associativity도 정해야 합니다. 예를 들어, $1-2-3$ 같은 식이 있을 때 보통 왼쪽 뺄셈부터 먼저 하는데, 암묵적으로 $(1-2)-3$으로 해석하는 것입니다. 이런 연산자를 왼쪽 결합left-associative 연산이라고 부르고, 반대의 경우 오른쪽 결합right-associative 연산이라고 부를 것입니다.

왼쪽 결합 연산

예를 들어, 식 1+2+3이 (1+2)+3로 해석된다고 합시다. 그러면 가운데 숫자 2가 왼쪽 덧셈에 ‘붙는다’고 볼 수 있을 텐데요. 상상력을 발휘해서 덧셈 기호 +의 양쪽에 ‘붙는 힘’이 있다고 해봅시다. 여기서는 각각 30과 31으로 크기를 정해보겠습니다.

이 그림이 보여주듯이, 숫자 2는 ‘붙는 힘’이 높은 쪽에 붙으면 됩니다. 그 힘을 프랫 파서에서는 바인딩 파워binding power라고 부릅니다.

우선 순위

한편, 1+2*3 같은 식은 1+(2*3) 처럼 곱셈을 먼저 하게끔 만들어야 합니다. 그렇게 만들려면 바인딩 파워를 어떻게 조절해야 할까요?

답은 곱셈 기호 *의 바인딩 파워를 더 높게 만드는 것입니다. 여기선 왼쪽과 오른쪽에 각각 40과 41 정도면 될 것입니다. 바인딩 파워는 값 자체보다 상대적인 차이에 의미가 있다는 점을 참고하세요.

이 그림대로라면, 숫자 2는 여전히 더 높은 바인딩 파워에 붙었을 뿐입니다. 이런 식으로 바인딩 파워만 잘 정하면 프랫 파서의 문법을 결정할 수 있습니다. 숫자를 바인딩 파워가 더 높은 쪽에 붙인다는 규칙만 남기 때문에 간단합니다.

오른쪽 결합 연산

앞서 덧셈 기호 +의 경우처럼, 연산자 오른쪽의 바인딩 파워가 더 높으면 왼쪽 결합 연산이 됩니다. 반대로 왼쪽이 더 높으면 오른쪽 결합 연산이 되는데요. 그런데 오른쪽 결합이 필요한 연산은 무엇이 있을까요?

대표적으로 대입 연산자 =을 그렇게 만들어야 합니다. 왜냐면 a = b = 1 같은 코드를 a = (b = 1) 처럼 만들고 싶기 때문입니다. (아니라면 어떨지 상상해보세요.)

바인딩 파워를 결정하기 위해 다른 연산과의 관계를 생각해봐야 합니다. 예를 들어, a = 1 + 2 같은 코드에서는 덧셈한 결과를 대입하고 싶을 것입니다. 즉 대입 연산은 사칙 연산보다 바인딩 파워가 낮아야 합니다. 따라서 여기서는 왼쪽과 오른쪽에 각각 11과 10을 주겠습니다.

함수를 정의하는 화살표 연산 -> 또한 오른쪽 결합 연산이어야 합니다. a -> b -> a+b와 같은 코드는 a -> (b -> a+b) 처럼 해석해야 하니까요. 이 경우에도 왼쪽 바인딩 파워를 더 높게 주면 됩니다.

구현하기

바인딩 파워는 단순히 왼쪽과 오른쪽 값을 가집니다. 파이썬으로 다음과 같이 만들어보겠습니다.

class BindingPower:
    def __init__(self, left, right):
        self.left = left
        self.right = right

    def __repr__(self):
        return f"[BindingPower: {self.left}, {self.right}]"

여기서 스트링 표현 함수 __repr__()는 단순히 print() 함수에 쓸 용도로 만든 것입니다. 앞으로도 마찬가지니 이후 설명은 생략하겠습니다.

이번엔 연산자마다 바인딩 파워를 매길 차례인데요. 아래처럼 새로운 클래스의 get() 메소드에 그 역할을 맡깁니다.

class BindingPowers:
    def __init__(self):
        self.lowest = BindingPower(0, 1)
        self.assignment = BindingPower(11, 10)
        self.arrow = BindingPower(21, 20)
        self.summative = BindingPower(30, 31)
        self.productive = BindingPower(40, 41)

    def get(self, operator: str) -> BindingPower:
        if operator == "=":
            return self.assignment
        if operator == "->":
            return self.arrow
        if operator in "+-":
            return self.summative
        if operator in "*/":
            return self.productive

        return self.lowest

연산자를 찾을 수 없으면 가장 낮은 바인딩 파워를 리턴하게 만들었습니다. 그 이유는 나중에 파서를 완성할 때쯤 만날 것입니다.

덧셈 연산의 바인딩 파워를 알고 싶다면 다음과 같이 사용합니다.

bindingPowers = BindingPowers()
plus = bindingPowers.get("+")
print(plus)
# result: [BindingPower: 30, 31]

덧셈 표현식 파서 만들기

본격적으로 1+2+3 와 같은 식을 파싱할 차례입니다. 앞으로 파싱할 단위를 표현식expression이라고 부르겠습니다. 일단 하나의 표현식을 파싱해봅시다. 그러면 여러 개의 표현식으로 파싱 능력을 손쉽게 확장할 수 있습니다.

파싱은 첫 토큰과 나머지 토큰을 처리하는 부분으로 나눌 것입니다. 첫 토큰에서는 숫자 토큰 1 같은 것이 오기를 기대할 수 있지만, 이후는 덧셈 토큰 + 같이 다른 종류를 기대하기 때문입니다.

숫자 토큰을 만난 다음 +와 같은 연산자 토큰을 만나면, 표현식에 파싱할 부분이 남았다는 뜻입니다. 파서는 여태까지 파싱한 결과인 문법 트리의 루트 노드를 top 노드로 유지할 것입니다. + 같은 연산자 토큰을 만날 때마다 새로운 top 노드로 파싱하고, 이전 결과를 왼쪽 자식 노드로 갖다 붙입니다.

준비하기

파싱 결과를 표현할 트리 타입을 다음과 같이 준비합시다.

class Node:
    def __init__(self, kind: str, children: list[Any]):
        self.kind = kind
        self.children = children

    def __repr__(self) -> str:
        return f"[Node: {self.kind}, {self.children}]"

한편, 파서는 토큰을 하나씩 읽다가 다음 토큰을 미리 봐야할 필요도 있습니다. 반복적으로 나타나는 현상이므로 토큰 리더 클래스를 따로 만들어봅시다.

이전 글에서 토크나이저가 문자를 읽었을 때처럼 비슷하게 만들 것입니다. 즉 read() 메소드로 토큰을 읽고, advance() 메소드로 다음 토큰으로 이동합니다.

from tokenizer import Token

class TokenReader:
    def __init__(self, tokens: list[Token]):
        self.tokens = tokens
        self.pos = 0 # index to read next

    def read(self) -> Token:
        if self.pos == len(self.tokens):
            return self.tokens[-1]

        return self.tokens[self.pos]

    def advance(self) -> None:
        if self.pos == len(self.tokens):
            return

        self.pos += 1

표현식 첫 부분 파싱

토큰 리더와 바인딩 파워로 파서를 만들어 봅시다.

class Parser:
    def __init__(self, tokens: list[Token]):
        self.reader = TokenReader(tokens)
        self.bindingPowers = BindingPowers()

이 클래스에 표현식 파싱을 맡을 메소드입니다.

    def parseExpression(self, leftBindingPower: BindingPower) -> Node:
        top = self.parseExpressionFirst()

        return top

이 메소드는 앞으로 재귀적으로 쓸 것입니다. 매개변수로 받는 leftBindingPower는 이전에 파싱했던 부분에서 오는데, 이렇게 만드는 이유는 곧 만날 것입니다.

표현식의 첫 토큰을 파싱하는 메소드를 만듭시다. 일단 숫자 토큰만 처리합니다.

    def parseExpressionFirst(self) -> Node:
        token = self.reader.read()
        self.reader.advance()

        if token.kind == "number":
            return Node("number", [int(token.value)])

        raise Exception(f"bad token '{token.kind}' for the first part of expression")

앞으로 사용할 파서의 인터페이스로 parse() 메소드를 쓸 것입니다. 지금은 하나의 표현식만 맡도록 둡니다.

    def parse(self) -> Node:
        return self.parseExpression(self.bindingPowers.lowest)

parseExpression() 메소드는 이전에 파싱한 토큰의 바인딩 파워를 받습니다. 그런데 이전에 처리한 부분이 없기 때문에, 가장 낮은 바인딩 파워를 넘깁니다. 즉 이쪽에 토큰이 붙지 말라는 뜻입니다.

이렇게 만든 파서는 숫자 하나를 파싱할 수 있을 정도가 되었습니다.

input = "1"
tokens = Tokenizer(input).getTokens()
node = Parser(tokens).parse()
print(node)
# result: [Node: number, [1]]

표현식 나머지 부분 파싱

parseExpression() 메소드를 어떻게 확장시킬 수 있는지 소개하겠습니다.

표현식에 파싱할 부분이 남았다면 파싱해서 top 노드로 하고, 이전 노드를 그 자식으로 만듭니다. 하지만 다음 토큰이 이전 토큰보다 바인딩 파워가 더 낮다면 이 반복을 멈춤니다. 현재 토큰이 다음 토큰에 붙으면 안되기 때문입니다.

    def parseExpression(self, leftBindingPower: BindingPower) -> Node:
        top = self.parseExpressionFirst()

        while True:
            token = self.reader.read()
            
            rightBindingPower = self.bindingPowers.get(token.kind)
            if leftBindingPower.right >= rightBindingPower.left:
                break
            
            parsedRest = self.parseExpressionRest(top)
            top = parsedRest

        return top

이제 표현식 나머지 부분을 파싱할 차례입니다. 매개변수 left에 왼쪽 자식으로 할 노드를 받고, 현재 토큰을 읽은 다음, 오른쪽 자식 right에 재귀적으로 파싱한 결과를 가져옵니다.

    def parseExpressionRest(self, left: Node) -> Node:
        token = self.reader.read()
        self.reader.advance()

        if token.kind == "+":
            infix = token.kind
            right = self.parseExpression(self.bindingPowers.get(infix))

            return Node("infix", [infix, left, right])

        raise Exception(f"bad token '{token.kind}' for the rest part of expression")

오른쪽 자식 right를 파싱할 때, 현재 토큰의 바인딩 파워를 알려줍니다. 이는 다음 표현식을 파싱하는 parseExpression() 메소드에서 왼쪽 바인딩 파워로 쓰이게 됩니다.

이렇게 만든 파서는 드디어 1+2+3을 파싱할 수 있게 됐습니다.

input = "1+2+3"
tokens = Tokenizer(input).getTokens()
node = Parser(tokens).parse()
print(node)

결과를 보기 좋게 정리하면 이런 식입니다.

[Node: infix, [
  '+',
  [Node: infix, [
    +',
    [Node: number, [1]],
    [Node: number, [2]]
  ]],
  [Node: number, [3]]
]]

이 결과는 앞서 ‘그림 5’에서 봤던 트리와 일치합니다.

파서 완성하기

현재 파서는 덧셈을 파싱할 수 있지만, 다른 연산자로도 확장할 수 있습니다. 큰 틀은 완성해두었기 때문에, 나머지 과정은 비교적 간단합니다.

사칙 연산과 대입 연산 파싱

몇 줄 되지 않는 코드로 사칙연산과 대입 연산의 파싱을 추가할 수 있습니다.

    def parseExpressionRest(self, left: Node) -> Node:
        # ...

        if token.kind == "+": 
        if token.kind in "+-*/=": 
            # ...

여기에 a = 1과 같이 대입 연산을 쓸 수 있도록 식별자 토큰을 파싱합시다. 식별자 토큰은 표현식 첫 부분에 오기 때문에 다음과 같이 추가합니다.

    def parseExpressionFirst(self) -> Node:
        # ...

        if token.kind == "number":
            return Node("number", [int(token.value)])
        if token.kind == "identifier": 
            return Node("identifier", [token.value]) 

        # ...

벌써 끝났습니다. 이제 a = b = 1+2*3 같은 표현식을 파싱할 수 있게 됩니다.

input = "a = b = 1+2*3"
tokens = Tokenizer(input).getTokens()
node = Parser(tokens).parse()
print(node)

결과를 보기 좋게 정리하면 이렇게 됩니다.

[Node: infix, [
  '=',
  [Node: identifier, ['a']],
  [Node: infix, [
    '=',
    [Node: identifier, ['b']],
    [Node: infix, [
      '+',
      [Node: number, [1]],
      [Node: infix, [
        '*',
        [Node: number, [2]],
        [Node: number, [3]]
      ]]
    ]]
  ]]
]]

먼저 계산할 부분이 자식 노드에 위치한다는 점을 참고하세요. 즉 곱셈, 덧셈, 대입 순으로 처리 순서가 나타납니다. 대입 또한 b 식별자에 먼저 이루어집니다. 전부 우리가 원했던 바입니다.

함수 정의 파싱

함수 정의는 a -> b 처럼 화살표 토큰 ->으로 할 것입니다. 지금까지 했던대로 파서를 확장하면 됩니다. 사칙 연산 토큰을 처리하는 부분에 화살표 토큰도 더합니다.

    def parseExpressionRest(self, left: Node) -> Node:
        # ...

        if token.kind in "+-*/=": 
        if token.kind == "->" or token.kind in "+-*/=": 
          # ...

이게 전부입니다. 이제 함수 정의를 파싱할 수 있게 됩니다.

input = "a -> b -> c"
tokens = Tokenizer(input).getTokens()
node = Parser(tokens).parse()
print(node)

출력 결과를 정리하면 이렇습니다.

[Node: infix, [
  '->',
  [Node: identifier, ['a']],
  [Node: infix, [
    '->',
    [Node: identifier, ['b']],
    [Node: identifier, ['c']]
  ]]
]]

함수 호출 파싱

마지막으로 f(1)과 같은 함수 호출만 남았습니다.

여기서 ( 토큰을 일종의 호출 연산자라고 생각해봅시다. 그러면 이것은 다른 것들보다 우선 순위가 높아야 합니다. 이에 따라 바인딩 파워를 새로 추가합시다.

class BindingPowers:
    def __init__(self):
        # ...
        self.productive = BindingPower(40, 41)
        self.call = BindingPower(50, 51) 

    def get(self, operator: str) -> BindingPower:
        # ...
        if operator in "*/":
            return self.productive
        if operator == "(": 
            return self.call 

        # ...

앞서 언급한 대로, 여는 괄호를 하나의 연산자로 처리합시다. 뒤에 오는 호출 인자argument는, f(1+2)에서 나타나는 덧셈처럼 어떤 표현식이든 될 수 있습니다. 그리고 닫는 괄호가 오기를 기대한 뒤, 함수 호출 노드를 만들어서 리턴합니다.

    def parseExpressionRest(self, left: Node) -> Node:
        # ...

        if token.kind == "->" or token.kind in "+-*/=":
            # ...

        if token.kind == "(":
            arg = self.parseExpression(self.bindingPowers.lowest)
            
            token = self.reader.read()
            if token.kind != ")":
                raise Exception(f"expected ')' but received '{token.kind}'")
            self.reader.advance()
            
            return Node("call", [left, arg])

        # ...

이제 다음과 같이 함수 호출을 파싱할 수 있습니다.

input = "a(1)"
tokens = Tokenizer(input).getTokens()
node = Parser(tokens).parse()
print(node)
# [Node: call, [[Node: identifier, ['f']], [Node: number, [1]]]]

소스 코드 파싱

표현식 파싱은 끝났습니다. 그런데 실제 소스 코드는 보통 표현식이 많이 있기 때문에, 그 수준까지 확장하는 것으로 파서 구현을 마치겠습니다.

    def parse(self) -> Node:
        return self.parseExpression(self.bindingPowers.lowest) 
        nodes: list[Node] = []
        while self.reader.read().kind != "END":
            nodes.append(self.parseExpression(self.bindingPowers.lowest))
        return nodes

이제 다음과 같은 소스 코드를 파싱할 수 있습니다.

input = "a+b c*d"
tokens = Tokenizer(input).getTokens()
node = Parser(tokens).parse()
print(node)

결과는 정리하면 다음과 같습니다.

[
  [Node: infix, [
    '+',
    [Node: identifier, ['a']],
    [Node: identifier, ['b']]
  ]],
  [Node: infix, [
    '*',
    [Node: identifier, ['c']],
    [Node: identifier, ['d']]
  ]]
]

왜 갑자기 여러 표현식을 파싱할 수 있게 됐을까요? 하나의 표현식을 파싱하고나면, 그 다음 표현식의 시작은 가장 낮은 바인딩 파워를 가진다고 가정했기 때문입니다.

    def parseExpression(self, leftBindingPower: BindingPower) -> Node:
        # ...

        while True:
            token = self.reader.read()

            rightBindingPower = self.bindingPowers.get(token.kind)
            if leftBindingPower.right >= rightBindingPower.left:
                break

            # ...

이전 표현식이 끝나고 다음 표현식이 시작되면, 다음 토큰은 연산자가 아닐 것입니다. 따라서 바인딩 파워 클래스의 get() 메소드는 가장 낮은 바인딩 파워인 lowest를 주게 되고, while 문은 중단되어 표현식 파싱이 끝나게 됩니다. 이것이 처음에 바인딩 파워 클래스 BindingPowers를 구현할 때, 연산자가 아니면 lowest를 리턴했던 이유입니다.

마치며

토큰을 통해 파싱하는 부분을 구현해보았습니다. 파싱 결과인 트리는 앞으로 만들 값 평가에 사용됩니다. 이를 통해 1+2 같은 코드는 3으로 평가되어 간단한 인터프리터를 완성하게 됩니다.

이 글에서 ‘표현식 첫 부분’과 ‘표현식 나머지’라는 표현을 썼는데요. 사실 프랫 파서는 각각을 nudnull denotation와 ledleft denotation라는 이름으로 부릅니다. 본문에서는 쉬운 이해를 위해 다른 이름으로 바꿨습니다.

앞에서 언급했던 것처럼, 파싱은 다양한 방법이 있습니다. 대표적으로는 LL(k) 문법이라고 부르는 문맥 자유 문법context-free grammar을 만드는 것입니다. 그런 문법을 파싱하는 것을 LL 파서라고 부릅니다. 이 문법은 BNFBackus–Naur form라는 형식으로 기술할 수 있고, 이를 바탕으로 최대 k번의 토큰 미리보기를 통해 백트래킹 없이 재귀적으로 동작하는 파서를 구현할 수 있습니다.

여기까지 생략된 부분을 포함한 코드는 지스트Gist에서 볼 수 있습니다.

레퍼런스

• Writing An Interpreter In Go (Thorsten Ball, 2020), 또는 밑바닥부터 만드는 인터프리터 in Go (2021)

• Beautiful Code (Andy Oram, Greg Wilson, 2007): 자바스크립트JavaScript로 구현한 프랫 파서가 아홉번째 챕터에 소개되어 있습니다.

• Top Down Operator Precedence (Vaughan R. Pratt, 1973)

• crockford.com: 위 Beautiful Code 책의 내용과 같습니다.

• matklad.github.io: 러스트Rust로 구현한 프랫 파서가 소개되어 있습니다.