Pratt Parsing 알고리즘

코드
우선순위 대신 결합력을 도입하자
시뮬레이션
관찰
결론
참고문헌

파싱 알고리즘은 크게 상향식(bottom-up)과 하향식(top-down)으로 나뉠 수 있다. 이 글에서는 하향식 파싱 알고리즘 중 가장 간단한 편에 속하는 Pratt Parsing을 소개한다. 간단하다고는 하지만, 필자의 경우에는 이해하는 데 꽤 많은 시간이 걸렸다. 인터넷으로 여러 글을 찾아보고, 손으로 끄적이면서 파싱 트리를 그려보고 코드를 머릿속으로 돌려보는 과정을 여러 번 거친 후에야 어느 정도 이해를 할 수 있었다.

이 글에서는 Alex Kladov의 글 Simple but Powerful Pratt Parsing을 읽고 내가 이해한 것을 기반으로 Pratt 파싱의 원리를 간략하게 정리해보겠다. 이왕이면 필자의 글을 읽기 전에 저 글을 먼저 읽고 오는 것을 추천한다. Pratt 파싱을 다룬 많은 글(survey post가 따로 있을 정도로 많다) 중에서는 굉장히 이해하기 쉽게 쓰인 편이라고 생각한다.

이 글은 Pratt 파싱의 이론적 원리를 엄밀하게 따지기보다, 직접 예시 표현식을 눈으로 따라가면서 파싱해보면서 알고리즘의 원리를 직관적으로 이해해보는 것을 목표로 한다.

코드

우선 코드부터 보자. 참고로 Simple but Powerful Pratt Parsing의 본문에 있는 코드이다.

fn expr(input: &str) -> S {
    let mut lexer = Lexer::new(input);
    expr_bp(&mut lexer, 0) 
}

fn expr_bp(lexer: &mut Lexer, min_bp: u8) -> S { 
    let mut lhs = match lexer.next() {
        Token::Atom(it) => S::Atom(it),
        t => panic!("bad token: {:?}", t),
    };
    loop {
        let op = match lexer.peek() {
            Token::Eof => break,
            Token::Op(op) => op,
            t => panic!("bad token: {:?}", t),
        };
        let (l_bp, r_bp) = infix_binding_power(op);
        if l_bp < min_bp { 
            break;
        }
        lexer.next(); 
        let rhs = expr_bp(lexer, r_bp);
        lhs = S::Cons(op, vec![lhs, rhs]); 
    }
    lhs
}

Rust라서 조금 생소할 수 있지만 크게 어렵지는 않은 코드이다. 특이한 점으로는 반복문과 재귀를 둘 다 사용한다. 여기서 Lexer는 토큰을 하나씩 제공해주는 역할을 하는 구조체로, .next()는 토큰을 하나 pop하는 역할을, .peek()는 다음 토큰을 (pop하지는 않고) 보여주는 역할을 하는 메서드이다.

토큰의 경우 다음과 같은 enum으로 정의되어 있다.

enum Token {
    Atom(char),  // 1, 2, 3, a, b 등
    Op(char),    // +, *, ^ 등
    Eof,         // End Of File
}

코드를 부분부분씩 뜯어보도록 하자.

우선순위 대신 결합력을 도입하자

Pratt Parsing의 중요한 아이디어는 연산자의 우선순위(precedence) 대신 결합력(binding power)이라는 개념을 사용한다는 것이다. 예를 들어서, 1 + 2 * 3이라는 식이 주어져 있을 때 1 + 2보다 2 * 3이 먼저 계산되는 것은 곱셈의 결합력이 덧셈보다 높기 때문이다.

이때 해당 연산이 오른쪽과 왼쪽 피연산자 중 무엇을 우선순위로 하는지에 따라서 왼쪽 결합력과 오른쪽 결합력을 다르게 두어야 한다. 예를 들어서 덧셈이나 곱셈의 경우 왼쪽부터 차례대로 계산하므로(1+2+3에서 1+2를 먼저 계산하고 3을 더한다) 연산자의 왼쪽 결합력이 더 낮은 것으로 정의되어야 한다. (피연산자가 왼쪽 연산자를 우선시하는 것이지, 연산자의 왼쪽 결합력이 더 높은 것이 아니다!)

식:   a   +    b    +    c
결합력:   1    2    1    2

이렇게 되어야 위의 식처럼 c를 왼쪽에서 끌어당기는 결합력이 오른쪽에서 끌어당기는 결합력보다 높아 (a+b)가 먼저 계산된 후 (a+b)+c가 계산된다.

