[Compiler] Parsing Table for Top Down Predictive Parsing

이번 포스트에서 다뤄볼 내용은 지난 포스트에서 언급했던 backtracking을 완전히 배제한 Predictive Parsing이다. 말 그대로 한단계 이후의 결과를 미리 예상하고 parsing path를 정하기 때문에 틀린 결과로 인한 backtracking을 할 필요가 없어진다. 보통 이런 개념을 lookahead라고 하고 몇단계를 미리 예상할 것이냐에 따라서 정도가 달라진다. 물론 그 depth가 커지면 그만큼 컴파일러의 성능도 나빠질 것이다. 그래서 일반적으로는 이 lookahead의 정도를 1로 둔다. 참고로 이런 Top Down parsing방식은 지난 포스트에서도 언급했었지만 왼쪽에서 오른쪽으로 가면서 분석하고(left-to-right) 왼쪽부터 derivation을 수행하기 때문에(leftmost derivation) 다른 말로 LL Parser라고 한다. 여기에 앞에서 언급한 lookahead의 depth 를 붙여서 LL(1) 이라고 하면 one-token lookahead Top-Down Predictive Parser (참 길다...) 라고 할 수 있겠다.

 그러면 어떤 방식으로 lookahead를 하냐가 관건인데, Predictive Parsing에서는 사전에 parsing table을 만들어서 다음에 어떤 token이 나올지를 찾는다. 물론 이 Token에 대한 Transition을 찾아야 되는데 이런 걸 FIRST()와 FOLLOW() 라는 두 함수로 나눠서 수행하게 한다. 어떻게 보면 일전에 다뤘던 Deterministic FA 의 수행과정과 유사하다고 볼 수 있다.

 일단 FIRST()와 FOLLOW()의 역할을 살펴보면 좋을 것 같다.

 FIRST()는 해당 token의 set 중에서 비교대상의 이전 terminal을 찾아주는 함수이다. 다시 말해 FIRST(A)라고 하면 A라고 하는 Set중에서 첫번째 Terminal을 찾아주는 것이다. 가령 다음과 같이 grammar가 있다고 치자.

A->aB

A->ac

그러면 FIRST(A) = a라는 결과를 얻게 하는 것이다. 다른 예제도 한번 보겠다.

S -> ( S ) S | ε

