Compiler Design 7th Homework Solution

       

1. 다음 두 문맥-자유 문법이 각각 ${\rm LL}(1)$ 문법인지 그리고 $\textrm{SLR}(1)$ 문법인지 판단해보고, 그 이유를 설명하세요.

1-1. 문법 $G_1=(V_N,V_T,P,S)$는 다음과 같이 정의합니다.

$ S \to AaAb \mid BbBa$

$ A \to \epsilon$

$ B \to \epsilon$

   

$\textrm{FIRST(S)}=\{ a, b\}$

$\textrm{FIRST(A)}=\{\epsilon\}$

$\textrm{FIRST(B)}=\{\epsilon\}$

$\textrm{FOLLOW(S)}=\{\$\}$

$\textrm{FOLLOW(A)}=\{ a,b \}$

$\textrm{FOLLOW(B)}=\{ a,b \}$

$\textrm{FIRST(AaAb)} \cap \textrm{FIRST(BbBa)}=\{ a \} \cap \{ b\} = \emptyset$ 이므로 해당 문법은 $\textrm{LL(1)}$ 문법이다.

$\textrm{CLOSURE}(I)=I_0 = \{ [S’ \to \bullet \ S], [S\to \bullet AaAb], [A\to\bullet\epsilon],[B\to\bullet\epsilon] \}$

$\textrm{GOTO}(I_0,S)=I_1=\textrm{CLOSURE}(\{ [S’\to S\bullet ] \})=\{ [S’\to S\bullet ] \}$

$ \textrm{GOTO}(I_0,A)=I_2=\textrm{CLOSURE}(\{ [S\to A\bullet aAb] \})=\{ [S\to A\bullet aAb] \}$

$\textrm{GOTO}(I_0,B)=I_3=\textrm{CLOSURE}(\{ [B \to B\bullet bBa ] \})=\{ [B \to B\bullet bBa ] \}$

$\textrm{GOTO}(I_0,\epsilon)=I_4=\textrm{CLOSURE}(\{ [A\to \epsilon\bullet ],[B\to \epsilon\bullet ] \})= \{ [A\to \epsilon\bullet ],[B\to \epsilon\bullet ] \}$

$…$

이때, $I_4$에 포함된 감축조건은 $[A\to \epsilon\bullet ],[B\to \epsilon\bullet]$ 으로, $\textrm{FOLLOW(A)}$ 와 $\textrm{FOLLOW(B)}$ 에 중복된 원소가 있음을 고려하면 파싱표를 구성할 때 특정 터미널 문자를 읽는 경우 적용해야 할 감축조건을 확정적으로 결정하지 못할 것임을 알 수 있다. 따라서 해당 문법은 $\textrm{SLR(1)}$ 문법이 아니다.

   

1-2. 문법 $G_2=(V_n,V_t,P,S)$는 다음과 같이 정의합니다.

$S \to SA \mid A$

$A \to a$

   

$\textrm{FIRST(S)}=\{ a\}$

$\textrm{FIRST(A)}=\{a\} $

$\textrm{FOLLOW(S)}=\{\$, a\}$

$\textrm{FOLLOW(A)}=\{ \$, a \} $

$\textrm{FIRST(SA)} \cap \textrm{FIRST(A)}=\{ a \} \cap \{ a\} \neq \emptyset$ 이므로 해당 문법은 $\textrm{LL(1)}$ 문법이 아니다.

$\textrm{CLOSURE}(I)=I_0 = \{ [S’ \to \bullet \ S], [S\to \bullet SA], [S\to\bullet A],[A\to\bullet a] \}$

$\textrm{GOTO}(I_0,S)=I_1=\textrm{CLOSURE}(\{ [S’\to S\bullet ],[S\to S\bullet A] \})=\{ [S’\to S\bullet ],[S\to S\bullet A], [A\to \bullet a] \}$

$\textrm{GOTO}(I_0,A)=I_2=\textrm{CLOSURE}(\{[S\to A\bullet] \})=\{ [S\to A\bullet] \}$

$\textrm{GOTO}(I_0,a)=I_3=\textrm{CLOSURE}(\{[A \to a\bullet ] \})=\{ [A \to a\bullet ] \}$

$\textrm{GOTO}(I_1,A)=I_4=\textrm{CLOSURE}(\{ [S\to SA\bullet ]\})=\{ [S\to SA\bullet ] \}$

$\textrm{GOTO}(I_1,a)=I_3=\textrm{CLOSURE}(\{[A\to a\bullet ] \})=\{ [A\to a\bullet ] \}$

파싱표 구성

구문분석기 행동 GOTO
상태 a $ S A
0 s3 1 2
1 s3 acc 4
2 r2 r2
3 r3 r3
4 r1 r1

