[Compiler] Viable Prefix of Shift Reduce Parsing

지난 포스트에 이어서 Shift Reduce Parsing에 대해서 조금더 이야기 해보도록 하겠다. 

어차피 Shift Reduce 방식도 전형적인 Bottom Up Parsing 중 하나이므로 substring에 대한 handle이 존재할 것이고, 그 handle로부터 pruning을 해나가면서 최종적으로 root node를 찾아나가는 것이 목적이다. 그런데 문제는 input string 중에서 어떤 걸 handle이라고 정의할 것이냐는 것이다. 

 지금 우리가 다루고 있는 내용은 지난 포스트 중에서 나왔지만 Context Free Grammar(CFG)를 바탕으로 설명되고 있다. 사실 가장 이상적인 Parsing이라면 한번에 handle을 인식하고 그에 따른 terminal string으로 바꿔주는 건데 지금까지 한 걸 보면 뭔가 단계를 나눠서 답을 찾아갔다. 당연히 이에 따른 처리 시간 증대는 어쩔 수 없이 감당해야 된다. 정확히 말하면 이렇게 한번에 처리할 수 있는 algorithm이 존재하지 않는다는 것이다. 그래서 이를 조금더 보완하기 위해 적용한 개념이 바로 Heuristic 이라는 것이다. 쉽게 말하면 정확한 답이 아닌 근사치를 찾아 답이라 정의하는 기법인데 확률적으로 그 근사치가 답과 매우 유사하기 때문에 많이 사용된다. 물론 이에 대한 예외도 있기 때문에 그것에 대한 처리도 따로 해줘야 되는 것도 필요하다. 그래서 보통 이런 건 바이러스 탐색시 많이 응용된다. 수백만 크래커가 만드는 이상 바이러스나 악성코드는 동일하지 않다. 하지만 기본적인 형태는 나눠져 있으며, 그런 형태를 사전에 백신에 인식시켜두고 같은 패턴 검사를 하게 한다. 물론 이 패턴과 유사한 코드는 바이러스라고 추측하는게 바로 heuristic의 정의이다. (물론 백신에 Heuristic이 적용되어 있다 해서 무조건 좋은 건 아니다. 가끔은 정상적인 프로그램도 패턴이 유사하다고 해서 바이러스로 인지하는 경우가 발생하는 경우도 있다....) 

 그런데 지금 이 얘기를 듣고 나면 왠지 Parsing시에도 적용할 수 있지 않을까? 뒤에 parser로부터 인식되지 않은 string을 배제하더라도 기존에 인식된 string만 가지고 그 root node를 찾아나갈 수 있게끔 말이다. 그래서 다음과 같이 

input string이 있으면 ѡ 를 parser가 인지하지 않은 상태에서 처리를 수행하자는 것이다.  이 때 α 를 viable prefix , 굳이 우리말로 번역하자면 선행자라고 한다. 당연한 이야기이고 위에도 나와있다시피 viable prefix도 우리가 지금까지 해왔던 일반적인 substring의 개념이며, 물론 지난번에 사용했던 Shift Reduce Parsing에도 똑같이 적용할 수 있다. stack에 viable prefix이 들어있도 이게 error가 나는 전혀 새로운 개념이 아닌 것이다. 또 Prefix에 속해있으면 당연히 Handle에도 속해있다는 말도 할 수 있다. 

 그러고 보면 이 viable prefix도 우리가 맨 처음에 다뤘던 Regular Expression으로 표현할 수 있는 Regular Language의 범주에 들어간다고 할 수 있다. 사실 이게 당연한 개념이긴 하지만 시사하는 바가 크다. regular Language로 표현할 수 있다는 말은 그 포스트에서도 다뤘지만 이걸 Finite Automata로도 찾을 수 있다는 것이다. 결국 맨처음에 가졌던 질문이 Handle을 어떻게 판단하냐에 대한 답은 바로 viable Prefix가 Regular Language이기 때문에 Finite를 적용할 수 있고, 그중에서도 확실한 답을 찾기 위해서 Deterministic Finite Automata 를 쓰면 된다는 추측을 할 수 있게 된다. NFA와 DFA에 대해서 조금 가물가물한 사람은 이전 포스트를 참고하길 바란다.

