[Compiler] Bottom-Up Parsing

이번에 다룰 내용은 Bottom up Approach를 통해서 Parsing하는 Bottom up Parsing이다. 말 그대로 아래에서 위로, leaves에서 root를 찾아가는 방식이다. 그런데 사실 다른 compiler의 내부 구조는 거진 Top Down이 아닌 Bottom up 방식으로 구현되어 있다. 

 사실 Top Down 방식에서 직관적으로 봤을 때 가장 풀기 어려웠던 점이 무엇인지를 생각해보자. 개인적으로 생각했을 때는 absolute한 path를 찾는데 시간이 많이 걸린다는 것이다.  grammar라는게 가지치기를 통해서 여러 방향으로 뻗어나갈 수 있는 건데 Top Down 방식에서는 선택이 맞는지 틀린지를 직접 해보고 path를 결정할 수 있는 것이다. 또한 중간 결과가 맞았다고 해서 최종 결과가 틀리면 전체적으로 틀린 path로 판정되기 때문에 효율성도 없다. 물론 코딩하기도 쉽고, 코드의 크기도 작다는 장점을 가질 수 있지만 그것만 보고 가기에는 left recursion이나 Backtracking으로 인한 resource 낭비가 너무 심하다. 이 때문에 Bottom Up Parser가 널리 쓰이게 된 것이다.

 자 글 중에서도 말했지만 Bottom up 방식에서는 Left Recursion으로 인한 infinite loop가 발생하지 않는다. 말 그대로 결과로부터 뿌리를 찾는 것이기 때문에 다음에 무엇이 나올지에 대해서 고민하지 않아도 되는 것이다. 기존의 Top Down 방식에서는 이를 해결하기 위해서 Left Factoring이라는 방법을 제시했었지만 사실 이때 새로운 nonterminal을 생성해야 되서 조금 복잡한 경향이 있었다. 그대시 Bottom Up에서는 그냥 기존의 grammar 그대로 사용해도 되는 것이다.

 그래서 이번 포스트에서 주로 다루는 grammar는 다음과 같이 전제를 하고 정리해보려고 한다.

그런데 사실 눈썰미가 있는 사람이라면 여기서도 조금더 축약을 할 수 있을 것이다. 바로 T에 들어있는 nonterminal F를 대체할 수 있는 것이다. 그러면 최종적으로 다음과 같이 변하게 된다.

자 그럼 만약 int * int + int 라는 input이 들어왔다고 가정해보자.그러면 이 입력으로부터 grammar를 거꾸로 적용시키면 되는 것이다. 

여기서 우리가 최종적으로 원하는 건 과연 위의 입력 int * int + int 가 E에서 나온게 맞느냐는 것이다.  이걸 Top Down 방식에서는 이렇게 풀었다.

사실 이게 맞을 수 있었던 전제 조건 중 하나가 int * int  + int 가 E에 포함된 거라는 것이다. 사실 이 전제가 안 맞았더라면 입력은 다른 grammar와 적용해야 됬을지도 모른다. 반면 bottom up에서는 그럴 필요가 없는것이다. 그런데 여기서 여기서 유심히 볼게 하나 있다.

왼쪽에 있는 tree가 Top Down Parsing Tree이고 오른쪽이 Bottom up Parsing Tree이다. 왼쪽은 아래로 내려가면서 증가하지만 오른쪽은 그 반대이다. 왼쪽은 nonterminal안에 nonterminal이 생성되어 증식하고 있지만 오른쪽은 오히려 하나로 줄어들고 있다. 바로 이런걸 Production 과 Reduction이라고 한다.  Top Down에서는 Root로부터 Production을 통해서 input과 stack의 결과가 같은지를 비교하지만. Bottom Up은 input에서 Reduction을 통해서 최종 root와 비교하는 것이 목적이다. Bottom Up Parsing에서는 여기서 소개한 Reduction과 뒤에서 소개할 Shift 를 통해서 Parsing을 한다. 이 부분은 조금 뒤에서 다루기로 하고...

 아무튼 Bottom up Parsing도 하나의 Parsing 기법 중 하나이기 때문에 나름의 Parse Tree가 나온다. Top-Down과의 차이라면 입력부터 만들어나간다는 것이다. 

그러면 결국 관건은 Reduction을 언제 하느냐, 어떤 걸 reduction을 취하느냐 인 것이다. 이걸 위해서 필요한 개념이 바로 Handle이다.