파싱표의 모든 상태에서 결정하는 모든 행동이 확정적으로 이루어지므로 해당 문법은 $\textrm{SLR(1)}$ 문법이다.

   

2. 다음 문맥-자유 문법에 대한 아래의 질문에 답하세요.
\[S \rightarrow SS+\, | \, SS* \, | \, a\]

   

2-1. 위 문법에 대해 $\textrm{LR}(0)$ 항목 집합에 대한 정규 모임을 계산하세요.

$I = \{[S’ \rightarrow \bullet S]\}$

$\textrm{CLOSURE}(I) = I_0 = \{[S’ \rightarrow \bullet S], [S \rightarrow \bullet SS+], [S \rightarrow \bullet SS*], [S \rightarrow \bullet a]\}$

$\textrm{GOTO}(I_0, S) = I_1 = \textrm{CLOSURE}(\{[S’ \rightarrow S \bullet], [S \rightarrow S \bullet S+], [S \rightarrow S \bullet S *]\}) = \{[S’ \rightarrow S \bullet], [S \rightarrow S \bullet S+], [S \rightarrow S \bullet S *], [S \rightarrow \bullet SS+], [S \rightarrow \bullet SS *], [S \rightarrow \bullet a]\}$

$\textrm{GOTO}(I_0,a) = I_2 = \textrm{CLOSURE}[\{[S \rightarrow a \bullet]\}] = \{[S \rightarrow a \bullet]\}$

$\textrm{GOTO}(I_1, S) = I_3 = \textrm{CLOSURE}(\{[S \rightarrow SS \bullet +], [S \rightarrow SS \bullet * ], [S \rightarrow S \bullet S+], [S \rightarrow S \bullet S * ] \}) = \{[S \rightarrow SS \bullet +], [S \rightarrow SS \bullet * ], [S \rightarrow S \bullet S+], [S \rightarrow S \bullet S * ], [S \rightarrow \bullet SS+], [S \rightarrow \bullet SS*], [S \rightarrow \bullet a] \} $

$\textrm{GOTO}(I_1,a) = \textrm{CLOSURE}(\{[S \rightarrow a \bullet]\}) = \{[S \rightarrow a \bullet]\} = I_2 $

$\textrm{GOTO}(I_3,S) = \textrm{CLOSURE}(\{[S \rightarrow SS \bullet +], [S \rightarrow SS \bullet * ], [S \rightarrow S \bullet S+], [S \rightarrow S \bullet S * ] \}) = \{[S \rightarrow SS \bullet +], [S \rightarrow SS \bullet * ], [S \rightarrow S \bullet S+], [S \rightarrow S \bullet S * ], [S \rightarrow \bullet SS+], [S \rightarrow \bullet SS*], [S \rightarrow \bullet a] \} = I_3 $

$\textrm{GOTO}(I_3,+) = I_4 = \textrm{CLOSURE}(\{[S \rightarrow SS+ \bullet]\}) = \{[S \rightarrow SS+ \bullet]\} $

$\textrm{GOTO}(I_3, * ) = I_5 = \textrm{CLOSURE}(\{[S \rightarrow SS* \bullet]\}) = \{[S \rightarrow SS * \bullet]\} $

$\textrm{GOTO}(I_3,a) = \textrm{CLOSURE}(\{[S \rightarrow a \bullet]\}) = \{[S \rightarrow a \bullet]\} = I_2 $

   

2-2. 위에서 계산된 GOTO 함수에 대한 상태 전이도를 그리세요.

title

2-3. 위 문법에 대한 SLR 파싱표를 구성하세요

$\textrm{FOLLOW}(S) = \{\$, +, *, a\}$

구문분석기 행동 GOTO
상태 a + * $ S
0 s2 1
1 s2 acc 3
2 r3 r3 r3 r3
3 s2 s4 s5 3
4 r1 r1 r1 r1
5 r2 r2 r2 r2

   

2-4. 구성된 SLR 파싱표를 이용하여 입력 문자열 $aa*a+$의 구문 분석을 수행하고 그 행동을 순서대로 적으세요.

단계 스택 기호 입력기호 생성규칙
1 0 aa*a+$ 이동 2(s2)
2 0 2 a a*a+$ 감축 S➝a (r3)
3 0 1 S a*a+$ 이동 2(s2)
4 0 1 2 Sa *a+$ 감축 S➝a (r3)
5 0 1 3 SS *a+$ 이동 5(s5)
6 0 1 3 5 SS* a+$ 감축 S➝SS*(r2)
7 0 1 S a+$ 이동 2(s2)
8 0 1 2 Sa +$ 감축 S➝a (r3)
9 0 1 3 SS +$ 이동 4(s4)
10 0 1 3 4 SS+ $ 감축 S➝SS+ (r1)
11 0 1 S $ acc

       

