[Compiler] Simple LR Parsing

계속해서 shift reduce Parsing에 대해 다뤄보고 있다. 지난 포스트에서 소개한 건 현재 주어진 Production을 통해서 DFA를 구하는 LR(0) Parsing이었다. 잠시만 Rewind해보자

사실 이 건 정확한 답이라고 할 수 없다. 그때도 언급했었지만 효율적인 algorithm이라는 건 없고, heuristic을 활용해서 전개하는 방식이 위와 같은 건데 갑자기 왠 헛소리냐라고 생각할 수 있다. 그런데 우리가 간과한게 있으니 바로 conflict라는 것이다. 

 Shift Reduce Parsing에서는 두가지 conflict가 있는데 하나는 Reduce-Reduce conflict 이고 다른 하나는 Shift-Reduce Conflict이다. 가령 다음과 같은 item이 있다고 가정해보자.

X->a

Y->a

위와 같은 production이 있을 때 production의 반대인 reduction을 통해서 축약하고자 할때는 어떤 것을 따라가겠는가? 여기서 ambiguity가 발생한다. 이걸 reduce-reduce Conflict라고 하고 Shift-Reduce Conflict는 다음과 같은 케이스이다.

X->a

Y->abc

자 이상태에서는 a를 reduction을 취해야 할 것인가? 아니면 shift를 취해서 다음 string을 인지해야 될까? 여기서도 Ambiguity가 발생한다. 

그러면 이 걸 바탕으로 위의 DFA에서 어떤 부분이 문제가 되는지를 찾아보자 initial 상태에서는 상관없지만 하나의 string이 인식된 상태 즉 ∙ 이 한단계 거친 상태를 찾으면 된다. 월리를 찾아라는 아니지만 딱 두군데에서 Shift Reduce Conflict가 발생한다. 

    

결국 두군데에서는 Shift할지 reduce를 할지가 참 애매한 것이다. LR(0) DFA는 사실 이런 부분에 대한 고민 없이 그냥 답을 찾은 것이기 때문에 이를 해결할 수 없다. 그래서 사람들이 생각해낸 방법 중 하나가 언제 shift하고 언제 reduce할지를 재정립해서 하나의 table로 만들어놓자는 것이다. 그래서 ambiguity가 발생할 때 참조해서 conflict를 해소하자는 아이디어인 것이다. 물론 그렇다고 완벽하게 없앨 수는 없지만 그래도 성능 향상에는 도움이 될 것이다. 바로 이같은 방식을 Simple LR, 줄여서 SLR Parsing이라고 한다. 여기서도 LookAhead 개념을 붙여 SLR(1)이라고도 사용할 수 있다.

 그럼 이제 Table을 어떻게 만드냐는 것이 관건인데 사실 이름에서 나오듯이 해결 방법이 매우 simple하다. 지금 발생하고 있는 conflict인 Shift-Reduce Conflict나 Reduce-Reduce Conflict 에서 문제로 야기되는 공통적인 요인이 무엇인가에 대해서 고민해보면 우연하게도 둘다 Reduce 과정에서 Ambiguity가 발생하는 것이 눈에 띈다. 그래서 SLR의 해결 방법은 Reduce를 할 때 조건을 하나 더 첨부하자는 것이고, 그 조건으로 next input이 Production 의 FOLLOW에 들어가는지를 확인하자는 것이다. 

 즉 다시 말하면 state s가 X -> β∙  안에 들어 있으면서 추가로 t 가 FOLLOW(X) 에 속해 있어야 X-> β  를 reduce 할 수 있게끔 하는 것이다. shift에 관해서는 동일하게 그냥 state s가 X-> β∙tω   안에 들어있는지만 확인하면 된다. 그래서 기본적인 form은 똑같되 Conflict가 발생하는 것에 대해서 FOLLOW만 정해주면 장땡이 되는 것이다. 

  

그러면 이를 바탕으로 SLR Parse Table을 만들어보겠다. 약식으로 각 state에 번호를 붙인다. 

이상태에서 입력을 int*int 를 준다고 하자 그러면 initial은 다음과 같이 작성할 수 있다. 

당연히 parser가 지금 입력으로 뭐가 들어왔는지 알기 위해서는 shift가 수행되어야 한다. 그러고 나서 int가 인지되었으므로 state는 3번으로 transition된다.

자 이제 첫번째 conflict가 발생한다. 그런데 next input이 *가 들어오는데 이건 FOLLOW(T)에 속하지 않는다. 그렇기 때문에 이때는 reduce가 아닌 shift를 수행하게 될 것이다.

그럼 쭉쭉 넘어가서 다음 conflict가 발생하는 부분으로 가보자 그러면 이때 stack에는 int*int | $ 가 있을텐데 이때 다음 input은 $ 이다. 그런데 다들 알다시피 $,즉 end of Input은 모든 FOLLOW() 에 포함된다. 그래서 이때는 shift가 아닌 reduce가 일어난다. 그러고 난 후에는 stack에는 int*T|$ 가 남게 될 것이다. 

이런 식으로 쭉쭉 FOLLOW에 next input이 포함되어 있는지를 확인해보면서 작성하면 최종적으로 아래 결과를 얻을 수 있다.

그런데 사실 위와 같이 하는 것은 어쩌면 불필요한 작업을 하는 것일 수도 있다. 또한 input이 들어온 것에 대해서 하나씩 분석한 것이기 때문에 다른 input이 들어왔을 때도 적용할 case를 만들어야 하는 것이다. 그래서 조금더 효율적으로 SLR Parsing을 구현하기 위해서는 그냥 필요한 케이스에 대해서만 table화해서 transition시 참고하자는 것이다. 

이걸 가지고 이제 Transition table을 만들면 다음과 같이 만들 수 있겠다.

이게 의미하는 것은 현재 state에 대해서 input이 non terminal인 경우의 transition table을 표현한 것이다. 즉 예를 들어서 현재 state가 1번인데 E가 들어오면 2번 state로 넘어가라는 의미이다. 코드 상에서도 해당 part로 바로 넘어가게 하는 구문을 goto 구문이라고 하는데 여기서도 이 table을 goto table이라고 한다. 그런데 여기에는 nonterminal이 들어왔을 때만 정의가 되어 있지 terminal이 들어왔을 때는 표현이 되어 있지 않다. 그래서 이에 대한 table도 만들어야 되는데 보통 그 table은 action table이라고 한다. 흔히들 Simple LR Parsing Table이라고 하는 것은 이 Action Table과 Goto Table이 합쳐진 것을 말한다. 그래서 table initialization은 다음과 같이 된다.

ACTION이 의미하는 것은 현재 state에서 Terminal이 들어왔을 때 어떤 state로 transition 하겠느냐는 것을 알려주는 것이다. 그래서 여기에 앞에서 열심히 적용했던 Shift와 Reduce를 삽입해주면 된다. 정답은 나와있지 않은데 내 나름대로 작성해본 건 다음과 같다. 

아직도 모르는 내용들이 많지만 내일이 시험이라서 이정도만 정리하고 다시 처음으로 돌아가고자 한다. 

Reference 

Univ of Washington : SLR Parse Table - (http://courses.washington.edu/css448/zander/Notes/SLRtable.pdf)