Compiler Design 6th Homework Solution

       

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'→ε
$ $