3. 다음 문맥-자유 문법에 대한 아래의 질문에 답하세요.

$S’ \to S$

$S \to CC$

$C \to cC \mid d$

   

3-1. 위 문법에 대해 $\textrm{LR}(1)$ 항목 집합의 정규 모임을 계산하세요.

$\textrm{CLOSURE}(I)=I_0= \{ [S’\to\bullet S, \$],[S\to\bullet CC, \$],[C\to\bullet cC,c/d],[C\to\bullet d,c/d] \}$

$\textrm{GOTO}(I_0, S)=I_1=\textrm{CLOSURE}(\{ [S’\to S\bullet,\$]\}) = \{[S’\to S\bullet,\$]\}$

$\textrm{GOTO}(I_0, C)=I_2=\textrm{CLOSURE}(\{ [S\to C\bullet C,\$]\}) = \{[S\to C\bullet C,\$],[C\to \bullet cC,\$],[C\to \bullet d,\$]\}$

$\textrm{GOTO}(I_0, c)=I_3=\textrm{CLOSURE}(\{ [C\to c\bullet C,c/d]\}) = \{[S\to c\bullet C,c/d],[C\to \bullet cC,c/d],[C\to \bullet d,c/d]\}$

$\textrm{GOTO}(I_0, d)=I_4=\textrm{CLOSURE}(\{ [C\to d\bullet,c/d]\}) = \{[C\to d\bullet,c/d]\}$

$\textrm{GOTO}(I_2, C)=I_5=\textrm{CLOSURE}(\{ [S\to CC\bullet,\$]\}) = \{[S\to CC\bullet,\$]\}$

$\textrm{GOTO}(I_2, c)=I_6=\textrm{CLOSURE}(\{ [C\to c\bullet C,\$]\}) = \{[C\to c\bullet C,\$],[C\to \bullet cC,\$],[C\to \bullet d,\$]\}$

$\textrm{GOTO}(I_2, d)=I_7=\textrm{CLOSURE}(\{ [C\to d\bullet,\$]\}) = \{[C\to d\bullet,\$]\}$

$\textrm{GOTO}(I_3, C)=I_8=\textrm{CLOSURE}(\{ [C\to cC\bullet,c/d]\}) = \{[C\to cC\bullet,c/d]\}$

$\textrm{GOTO}(I_3, c)=\textrm{CLOSURE}(\{ [C\to c\bullet C,c/d]\}) = \{[S\to c\bullet C,c/d],[C\to \bullet cC,c/d],[C\to \bullet d,c/d]\}=I_3$

$\textrm{GOTO}(I_3, d)=\textrm{CLOSURE}(\{ [C\to d\bullet,c/d]\}) = \{[C\to d\bullet,c/d]\}=I_4$

$\textrm{GOTO}(I_6, C)=I_9=\textrm{CLOSURE}(\{ [C\to cC\bullet,\$]\}) = \{[C\to cC\bullet,\$]\}$

$\textrm{GOTO}(I_6, c)=\textrm{CLOSURE}(\{ [C\to c\bullet C,\$]\}) = \{[S\to c\bullet C,\$],[C\to \bullet cC,\$],[C\to \bullet d,\$]\}=I_6$

$\textrm{GOTO}(I_6, d)=\textrm{CLOSURE}(\{ [C\to d\bullet,\$]\}) = \{[C\to d\bullet,\$]\}=I_7$

   

3-2. 위에서 계산된 GOTO 함수에 대한 상태 전이도를 그리세요.

I₀ I₁ I₂ I₅ I₃ I₄ I₈ I₆ I₇ I₉ S C C c d d C c c d c C d

   

3-3. 위 문법에 대한 CLR 파싱표를 구성하세요.

구문분석기 행동 GOTO
상태 c d $ S C
0 s3 s4 1 2
1 acc
2 s6 s7 5
3 s3 s4 8
4 r3 r3
5 r1
6 s6 s7 9
7 r3
8 r2 r2
9 r2

   

3-4. 구성된 CLR 파싱표를 이용하여 입력 문자열 $cdcd$의 구문 분석을 수행하고 그 행동을 순서대로 적으세요.

단계 스택 기호 입력기호 생성규칙
1 0 cdcd$ 이동 3(s3)
2 0 3 c dcd$ 이동 4(s4)
3 0 3 4 cd cd$ 감축 C➝d (r3)
4 0 3 8 cC cd$ 감축 C➝cC (r2)
5 0 2 C cd$ 이동 6(s6)
6 0 2 6 Cc d$ 이동 7(s7)
7 0 2 6 7 Ccd $ 감축 C➝d (r3)
8 0 2 6 9 CcC $ 감축 C➝cC (r2)
9 0 2 5 CC $ 감축 S➝CC (r1)
10 0 1 S $ acc