[컴파일러 이론] 5. Parsing table 만들기

 

 

이전 글에서 그냥 사용했던 parsing table을 만드는 법을 알아보자.

 

 

먼저 세 가지의 중요한 개념을 알아야한다.

각각 nullable, first, follow인데 하나씩 살펴보자.

---

Nullable, First, Follow

---

Nullable

어떤 $X$에 대해 derivation을 계속하여 empty string($\epsilon$)이 된다면 $X$는 nullable하다고 말한다.

아래의 예시에서 $X$는 nullable하다.

$X$→$ABC$

$A$→$\epsilon$

$B$→$\epsilon$

$C$→$\epsilon$

 

일반화해서 표현하면 아래와 같다.

정의 : {x | x→* $\epsilon$}

판단하는 방법 : 

$X$→$A_1 A_2 ... A_n$에 대해 $A_1, A_2, ... ,A_n$각각이 nullable하다면 $X$도 nullable하다.

 

---

First

First($X$)는 어떤 $X$에 대해 derivation을 계속해서 나올 수 있는 string들의 가장 앞 문자를 모아놓은 집합이다.

예시로 아래코드에서 First(X)는 First(A)를 포함한다.

만약 A가 nullable이라면  First(B)를 포함한다.

X→AB

 

정의 : First(x) = { t | x →* ty }

판단하는 방법 :

step1) terminal인 t에 대해, First(t) = {t} 이다. 즉 자기자신을 포함한다.

step2) $X$→$A_1 A_2 ... A_n$에 대해 $A_1 A_2 ... A_{i-1}$이 nullable하다면

First($X$)+=First($A_i$)

 

---

Follow

가장 복잡하다.

시작 symbol인 S에서 derivation을 시작해서 어떤 string이 만들어졌을 때 x라는 terminal 뒤에 terminal t가 있다면 

Follow(x)에 t가 포함된다.

시작 심볼로부터 만들어진 다른 문자열에서 x뒤에 y가 있다면 y도 포함된다.

 

정의 : Follow(x) = { t | S →* yxtz}

판단하는 방법 :

step1) Follow(S) = { $ } , 시작심볼 S의 follow는 끝을 의미하는 문자인 $로 초기화한다.

step2) $X$→$A_1 A_2 ... A_n$에서 $A_{i+1} A_{i+2} ... A_n$이 nullable이면

Follow($A_i$) += Follow(x) 이다.

step3) $X$→$A_1 A_2 ... A_n$에서 $A_{i+1} A_{i+2} ... A_{j-1}$이 nullable이라면

Follow($A_i$) += First($A_j$) 이다.

 

---

Parsing table을 위한 임시 table만들기

이제 위의 세 가지 속성을 통해 Parsing table을 만드는 과정으로 돌어가보자.

parsing table을 만들기 위해 임시 table을 하나 먼저 만들 것이다.

 

임시 테이블을 초기화 하는 법은 아래와 같다.

위에서 설명된 내용이 표현만 다르게 되어있는 것이다.

임시 표는 아래처럼 그리면 된다.

각 production의 왼쪽에 있는 문자들에 대해 first, follow, nullable을 계산하는 것이다.

초기화

주어진 CFG에 대해 위에서 설명한 과정들을 반복하여 계산하면 된다.

 

모든 production에 대해 수행했다고 끝이 아니고, 위 과정 중 S' 이 nullable하다는 것을 알았기 때문에,

S → ES' 의 식에서 Follow(E)에 Follow(S)가 포함되게 된다.

이렇게 얻어진 최종적인 표의 값은 아래와 같다.

이제 위의 표를 이용해 최종 목표인 Parsing table을 만들어보자.

다행히 임시표 → Parsing table과정은 간단하다.

 

parsing table은 세로 속성은 심볼들, 가로 속성은 terminal이다.

각 심볼(S,S',E)에 대해 First에 있는 terminal과 만나는 지점에 production의 오른쪽에 있는 내용을 넣으면 된다.

nullable이 true인 경우에는 follow에 해당하는 곳에 $\epsilon$을 넣으면 된다.

 

 

이전 글에서 봤었던 table이 완성되었다.

 

---

지금까지 다뤘던 내용은 LL1문법을 사용한 top-down parsing이었다.

LL문법 말고도 다양한 문법이 있는데 LR문법을 사용하는 bottom-up parsing은 top-down parsing보다 더 효율적이다.

 

다음 글에서는 bottom-up parsing을 알아보고, 간단히 다른 문법들도 살펴보자.