2013/03/25 - [About School/About Compiler] - [Study] NFA / DFA

그래서 결과부터 말하자면 이걸 만들겠다는 것이다.

조금 복잡하긴 하지만 이 과정을 순차적으로 나가보려고 한다. 

우선 필요한게 있다. DFA를 구하기 위해서는 답이라고 생각할 수 있는 집합군이 바탕에 있어야 가능하다. 물론 이걸 구해주는 것은 DFA의 전단계인 Non-Deterministic FA 이다. 그리고 NFA를 구하기 위해서는 말그대로 정답의 후보군을 나열해야 한다. 당연히 지금 수행하고 있는 과정에서는 Grammar들의 Production들이다. 이걸 구해주는 것이 바로 LR(0) 인데, 어디서 많이 보지 않았나? 바로 현재 LL(1)에서 나왔다시피 LookAhead 를 나타내는 level이 0인 것이다. 그말은 즉, 선행으로 인식하는 과정없이 현재 상태에서 item을 뽑는다는 것이다. 예는 다음과 같다. 

이걸로 파생될 수 있는 모든 item들을 바로 LR(0)로 뽑아낼 수 있다는 것이고, 보통 T->T+E 과 T->(E) 으로 나누겠지만 LR(0)는 인식할 수 있는 모든 substring을 나열해야 되기 때문에 다음과 같이 구할 수 있다.

여기서 ∙ 가 나타내는 것은  ∙ 이전까지 LR(0)로 인식했다는 것이다. 어떻게 보면 이전포스트에서 다뤘던 Shift Reduce Parsing의 Bar가 움직이는 것과 비슷하다고 볼 수 있다. 결국은 이 모든 것이 다 T를 표현하는 production이자 item인 것이다. 여기다 한가지 special case인 

   X-> ε  이면  X-> ∙  

 라는 것까지 포함시키면 LR(0)에 대한 item을 모두 구할 수 있고, 곧 이게 다 grammar라고 할 수 있을 것이다.  자 그럼 실례에선 어떻게 적용할 수 있을지 보자.

