[Compiler] Top-Down Parsing

지난 포스트에서 Abstract Syntax Tree 즉, derivation을 생략한 필수적인 정보만 남긴 Tree를 정리했었고, 이걸 지금까지 하고 있는 Top Down Parsing에 적용해보는 것을 이번 포스트에서 정리해보려고 한다. 

 Top Down Parsing이라는 것은 말 그대로 Tree의 맨 위에서부터 차례대로 Parsing한다는 의미를 가지고 있다. 그런데 우리가 보기 쉽게 Tree 형식으로 만들어놓는 것이지, 실제로 compiler가 볼때는 왼쪽에서 오른쪽으로 차례대로 string을 검색하는 형식을 취한다. 그 때 이걸 left Recursive라고 언급했었고, 바로 이런 방식때문에 Top Down Parsing을 Recursive Descent Parsing이라고 하기도 한다. 

 보통 Parsing을 하게 되면 바로 이전에 다뤘던 AST 처럼 일종의 Parse Tree를 그리는 과정이 선행되는데, 보통 Parsing을 하고난 결과물을 하나의 node로 표현할 수 있다.이 때 보통 더이상 쪼갤 수 없는 terminal들을 외곽에 leaf node로, 계속 쪼갤 수 있는 nonterminal들을 안쪽에 두고 계속 derivation을 거치게 한다. 그래서 terminal로만 이뤄진 결과물을 찾는 것이 목적이다. 그림으로 표현하면 다음과 같다. 

자 그럼 Top-Down Parsing의 예를 한번 찾아보자 다음과 같은 grammar가 정의되어 있다. 

이때 ( int ) $ 라는 set of string이 input으로 들어왔다. 이 set의 parse tree를 그리라면 어떻게 할 것인가?

가장 쉬운 방법은 하나씩 해보는 방법이다. 첫번째로 주어진 E->T 부터 아래로 쭈욱 내려가는 것이다. 그러면 다음과 같이 될 것이다.

당연히 주어진 set은 left bracket으로 시작하므로 fail을 return 할 것이다. 그런데 코드의 구조상 어떤 결과가 나올지 모르기 때문에 이 같은 과정을 수행한 후 다시 돌아가서 또다른 검증 과정을 거치게 된다. 알고리즘에서는 이같이 하나씩 답을 찾을때까지 조건을 검증하는 방법을 back tracking 이라고 한다. 그래서 쭉쭉 해보면 답을 얻을 수 있다. 

결과적으로 Top Down 방식은 애초에 어떤 terminal로 구성되어 있는지 알수가 없기 때문에 해당 Node들을 하나씩 검증해야 한다. 그래서 backtracking 과정이 필요한 것이다. stanford 대학에서 제공하는 dragon book lecture note에 보면 다음과 같은 예제가 제공되어 있다. 오히려 이게 과정을 묘사했기 때문에 이해하기 더 쉬울 것으로 보인다. 다음과 같은 grammar가 존재한다.

여기에 bcd에 대한 parse tree를 그려보려고 한다. 그러면 아마 다음과 같은 과정을 거치게 될 것이다. 

결국 자기가 원하는 답이 아니면 다시 돌아가서 수행하는 일련의 과정이 backtrcking이 되는 것이다.

그럼 위의 tree를 하나의 코드로 구현하려면 어떻게 해야 될지가 고민된다. 그런데 사실 위에서 언급한 내용들이 다 포함되어 있으면 된다. 

우선은 현재 string을 분석하는 TOKEN이라는게 필요할 것이고 그 TOKEN의 다음 것을 가리키는 포인터도 필요할 것이다. 또한 지난 포스트에서 AST를 코드로 구현했을 때와 마찬가지로 하나하나의 function으로 만들어서 처리하면 될 것이다. 그래서 간단한 pseudo 코드로는 다음과 같이 나올 것이다. 

이렇게 하면 token을 분석하는 부분에서는 E()와 T()만 호출해서 사용할 수 있다. 

 그런데 여기서 유의 사항이 있다. 맨 앞에서 Left Recursive Grammar라고 했는데 이전 포스트중에 보면 Grammar 중에 자신과 같은 Nonterminal이 있으면 발생할 수 있는 문제가 있는데 그게 Left Recursion 현상이다. 위와 같이 BackTracking을 하다보면 계속 무한하게 분석하는 경우가 발생하는 것이다. 다음 케이스를 잠깐 본다.

E -> E+ int | int

위와 같은 grammar가 있고 여기에 해당하는 Top Down Parser가 있다.

이때 1+2 라는 string이 들어오면 어떻게 될 것인가 예측을 해보자. 그러면 backtracking에 의해서 E()는 E1()을 return 할 것이다. 그런데 문제는 E1() 내에서도 E()를 return 하는 것이고 결과적으로 이 과정이 무한하게 발생하는 것이다. 그래서 이를 해결하기 위해서 지난 포스트 중에 Left Factoring이라는 방법이 있다고 소개했었다. 이를 적용하면 이전 예제에서 발생하는 Left Recursion 현상으로 인한 infinite loop 가 발생하지 않는다.

 간단히 지금까지 다룬 내용을 정리하면 Top Down Parsing이라는 건 말 그대로 위에서 아래로 parse tree를 그리면서 결과를 찾아가는 방식이다. 이 와중에 틀린 결과가 나오면 바로 처음으로 돌아가 다시 수행하는 Backtracking에 대해서 언급했는데, 사실 Backtracking 방식은 약점이 존재한다. 바로 하나의 Token을 일일히 검증해보고 돌아가는 방식이기 때문에 시간이 많이 걸린다는 것이다. 또한 과정이 맞다고 하더라도 최종 결과가 틀리면 지금까지 수행한 결과가 필요없어지는 것이다. 사실 미리 이 결과가 틀렸다는 것을 알았으면 굳이 중간 과정을 수행하지 않고 다른 과정을 수행했을지도 모를텐데 말이다. 여기에 소비되는 computational power도 낭비일 수 있다. 이 때문에 뭔가 결과에 대해서 예측할 수 있는 프로세스가 필요했는데 이 방식이 Top Down 방식에 적용되어 Top-Down Predictive Parsing이라고 불리게 된다. 이 방법이 가지는 장점은 앞에서 낭비를 야기하는 backtracking이 없다는 것이다. 대신 backtracking을 대신할 만한 것으로 Parsing Table이라는 것을 만들어야 되는데 이 부분은 다음 포스트에서 계속 이어서 언급해보려고 한다.

Reference : 

Stanford Univ. Dragon book Lecture note - (http://dragonbook.stanford.edu/lecture-notes/Stanford-CS143/07-Top-Down-Parsing.pdf)