반면, 거듭제곱(^)과 같은 연산의 경우에는 오른쪽부터 계산이 되어야 한다. ($2^{3^4}$은 $2^{81}$이지, $8^4$이 아니라는 사실을 생각하자) 이런 경우는 오른쪽 결합력이 더 높은 것으로 생각할 수 있다.

이 글에서는 사칙연산과 거듭제곱 연산만을 다룰 것이다. 이런 경우 연산자의 결합력을 구하는 함수는 다음과 같이 정의할 수 있을 것이다.

fn infix_binding_power(op: char){
    match op {
        '+' | '-' => (1, 2),
        '*' | '/' => (3, 4),
        '^' => (6, 5),
        t => panic!("Invalid operator {:?}", t)
    }
}

시뮬레이션

코드의 작동 원리가 한눈에 들어오지 않을 때는 pen-and-paper 디버깅이 도움이 될 때가 많다. 1 * 2 ^ 3 * 4 + 5라는 표현식을 예시로 하여 머릿속에서 실행해보자.

expr_bp(토큰 포인터: 1, min_bp:0)
시작하면서 피연산자(Token::Atom)와 연산자(Token::Op)를 하나 가져온다. minbp는 0이므로 당연히 lbp보다 낮다. 따라서 우선은 atom과 op을 각각 구문분석 트리의 왼쪽 자식(lhs)과 루트 노드로 삼는다.

   *
  / \
1   RHS1

RHS로는 뭐가 올지 알 수 없으므로 expr_bp(토큰 포인터: 2, min_bp: 4)를 재귀호출해 구하기로 한다. min_bp에 들어간 것은 *의 오른쪽 결합력이다.

expr_bp(토큰 포인터: 2, min_bp: 4)
atom과 operator를 하나씩 가져온다. 2와 ^인데, ^의 왼쪽 결합력은 6으로 min_bp=4보다 높다. 따라서 마찬가지로 2를 왼쪽 자식으로, ^을 부모로 삼아 계속 진행해간다.

RHS1:

  ^
 / \
2 RHS2

여기에서도 RHS에 무엇이 올지 모르니 이를 구하기 위해 expr_bp(토큰 포인터:3, min_bp: 5)를 실행한다.

expr_bp(토큰 포인터:3, min_bp: 5)
여기에서도 마찬가지로 진행한다면 RHS2는 다음과 같은 형태가 될 것이다.

RHS2(?):


  *
 / \
3 RHS3?

하지만 여기에서는 min_bp=6보다 다음 연산자(*)의 왼쪽 결합력 5가 더 낮다. 따라서 반복문이 break되고, lhs의 값인 현재 토큰 3이 반환된다. 이것이 RHS2의 값이다.

expr_bp(토큰 포인터: 2, min_bp: 4)
expr_bp(토큰 포인터:3, min_bp: 5)가 리턴을 해서 expr_bp(토큰 포인터: 2, min_bp: 4)로 돌아왔다. 이는 RHS2로 3을 받아서 다음과 같은 트리를 lhs로 갖게 되었다.

RHS1:

  ^
 / \
2   3

이제 loop의 다음 번 반복이 실행된다. 다음 연산자를 peek로 가져와보니 *이다. 이는 왼쪽 결합력이 3으로, min_bp=4보다 낮다. 따라서 또 break를 하고 lhs를 리턴한다.

expr_bp(토큰 포인터: 1, min_bp:0)
이제 맨 처음의 함수 호출로 돌아왔다. RHS1로 (^ 2 3)을 받아, lhs는

와 같은 상태이다. 이를 저장해둔 채로 다음 loop가 실행된다. 다음 연산자를 가져오면 (아까 peek를 했으니 소모되지 않은 상태이다) 로, 왼쪽 결합력이 3이니 min_bp=0보다 높다. 따라서 현재의 lhs 전체를 왼쪽 자식으로 하는 새로운 부모 노드로 를 만들자.

이제 RHS3를 구하기 위해 또 재귀함수를 호출한다.

expr_bp(토큰 포인터: 4, min_bp: 3)
다음 atom인 4를 가져오고, 연산자인 +를 peek해 읽어온다. 덧셈의 왼쪽 결합력은 1으로, min_bp=3보다 작다. 따라서 4가 그대로 return된다. 이것이 5.expr_bp(토큰 포인터: 1, min_bp:0)의 RHS3에 해당된다.
expr_bp(토큰 포인터: 1, min_bp:0)
6에서 RHS3에 들어갈 부분트리를 알았으니 계속 loop를 돌리며 진행할 수 있다. 이 시점에서 변수 lhs의 상태는 다음과 같다.