위와 같은 production이 주어져 있는 상태에서 input으로 (int) 가 들어왔다고 가정하자. 그러면 (int) 에 대한 Shift Reduce Parsing을 수행할 수 있는데  (int| ) 까지 shift를 수행하게 되면 여기서 (E|)으로 Reduction을 취할 수 있다. 하지만 우리가 Shift Reduce Parsing을 마치려면 정확히 close Bracket인 ) 까지 읽어야 한다. 그런데 이 과정을 앞에서 언급한 Viable Prefix를 통해서 찾자는 것이다. 그러면 앞에서 언급한 대로라면 전체 (E)에서 (E 는 T->(E)의 viable prefix라고 할 수 있다. 그러면 앞에서 언급한 T에 대한 LR(0) item 중에서 (E 에 해당하는 요소가 있는지를 찾아보는 것이다. 그러면 마지막쯤에 T->(E∙)가 있는 것을 볼 수 있고, 이걸 통해서 DFA를 구하는게 최종 결과물이 되겠다. 

  한가지 예를 더 살펴본다.

위와 같이 정의되어 있는 item들이 있는데 input으로 (int*int)이 들어왔다고 가정하자. 그러면 끝까지 다 parsing 할 필요없이 viable Prefix를 사용하자는 것이다. 그러면 딱 여기까지 하면 된다. 

그러고나서 각각의 string에 대한 prefix를 정의해본다. 그러면 맨처음에 나오는 open bracket은 T->(E)에 대한 prefix라고 할수 있고, 그리고 우리 눈에는 없지만 (와 int 사이에는 empty string도 존재한다. 앞의 정의에 따르면 empty string은 그냥 ∙에 대한 prefix라고 보면 된다. 이런식으로 순차적으로 적용하면 다음과 같이 되는 것이다. 

이전에도 말했다시피 일종의 stack내에서 push와 pop이 이뤄지는 형태라고 했다. 그러면 stack안에 들어있는 item으로 그 다음 걸 추정해보자. 그러면 다음과 같이 나올 것이다.

결국은 item에 들어있는 내용을 바탕으로 다음 item을 판단하고 그에 대한 state transition이 이뤄지는 것이다.

자 그럼 지금까지 다룬 과정을 총집약해보자면 string에 대한 Shift Reduce Parsing을 하기 위해서는 Viable Prefix가 필요하고, 무턱대고 구하기가 힘드므로 이 과정을 Finite Automata의 힘을 빌리자고 했다. 답을 구하기 위해서는 DFA를 유추해야 되는데, 그전에 답의 집합군인 NFA를 구하는 과정이 선행되어야 하며, 이말이 곧 LR(0)의 item을 찾자는 말이 된다. 그런데 지금 보면 알다시피 state에 대한 transition table이 필요할 것 같다. 그러면 이 과정을 전에 다뤘던 예제를 통해서 하나씩 적용해보자.

 참 이 과정을 하기 위한 선행 조건으로 E에 대한 augmented Grammar를 생성해둔다. 별 의미가 있는 건 아닌데 사실 우리가 구해야 되는 건 root node가 E가 아닌 Start State인 S 인 것이다. 이중 S`이 S로 되는 과정까지 고려해 둔 것이다. 나도 정확히는 모르지만 아무튼 그냥 선행과정이라고만 알아두면 좋을 거같다. 그러면  원래의 grammar인 

는 다음과 같이 수정되고 여기서부터 NFA를 구하게 될 것이다. 그러면 우리가 이전에 다뤘던 내용 중 Tompson`s Contruction Algorithm을 적용해볼 수 있다.

그럼 transition은 여기서부터 시작할 수 있을 것이다..

<빈공간이다....>

일단 E와 같은 State는 transition시 empty string으로 움직일 수 있는 E -> ∙T 혹은 E -> ∙T + E 일 것이다. 또는 정말로 E가 끝이라고 맺음을 지을 수도 있는 것이다. 이때의 transition은 다음과 같다.

먼저 하단 부에 있는 E -> ∙T 부터 보자. 일단 T와 state가 같은 것은 T -> ∙(E), T->∙int, T->∙int*T 이고 여기는 empty string으로 transition할 수 있다. 혹은 앞의 상황과 마찬가지로 T를 그대로 인식하고 끝내버릴수도 있다.

자 그 다음은 E->∙T+E를 풀어볼 차례다.다음으로 인식될 것은 T인데 T와 State transition이 이뤄질 수 있는 부분은 두군데이고, 이미 그림상에 나와있다. 또는 T를 인지하고 E->T∙+E 로  transition시킬 수도 있다. 

그러면 이제 transition을 수행할 수 있는 부분이 4군데가 있다. 맨 처음은 bracket이 있는 부분의 transition은 다음과 같이 이뤄진다. 

복잡하긴 한데 그렇게 못따라갈 정도는 아니다. 아무튼 NFA를 다 구해보면 다음과 같이 나온다.

그러면 이제 궁극적인 DFA 유추를 해보면 되는데 이건 NFA에서 DFA로 바꿔주는 Subset Contruction Algorithm을 사용하면 된다. 그런데 오히려 처음 DFA를 소개할 때보다 더 직관적이어서 이해하기가 쉽다. 우선은 주어진 grammar를 다 나열을 한다. 

여기서 인지된 string을 하나씩 빼주면 되는 것이다. 즉 ∙을 한칸씩 움직이고 state가 같은 것들은 묶어주자는 것이다. 그러면 최종적으로 맨 앞에서 소개한 결과를 얻을 수 있다.

참고로 딱 보면 너무 복잡한 내용 때문에 막상 좌절감이 들기에 반복적인 연습과 좌절(!)을 겪어야 익힐 수 있는 내용이라고 한다. 그게 얼마나 효과가 있을지는 모르겠지만 말이다.

사실 맨처음 NFA/DFA를 배우고 Natural Language로 표현할 수 없는 것 때문에 Context Free Grammar를 쓴다는 이야기를 듣고 왜 그럼 NFA/DFA를 미리 가르치는 걸까 하는 의문이 들곤 했었는데 그 때 배웠던 내용을 이런식으로 CFG내에서도 적용할 수 있는 모습을 보면 신기하다. 뭐 이러면서 배우는거니까... 이번 내용은 여기까지..