grammar가 위와 같이 정의되어 있는데 FIRST(S)를 구하면 위의 정의에 의해 { ( , ε  } 라는 결과를 얻을 수 있다. dragon book에 보면 그 절차를 다음과 같이 소개하고 있다.

• Algorithm to compute FIRST(X):
1. If X is a terminal, then FIRST(X) = { X }.
2. If X → ε is a production, then add ε to FIRST(X).
3. If X → Y₁ Y₂ ... Y_k is a production for k ≥ 1, and
      for some i ≤ k, Y₁Y₂ ... Y_i-1 derives the empty string, and a is in FIRST(Y_i), then add a to FIRST(X).
   If Y₁Y₂ ... Y_k derives the empty string, then add ε to FIRST(X).

 반대로 FOLLOW()는 비교대상 바로 다음에 나올 수 있는 terminal 들의 집합을 구해주는 함수이다. 그래서 FOLLOW(A) 라고 하면 A라는 Symbol 뒤에 나올 수 있는 Symbol들을 포함하는 것이다. 역시 간단한 예를 두가지 들어본다.

X -> YAaZ

 라는 grammar가 있는데 여기서 FOLLOW(A) = {a}라고 정의할 수 있다. 또한 grammar가 두개 있는 경우에도

X -> YAZ

Z -> aZ` 

라고 해도 FOLLOW(A) = {a} 라고 할 수 있다. 결국 바로 다음의 terminal을 찾는 것이 관건이 되는 것이다. 그런데 이렇게 하면 FIRST()와 FOLLOW()의 관계를 알 수 있을 것이다. 상황에 따라서는 어떤 Symbol의 FIRST는 어떤 Symbol의 FOLLOW가 될 수도 있다는 것이다. 이런 점을 활용하면 parse tree를 조금더 쉽게 찾을 수 있다. 다른 예제도 역시 소개한다.

S -> +SS | *SS | a ;

라는 grammar가 정의되어 있다. 여기서 FOLLOW(S)를 구할 수 있을까? 그러면 각각의 derivation을 구해보면 된다. 일단 a가 나올 거라는 것은 아는 것이고, S가 가지치기를 하다보면 결국은 +도 나올 수 있고, *도 나올 수 있다.그리고 그냥 S에서 끝날경우 input string의 끝을 의미하는 $도 들어있을 것이다. 그래서 결국 FOLLOW(S) = { + , *, a, $ } 라는 결과를 얻을 수 있다. 역시 Dragon Book에는 다음과 같은 수행과정을 소개하고 있다.

• Algorithm to compute FOLLOW(A) for all nonterminals A of a grammar:
1. Place $ in FOLLOW(S) where S is the start symbol of the grammar.
2. If A → αBβ is a production, then add every terminal symbol a in FIRST(β) to FOLLOW(B).
3. If there is a production A → αB, or a production A → αBβ, where FIRST(β) contains ε,
   then add every symbol in FOLLOW(A) to FOLLOW(B).

결국 FOLLOW에는 무조건 $가 들어가고 그 이후부터 뒤에 뭐가 나올 건지를 쭉 검토하면 된다. 이런 말보다는 직접 해보는게 좋을 거 같다.

FIRST(e)는 e의 첫번째 terminal을 찾으면 된다. 그런데 지금 e는 t와 e' 이라는 nonterminal로 구성되어 있기 때문에 하나씩 대입하면서 풀어야 한다. 그러면 첫번째 nonterminal인 t로 들어가면 거기도 역시 nonterminal인 f와 t'으로 구성되어 있다. 그러면 여기서도 f에 대한 first를 찾으면 된다. 그러면 나올 수 있는 것이 { (  , x  ,  y  } 가 된다. FIRST(e) = { ( , x , y }  

FOLLOW(e)도 비슷하게 하면 된다. 일단 마지막 input string인 $는 포함이 되어 있을 것이고 f 쪽을 보면 e의 다음이 ')' 로 끝나는 것을 확인할 수 있다. FOLLOW(e) = { $ , ) }

이런 식으로 nonterminal들의 FIRST와 FOLLOW를 구해보면 다음과 같은 표를 구할 수 있을 것이다.

자.. 앞에서도 말했다시피 Predictive Parsing을 하기 위해서는 위의 결과를 가지고 Parsing Table을 만들어야 한다. 하나씩 과정을 거쳐보도록 한다.

맨처음에는 Table template을 만들어야 하는데 이때 Row 쪽에는 nonterminal / Coloum쪽에는 terminal로 배치를 한다.

그 후 Production에 대한 first를 찾아서 하나씩 삽입해주는 것이다.

이런식으로 x y에 대해서도 삽입을 해주면 된다. 그러면 first(e)를 다 채우면 다음과 같이 된다.

그 다음은 e' -> +te' 인데 FIRST(+te') = { + } 이므로 이에 해당하는 걸 집어넣어주면 된다.

그 다음 grammar는 e' -> ε 인데 FIRST( ε ) 이라는 의미는 없으므로 이 때는 FOLLOW(e')를 찾아서 집어넣어주면 된다. 순차적으로 다음과 같이 들어간다.

이런식으로 채워 나가면 된다. 그러면 결과적으로 grammar를 parsing table 로 바꿔주는 게 될 것이다. 최종적으로 나오는 parsing table은 다음과 같다.    

위에서 나온 Pseudo Code 대로만 구현을 하면 위와 같이 table을 완성시킬 수 있다. 

그러면 이제 이 Table을 가지고 Parsing을 해야 되는데 이와 같은 Parsing Table이 있다고 가정한다.

여기서 입력을 int * int (정확히 말하면 int * int $)로 넣었을 때 어떤식으로 tree를 짤 수 있는지를 살펴본다. 앞에서 언급한 것처럼 Left-to-right 이기 때문에 왼쪽에 있는 int 부터 쭉 따라 내려오면 된다. 

일단 grammar를 보면 E->TE' 부터니까 시작도 E 부터 해보자. 그러면 int가 있는 쪽에서의 E는 TE'이므로 E는 TE'로  대체된다. 하지만 아직 terminal이 나오지 않았기 때문에 input은 그대로 살아있다. 그러면 int를 첫번째 string인 T에 맞춰보면 int T' 으로 대체할 수 있겠다. 그러면 기존의 E'도 살아있으니까 TE' 은 int T'E' 로 대체 될 것이다. 여전히 nonterminal이므로 input에서 없어지는 것은 없다. 그런데 여기서 input과 일치하는게 생긴다.현재  input으로 남아있는 것은 int * int 인데 비교대상으로 남아있는 것을 보면 int T'E' 이기 때문이다. 이러면 int는 terminal이므로 더이상 찾을 필요가 없어서 제거할 수 있다. 위의 parse tree 대로 하자면 leaf node로 빠지는 것이다. 

 이제 input에는 int가 빠진 *int 가 있을 것이고, 비교대상도 역시 int가 빠진 T'E' 가 있을 것이다. 자 그럼 다음으로 나오는 건 * 이므로 table에서 T'과 *가 맞는 부분을 찾으면 *T 로 대체될 수 있다는 것을 알 수 있다. 그러면 T'E'은 *TE'으로 대체할 수 있을 것이고 입력은 아직 찾지 못한 상태이므로 *int가 남아있다. 여기서 또 * 라는 terminal을 찾았으므로 또 제거할 수 있다. 

 그럼 이제 입력에는 int만 남게 되고 비교 대상은 TE'이 남아있다. 그러면 이제는 int 와 T를 비교하면 된다. 그러면 교차점에 intT' 이 있고 이걸로 대체할 수 있겠다.(TE' -> intT'E') 여기서 또 int가 일치하므로 제거될 수 있겠다. 이런식으로 하나씩 parsing을 하면 된다. 그 과정은 다음과 같다.

이렇게 Parsing Table을 통해서 주어진 입력의 terminal들을 찾았다.비교 대상을 일종의 stack이라고 생각하고 하나씩 쌓여가는 거라고 보면 조금더 이해가 쉬울 거 같다.

Reference : 

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

MIT OpenCourceWare Lecture note - (http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-035-computer-language-engineering-spring-2010/lecture-notes/)

Columbia Univ Lecture note - (http://www1.cs.columbia.edu/~aho/cs4115/lectures/13-02-20.htm)

York Univ - Parsing Table (http://www.cs.york.ac.uk/fp/lsa/lectures/parsetable.pdf)