[Compiler] Shift Reduce Parsing

이번 포스트에서는 Bottom Up Parsing으로 해결하는 방법 중 하나인 Shift Reduce Parsing에 대해서 정리해보겠다. 

일단 지난 포스트에서 잠깐 다룬 것처럼 Bottom Up Parsing을 하기 위해서는 일종의 Handle, 즉 Production의 반대 개념인 Reduction을 적용할 substring을 찾는 과정이 필요했고, 이걸 마지막에 Handle Pruning이라고 했다. 그런데 한번 생각을 해보자. 어차피 substring으로 나누는 건데 reduction을 한 나머지도 일종의 substring이 아닐까? 물론 그게 정확한 terminal이다 라고는 말 못하지만 아무튼 진짜 terminal일 수도 있고, 혹은 Nonterminal과 Terminal로 결합으로 구성되어 있을 수도 있다. 그러면 Parsing 자체가 left to right으로 나가는데 그 방향대로 나가면 rightmost derivation을 취하면 되지 않을까? 

 Shift Reduce Parsing은 위의 방식을 따른 Parsing이다. 그대신 그 두가지의 substring, Parsing을 한 것과 안한 것을 가릴 수 있는 indicator가 필요하다. 그래서 이 indicator(또는 separator)를 기준으로 왼쪽이 이미 볼 수 있고, 기존에 주어진 grammar들로 reduction을 수행할 수 있는 것이고, 오른쪽이 아직 parser가 해당 string을 인지 못한 상태를 말한다. 그래서 parsing 과정이 진행되면서 이 indicator가 왼쪽에서 오른쪽으로 shift 하면서 이뤄진다. 여기서 shift가 나오고, 결국 이런 과정을 모두 통칭해서 Shift Reduce Parsing이라고 하는 것이다.  참고로 지금 진행되는 Parsing 방식이 left-to-right 형식을 취하면서 rightmost derivation을 수행하기 때문에 다른 말로 LR Parser라고도 할 수 있다. 

 shift는 앞에서도 설명했다시피 separator가 왼쪽에서 오른쪽으로 움직이는 과정을 말한다. 

쉽게 말해서 ABvC까지 분석했는데 대체할만한 Reduction이 없을 경우 위와 같이 separator를 한칸씩 움직이는 것이다. 그런데 Bottom Up Parsing 자체가 Reduction을 통해서 root를 node를 찾아가는 것이기에 이렇게 분석하다가 같은 grammar가 있을 경우에는 한 String으로 줄여야 할 것이다. 가령 T->Cx 라는 구문이 있으면 말그대로 reduce가 가능한 것이다. 

그럼 앞에서 언급한 예제인 int * int + int 예제를 이 Shift-Reduce Parsing에 적용시켜보면 다음과 같이 풀 수 있는 것이다.

여기서는 빨간 Bar가 separator가 된다. 조금더 이해가 쉽게 하려면 이것도 일종의 stack이라고 보면 된다. 다들 알다시피 stack은 Last In First Out을 구조를 띄는데 말그대로 Bar를 Top이라고 놓고 shift 가 일어날때 마다 stack에 집어넣는(push) 꼴이라고 생각한다. 그러고 reduction이 일어날때마다 stack에 있는 걸 빼는 모양(Pop) 형태로 보면 된다. MIT Lecture Note에 보면 이 같은 과정이 잘 묘사되어 있어서 소개해본다. 일단 이런 grammar가 있다. 

이렇게 우측 상단에 grammar가 정의되어 있고, 입력으로 하단에 있는 걸 넣고자 한다. 만약 Shift Reduce 방법을 쓴다면 좌측과 같이 Stack이 있다고 가정하면 되는 것이다. 그러면 맨처음에 shift에 의해서 num이 stack에 들어갈 것이다. 

그러면 parser는 num을 본 상태이므로 reduction 중에 num에 해당되는 것이 있는지를 찾아본다. 찾아보면 Expr -> num 이라는게 하나 있다. 그러면 stack에 있는 num은 pop이 되면서 대신 Expr이 들어가게 된다. 

다음은 Bar가 shift된 상태이므로 stack에는 * 연산자가 들어갈 것이고, 역시 이건 reduction에 의해서 Pop이 되고 대신 Op가 들어가게 될 것이다.

이런식으로 진행하다면 막히는 부분이 바로 괄호 부분 안이다. 이 부분도 똑같이 하다가 중간에 안의 content가 reduction 되는 경우가 발생한다. 

그러면 Left Bracket 다음에 나오는 Expr Op Expr 는 Expr로 Reduction을 취할 수 있다.

그러면 이것도 마찬가지로 Reduction을 취할 수 있고, Bar가 맨 끝까지 간 상태에서는 Stack의 state는 다음과 같이 되어 있을 것이다.

그런데 여기가 끝이 아니다 Bar가 끝까지 상태이더라도 Parsing이 끝난 상태가 아니고 Parser가 leftString에 뭔가가 있다고 인지를 한 상태인 것이다. 그리고 마지막 stack을 살펴보면 최종적으로 Expr Op Expr도 Expr으로 Reduction을 취할 수 있는 것을 발견할 수 있다. 그래서 최종적인 결과는 다음과 같이 된다. 

이 결과를 통해서 우리는 Shift Reduce Parsing의 과정과 Parse Tree를 그릴 수 있었다. 지금 위의 그림이 Tree의 형태라고 보기에는 조금 복잡해보이지만 바르게 보면 다음과 같이 된다. 

그런데 사실 지금 소개한 것은 평범한 Shift Reduce Parsing이다. 그런데 그냥 무작정 처음부터 규칙에 따라서 Shift & reduce를 실행하면 안된다는 것을 잘 알고 있다. 상황에 따라서 Reduction을 어떤 걸 수행해야 될지 모르는 경우가 발생하기 때문이다. 가령 A-> a 라는 grammar가 존재하고 또는 B-> a 라는 것도 있으면 어떤 것으로 Reduction을 취할 것인가? 그런 문제도 있고, 혹은 String은 인지한 상태에서 Shift를 해야할지 Reduce를 해야할지에 대한 문제가 발생하기도 한다. 전자와 같은 문제를 Reduce-Reduce Conflict 라고 하고 후자의 문제는 Shift-Reduce Conflict 라고 한다. 물론 이걸 해결하기 위해서 다양한 방법들이 있는데 보통 책에서 소개하는 것은 Top Down에서 했던 것처럼 Parsing시 다음 단계에 대해서도 예측을 해보자는 것이다. 거기서도 이런 걸 Look Ahead 라고 하는데 Bottom Up Parsing에서 이런 방식을 적용해서 만든 것이 LookAhead LR Parser, 줄여서 LALR Parser라고 한다. 물론 중간 단계로 거치는 Canonical LR (CLR) Parsing도 있는데 이 부분은 그냥 그렇다는 것만 알고 더 궁금한 사람은 찾아보길 권한다. 아무튼 더 자세한 건 다음 포스트에서 다뤄보려고 한다. 

Reference : 

MIT Lecture Note : Introduction of Shift Reduce Parsing -  (http://cons.mit.edu/sp13/ocw/L03.pdf)

UMD Lecture Note : LR(1) Shift Reduce Parsing - (http://www.cs.umd.edu/class/spring2009/cmsc430/lectures/lec07.pdf)