언제나처럼 다음 연산자를 파싱하면 +를 얻는다. 이는 왼쪽 결합력이 1으로, min_bp=0보다 크다. 따라서 +를 부모 노드로, 현재의 lhs를 왼쪽 노드로 하여 새로운 트리를 그린다.

RHS4를 구하기 위해 재귀호출을 시행한다. 토큰 포인터로는 다음 토큰의 위치인 5를, min_bp로는 +의 오른쪽 결합력인 2를 전달하면 된다.

expr_bp(토큰 포인터: 5, min_bp: 2)
Atom을 파싱하니 5가 나온다. loop를 돌며 연산자를 하나 가져오려고 하는데, 더 이상 가져올 수 있는 토큰이 없다! (Token::Eof) 따라서 5를 리턴하고 그냥 끝낸다.
expr_bp(토큰 포인터: 1, min_bp: 0)
8이 표현식의 끝에 도달하여 끝났으니, 다시 원래의 함수로 돌아온다. RHS4로는 그냥 5를 전달받았다. 따라서 최종 그래프가 만들어진다.

관찰

위의 예시를 실행해보면서 알 수 있는 점은 다음과 같다.

관찰 1. 알고리즘의 결과로 완성되는 구문분석 트리는 노드를 내려갈수록 edge의 결합력이 단조증가한다.
관찰 2. expr_bp가 다시 expr_bp를 재귀적으로 호출할 때, min_bp의 값은 단조증가한다.

따라서 알고리즘의 작동 방식을 다음과 같이 자연언어로 표현할 수 있을 것이다.

파싱을 진행하면서 나오는 새로운 연산자의 왼쪽 결합력(l_bp)이

min_bp보다 작으면(=직전 연산자의 오른쪽 결합력보다 낮으면) 관찰 1에 의해 이전 연산자의 오른쪽 자식으로 붙는 것이 불가능하다. 따라서 함수의 min_bp가 l_bp보다 약해질 때까지 호출 스택을 하나씩 탈출하게 된다.
- 호출스택을 탈출하는 것은 트리에서 노드를 하나씩 거슬러 올라가는 것과 같다.
- min_bp는 해당 노드를 루트로 하는 서브트리의 표현식을 왼쪽에서 끌어당기는 힘으로 생각할 수 있다. 즉, 새 연산자의 왼쪽 결합력(l_bp)이 어떤 서브트리의 min_bp보다 높으면 이에 해당하는 phrase는 그 왼쪽의 연산자가 대신 오른쪽의 새 연산자에 붙게 된다. 이것이 가능할 때까지 트리를 거슬러 올라가는 것으로 생각하면 된다.
- 트리를 거슬러 올라가면 새 연산자의 l_bp보다 낮은 min_bp를 만나게 된다는 보장이 있을까? 그렇다. 이는 관찰 2에 의해서 호출 스택을 하나씩 벗어날 수록 min_bp의 값은 단조감소하고, 맨 위로 올라가면 min_bp는 0인 것이 보장되어 있으므로 가능하다.
그렇지 않으면 단순히 직전 연산자의 오른쪽 자식으로 붙으면서 재귀호출을 이어나가게 된다.

결론

알고리즘을 이해하는 것은 항상 그것이 왜 동작하는지를 자신만의 직관으로 만들고 내면화시켜야 가능한 것 같다. 그런 점에서 Pratt 파싱은 꽤나 이해하기 어려운 알고리즘이었다고 생각한다. 필자는 며칠 동안 여러 번 구문분석 트리를 그리고 나서야 이해가 되었다. 이 글의 설명 또한 필자가 이 알고리즘을 이해한 방식일 뿐, 이를 더 간단하게 이해하고 표현하는 방법이 있을 것이라고 생각한다.

또한, 이 글에서는 사칙연산과 거듭제곱 정도만을 다루고 있지만, 알고리즘에 몇 줄을 더 추가하면 훨씬 다양한 표현식을 파싱하는 것이 가능하다. 이 글을 통해서 조금이나마 이해에 도움을 얻은 독자라면 Simple but Powerful Pratt Parsing을 마저 읽고, 괄호나 팩토리얼, unary - 등이 나오는 더 복잡한 표현식을 파싱하는 코드도 구현해보면 좋을 것 같다.

참고문헌

Simple but Powerful Pratt Parsing ↩