Handle은 Parsing 시 초점을 맞출 substring을 말한다. 정의대로 설명하면 production 의 결과물과 동일한 substring인데 Bottom up 방식에서는 당연히 reduction의 입력과 동일한 substrng이라고 말할 수 있겠다. 어차피 앞에서 소개했던 것처럼 production과 reduction은 서로 반대되는 개념이기 때문이다. 앞의 예제를 가져오자면 다음과 같이 handle을 정의할 수 있는 것이다.

 Top Down 방식에서는 Production 시 leftmost 에 맞춰서 derivation을 해야 했었다. 물론 이 때문에 발생하는 Left Recursion 문제도 야기되곤 했다. 그런데 위와 같이 handle을 사용할 때는 그런 leftmost에 맞춰서 parsing을 할 필요가 없다. 딱 위의 reduction을 보기만 해도 알 수 있다. leftmost derivation을 취했다면 int1이 분해될때까지 기다려야 했을 거다. 그런데 그러면 결과가 어떻게 나왔을까? 아마 E*int2가 나왔을 것이다. 그런데 우리가 이런 파싱으로부터 얻고자 했던 건 input이 E로부터 나올 수 있냐, 즉 root가 E냐를 판단하는 것이다. 당연히 E에서 E*int2 같은 건 빼올 수 없기 때문에 Parsing시 leftmost를 굳이 준수할 필요가 없다. grammar중에서 입력과 일치하는 게 있으면 그걸 reduction시키면 되는 것이다. 보통 이런 과정을 Parse Tree에서 가지를 친다고 해서 Handle Pruning이라고 한다. 어차피 Handle에 관해서 원하는 것을 찾고 가지를 reduction 한다고 생각하면 좋을 거 같다. 조금만 더 예제를 살펴보자. 만약 rightmost derivation을 취한 grammar 중에 다음과 같은 내용이 있다.

이게 의미하는 것은 Start String에서 rightmost Derivation을 취하면 두번째를 얻을 수 있고, 여기서 A->β 라는 grammar를 활용하면 세번째까지 갈 수 있다는 것이다. 그런데 우리가 세번째에서 첫번째 S로 돌아가기 위해서는 앞에서 언급한 Handle을 적용해야 한다. 바로 두번째에서 세번째로 넘어올 때 이용했던 production을 활용하면 되는 것이다. 이 때 A를 αβω의 handle이라고 하고 이 상황을 그림으로 표현하면 다음과 같다.

 여기서 Handle Pruning은 어떻게 할 수 있을까? 이런 과정이라면 생각하면 된다. 

위의 식은 rightmost derivation의 과정을 쭉 나열한 것이다. 우리가 시작해야 할 부분은 ω 인데 이걸 γ 라고 대체하고 시작해보면 된다. 일단 γ(n) 대신에 β(n) 을 집어넣고 사전에 정의되어 있는 production A -> β 를 이용해서 β(n) 대신에 A(n)을 넣어버리면 우리는 그걸로 γ(n-1)을 구한 것이다. 또 γ(n-2)을 구하기 위해서는 앞에서 나열한 방법들을 반복해서 수행하면 되는 건데 이것도 일종의 Pruning인 것이다. 이렇게 하면 최종적으로 γ(0)을 구할 수 있을 것이고, 그게 Start String과 같다는 것만 보이면 우리가 Bottom up Parsing을 통해서 구하고자 했던 것을 얻을 수 있을 것이다. 

 잠깐동안의 예제를 통해서 Bottom up Parsing에 대해서 정리해보았다. 사실 말이 거창한거지 Parsing의 기법을 Top Down에서 Bottom up으로 취했다는 것일뿐 기본적으로 Production과 Reduction의 적용과 Pruning만 처리할 줄 안다면 이해하기 쉬울 수 있다. 문제는 이런 Bottom up Parsing을 방법론적으로 적용했을 때다. 말이 쉬운거지, 이걸 구현하는 것은 오히려 더 복잡하고, String에 대해서 포괄적으로 처리하기 위해서는 여러가지 상황에 대해서 고민해봐야 한다. 그래서 아마 다음 포스트에서는 그런 방법 중 하나인 Shift & Reduce Parsing에 대해서 조금 이야기 해보고자 한다.