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 함수에 대한 상태 전이도를 그리세요.
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 함수에 대한 상태 전이도를 그리세요.
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 |