1. 다음 두 문맥-자유 문법에 대해 각 논터미널 기호의 FIRST와 FOLLOW 집합을 구하세요.
1-1. 문법 $G_1 = (V_N, V_T, P, S)$ 는 다음과 같이 정의합니다.
$ S \rightarrow ABC \, \mid \, BCA $
$A \rightarrow abc \, \mid \, BC $
$B \rightarrow SAa \, \mid \, C $
$C \rightarrow \epsilon$
- FIRST
$\textrm{FIRST}(S) = \{\textrm{FIRST}(ABC), \textrm{FIRST}(BCA)\} $
$\textrm{FIRST}(A) = \{a, \textrm{FIRST}(BC)\} $
$\textrm{FIRST}(B) = \{\textrm{FIRST}(SAa), \textrm{FIRST}(C)\} $
$\textrm{FIRST}(C) = \{\epsilon\} $
$ B \to C$ 생성규칙으로 인해 $ B \overset{* }{\Rightarrow} \epsilon$ 이 성립한다.
$ A \to BC$ 생성규칙으로 인해 $ A \overset{* }{\Rightarrow} \epsilon$ 이 성립한다.
$ S \to ABC$ 생성규칙으로 인해 $ S \overset{* }{\Rightarrow} \epsilon$ 이 성립한다.
따라서
$\textrm{FIRST}(SAa) = \{ \textrm{FIRST}(S), \textrm{FIRST}(A), a \}$
$\textrm{FIRST}(BC) = \{ \textrm{FIRST}(B), \textrm{FIRST}(C) \}$
$\textrm{FIRST}(ABC) = \{ \textrm{FIRST}(A), \textrm{FIRST}(B), \textrm{FIRST}(C) \}$
$\textrm{FIRST}(BCA) = \{ \textrm{FIRST}(B), \textrm{FIRST}(C), \textrm{FIRST}(A) \} $
로 나타낼 수 있다.
$\textrm{FIRST}(S) = \{ \textrm{FIRST}(A), \textrm{FIRST}(B), \textrm{FIRST}(C) $
$\textrm{FIRST}(A) = \{a, \textrm{FIRST}(B), \textrm{FIRST}(C)\} $
$\textrm{FIRST}(B) = \{\textrm{FIRST}(S), \textrm{FIRST}(A), a, \epsilon\} $
$\textrm{FIRST}(C) = \{\epsilon\} $
$\textrm{FIRST}(B) $ 가 포함한 터미널 기호는 $ a, \epsilon$ 이고, $\textrm{FIRST}(S)$ 와 $\textrm{FIRST}(A) $ 가 $\textrm{FIRST}(B) $ 를 포함하고 $ a, \epsilon$ 를 제외한 다른 터미널 기호가 $\textrm{FIRST}$ 집합으로 올 수 있는 경우가 없으므로
$\textrm{FIRST}(S) = \{ a, \epsilon \} $
$\textrm{FIRST}(A) = \{ a, \epsilon \} $
$\textrm{FIRST}(B) = \{ a, \epsilon \} $
$\textrm{FIRST}(C) = \{\epsilon\} $
- FOLLOW
$\textrm{FOLLOW}(S) = \{ \$ \}$
$ S \to ABC $ 생성규칙과 앞서 증명한 $ \epsilon $ transition 으로 인해
$\textrm{FOLLOW}(A) = \{ \textrm{FIRST}(B), \textrm{FIRST}(C), \textrm{FOLLOW}(B), \textrm{FOLLOW}(C), \$ \}$
$\textrm{FOLLOW}(B) = \{ \textrm{FIRST}(C), \textrm{FOLLOW}(C), \$ \}$
$ S \to BCA $ 생성규칙과 앞서 증명한 $ \epsilon $ transition 으로 인해
$\textrm{FOLLOW}(B) = \{ \textrm{FIRST}(C), \textrm{FIRST}(A), \textrm{FOLLOW}(C), \textrm{FOLLOW}(A) \}$
$\textrm{FOLLOW}(C) = \{ \textrm{FIRST}(A), \textrm{FOLLOW}(A) \}$
$ A \to BC $ 생성규칙과 앞서 증명한 $ \epsilon $ transition 으로 인해
$\textrm{FOLLOW}(B) = \{ \textrm{FIRST}(C), \textrm{FOLLOW}(C) \}$
$ B \to SAa $ 생성규칙과 앞서 증명한 $ \epsilon $ transition 으로 인해
$\textrm{FOLLOW}(S) = \{ \textrm{FIRST}(A), \textrm{FOLLOW}(A), a \}$
$\textrm{FOLLOW}(A) = \{ a \}$
$ \textrm{FIRST} $ 집합에 null 문자인 $ \epsilon $ 이 포함된 경우 $\textrm{FOLLOW} $ 집합에선 $을 포함한 다른 터미널 기호와 합쳐진다.
$\textrm{FOLLOW}(S), \textrm{FOLLOW}(A) $ 가 포함한 터미널 기호는 $ a, \$ $ 이고, $\textrm{FOLLOW}(B)$ 와 $\textrm{FOLLOW}(C) $ 가 $\textrm{FIRST}(A), \textrm{FOLLOW}(A) $ 를 포함하고 $ a, \$ $ 를 제외한 다른 터미널 기호가 $\textrm{FOLLOW}$ 집합으로 올 수 있는 경우가 없으므로
$\textrm{FOLLOW}(S) = \{ a, \$ \}$
$\textrm{FOLLOW}(A) = \{ a, \$ \}$
$\textrm{FOLLOW}(B) = \{ a, \$ \}$
$\textrm{FOLLOW}(C) = \{ a, \$ \}$
1-2. 문법 $G_2 = (V_N, V_T, P, S)$ 는 다음과 같이 정의합니다.
$S \rightarrow aBDh$
$B \rightarrow cC $
$C \rightarrow bC \, \mid \, \epsilon $
$D \rightarrow EF $
$E \rightarrow g \, \mid \, \epsilon$
$F \rightarrow f \, \mid \, \epsilon$
- FIRST
$\textrm{FIRST}(S) = \{ a \}$
$\textrm{FIRST}(B) = \{ c \}$
$\textrm{FIRST}(C) = \{ b, \epsilon \}$
$\textrm{FIRST}(D) = \{ \textrm{FIRST}(EF) \}$
$\textrm{FIRST}(E) = \{ g, \epsilon \}$
$\textrm{FIRST}(F) = \{ f, \epsilon \}$
$ EF \to g \mid f \mid gf \mid \epsilon $ 이므로
$\textrm{FIRST}(D) = \{ \textrm{FIRST}(EF) \} = \{ g, f, \epsilon \}$
$\textrm{FIRST}(S) = \{ a \}$
$\textrm{FIRST}(B) = \{ c \}$
$\textrm{FIRST}(C) = \{ b, \epsilon \}$
$\textrm{FIRST}(D) = \{ g, f, \epsilon \}$
$\textrm{FIRST}(E) = \{ g, \epsilon \}$
$\textrm{FIRST}(F) = \{ f, \epsilon \}$
- FOLLOW
$\textrm{FOLLOW}(S) = \{ \$ \}$
$ S \to aBDh $ 생성규칙과 앞서 증명한 $ \epsilon $ transition 으로 인해
$\textrm{FOLLOW}(B) = \{ \textrm{FIRST}(D), \textrm{FOLLOW}(D), h \}$
$\textrm{FOLLOW}(D) = \{ h \}$
$ D \to EF $ 생성규칙과 앞서 증명한 $ \epsilon $ transition 으로 인해
$\textrm{FOLLOW}(E) = \{ \textrm{FIRST}(F), \textrm{FOLLOW}(F) \}$
$ S \to aBDh \to acCDh$ 와 같은 transition이 가능하므로
$\textrm{FOLLOW}(C) = \{ \textrm{FIRST}(D), \textrm{FOLLOW}(D), h \}$
$ S \to aBDh \to aBEFh$ 와 같은 transition이 가능하므로
$\textrm{FOLLOW}(E) = \{ \textrm{FIRST}(F), \textrm{FOLLOW}(F), h \}$
$\textrm{FOLLOW}(F) = \{ h \}$
$\textrm{FOLLOW}(S) = \{ \$ \}$
$\textrm{FOLLOW}(B) = \{ g, f, h \}$
$\textrm{FOLLOW}(C) = \{ g,f,h \}$
$\textrm{FOLLOW}(D) = \{ h \}$
$\textrm{FOLLOW}(E) = \{ f, h \}$
$\textrm{FOLLOW}(F) = \{ h\}$
2. 다음 두 문맥-자유 문법이 $\textrm{LL(1)}$ 문법인지 판단해보고, 이유를 설명하세요.
2-1. 문법 $G_1 = (V_N, V_T, P, S)$ 는 다음과 같이 정의합니다.
$S \rightarrow Ab $
$A \rightarrow a \, \mid \, B \, \mid \, \epsilon $
$B \rightarrow b \, \mid \, \epsilon$
- FIRST
$ \textrm{FIRST}(S) = \{ a, b \} $
$ \textrm{FIRST}(A) = \{ a, b, \epsilon \} $
$ \textrm{FIRST}(B) = \{ b, \epsilon \} $
- FOLLOW
$ \textrm{FOLLOW}(S) = \{ \$ \} $
$ \textrm{FOLLOW}(A) = \{ b \} $
$ \textrm{FOLLOW}(B) = \{ b \} $
$ A \to a \mid B \mid \epsilon $ 생성규칙에서 $ \epsilon \in \textrm{FIRST}(\epsilon) $ 이므로 $ \textrm{FOLLOW}(A) \cap \textrm{FIRST}(B) = \emptyset $ 이 성립해야 $\textrm{LL(1)}$ 문법이다.
하지만 $ \textrm{FOLLOW}(A) \cap \textrm{FIRST}(B) = \{ b \} $ 이므로 해당 문법은 $\textrm{LL(1)}$ 문법이 아니다.
2-2. 문법 $G_2 = (V_N, V_T, P, S)$는 다음과 같이 정의합니다.
$S \rightarrow aSe \, \mid \, B $
$B \rightarrow bBe \, \mid \, C$
$C \rightarrow cCe \, \mid \, d$
- FIRST
$ \textrm{FIRST}(S) = \{ a, b, c, d \} $
$ \textrm{FIRST}(B) = \{b,c,d\} $
$ \textrm{FIRST}(C) = \{c,d\} $
- FOLLOW
$ \textrm{FOLLOW}(S) = \{ e, \$ \} $
$ \textrm{FOLLOW}(B) = \{ e, \$ \} $
$ \textrm{FOLLOW}(C) = \{ e, \$ \} $
$S \rightarrow aSe \, \mid \, B$ 생성규칙에서 $\textrm{FIRST}(aSe) \cap \textrm{FIRST}(B) = \emptyset$ 이 성립해야 $\textrm{LL(1)}$ 문법이다.
$\{a\} \cap \{b,c,d\} = \emptyset$
$B \rightarrow bBe \, \mid \, C$ 생성규칙에서 $\textrm{FIRST}(bBe) \cap \textrm{FIRST}(C) = \emptyset$ 이 성립해야 $\textrm{LL(1)}$ 문법이다.
$\{b\} \cap \{c,d\} = \emptyset$
$C \rightarrow cCe \, \mid \, d$ 생성규칙에서 $\textrm{FIRST}(cCe) \cap \textrm{FIRST}(d) = \emptyset$ 이 성립해야 $\textrm{LL(1)}$ 문법이다.
$\{c\} \cap \{d\} = \emptyset$
따라서, 해당 문법은 $\textrm{LL(1)}$ 문법이다.
3. 다음 문맥-자유 문법에 대해 예측 구문 분석을 수행하세요($\textrm{int}$는 하나의 터미널 심볼로 간주합니다.).
$E \rightarrow T+E\,\mid \,T $
$T \rightarrow \textrm{int}\,\mid \,\textrm{int}*T\, \mid \,(E)$
3-1. 위 문법을 ${\rm LL}(1)$ 문법으로 변환하세요.
-
Hint : 좌인수 분해를 적용해보세요.
$E \rightarrow TE’$
$E’ \rightarrow +E \, \mid \, \epsilon$
$T \rightarrow \textrm{int}T’ \, \mid \, (E)$
$T’ \rightarrow \epsilon \, \mid *T$
3-2. 아래의 예측 파싱표를 구성하세요.
-
FIRST
$\textrm{FIRST}(E) = \{\textrm{int}, (\}$
$\textrm{FIRST}(E’) = \{+, \epsilon\}$
$\textrm{FIRST}(T) = \{\textrm{int}, (\}$
$\textrm{FIRST}(T’) = \{\epsilon, *\}$
-
FOLLOW
$\textrm{FOLLOW}(E) = \textrm{FOLLOW}(E’) = \{\$,)\}$
$\textrm{FOLLOW}(T) = \textrm{FOLLOW}(T’) = \{\$,),+\}$
-
파싱표
int | * | + | ( | ) | $ | |
E | E→TE' | E→TE' | ||||
T | T→intT' | T→(E) | ||||
E' | E'→+E | E'→ε | E'→ε | |||
T' | T'→*T | T'→ε | T'→ε | T'→ε |
3-3. 위의 구성된 파싱표를 이용하여 문자열 $\textrm{int} * \textrm{int}$ 를 파싱하세요.
스택 | 입력기호 | 생성규칙 |
$E | int*int$ | E→TE' |
$E'T | int*int$ | T→intT' |
$E'T'int | int*int$ | |
$E'T' | *int$ | T'→*T' |
$E'T* | *int$ | |
$E'T | int$ | T→intT' |
$E'T'int | int$ | |
$E'T' | $ | T'→ε |
$E' | $ | E'→ε |
$ | $ |