Compiler Design 5th Homework Solution

       

1. 다음과 같은 생성 규칙을 갖는 문법이 있습니다. 이 때, $\#, \$, @$ 기호는 이항 연산자를 의미하며 연산자 우선 순위는 $@ > \# > \$$라고 가정합시다.

1-1. 연산자 우선순위를 고려하여 식 $a\;\$\;a\;@\;a\;\#\;a\;\$\;a$에 대한 파스 트리를 그리세요.

  • 오른쪽 결합

image

  • 왼쪽 결합

image2

1-2. 주어진 연산자들이 오른쪽 결합법칙을 따른다고 가정할 때, 연산자 우선순위와 오른쪽 결합법칙에 맞게 주어진 문법을 모호하지 않은 문법으로 변환하세요.

$ S \rightarrow E \, \$ \, S \, \mid \, E $

$ E \rightarrow F \, \# \, E \, \mid \, F $

$ F \rightarrow T \, @ \, F \, \mid \, T $

$ T \rightarrow a $

   

2. 다음 문법에서 불필요한 생성 규칙을 제거하세요.
  • 논터미널 기호 $B$는 터미널 문자열을 만들지 못한다.
  • 논터미널 기호 $C$는 시작 기호로부터 도달할 수 없다.

$ S \rightarrow A $

$ A \rightarrow aA \, \mid \, bS \, \mid \, b $

   

3. 다음 문법을 $\epsilon$-자유 문법으로 변환하세요.
  • $ A \overset{* }{\Rightarrow} \epsilon , \, C \overset{* }{\Rightarrow} \epsilon $ 논터미널 기호 $ A,C $ 는 $\epsilon$-생성 규칙을 가지고 있어 제거해야 한다.

$S \rightarrow a \, \mid \, aA \, \mid \, aBB $

$A \rightarrow aaA \, \mid \, aa $

$B \rightarrow bB \, \mid \, bbC \, \mid \, bb $

$C \rightarrow B $

   

4. 다음 문법을 proper한 문법으로 변환하세요.

1단계. $\epsilon$-생성 규칙 제거

$C \overset{* }{\Rightarrow} \epsilon, \, E \overset{* }{\Rightarrow} \epsilon $

또한 주어진 문법을 통해 $A \Rightarrow C \overset{* }{\Rightarrow} \epsilon, \, B \Rightarrow E \overset{* }{\Rightarrow} \epsilon, \, S \Rightarrow A \overset{* }{\Rightarrow} \epsilon, \, D \Rightarrow S \Rightarrow A \overset{* }{\Rightarrow} \epsilon $ 임을 알 수 있다.

따라서 새로운 시작기호 $S’$ 를 가지고 $\epsilon$-생성 규칙을 제거할 수 있다.

$S’ \rightarrow S \, \mid \epsilon$

$S \rightarrow A \, \mid B$

$A \rightarrow C \, \mid D$

$B \rightarrow D \, \mid E$

$C \rightarrow S \, \mid a$

$D \rightarrow S \, \mid b$

$E \rightarrow S \, \mid C$

 

2단계. 단일 생성 규칙 제거

  1. $S’ \Rightarrow S \Rightarrow A \Rightarrow C, \, S’ \Rightarrow S \Rightarrow B \Rightarrow D $ 이므로 $S’ \Rightarrow a \, \mid \, b \, \mid \, \epsilon$ 이 된다.

  2. $S \Rightarrow A \Rightarrow C, \, S \Rightarrow B \Rightarrow D$ 이므로

$S’ \Rightarrow S \, \mid \, \epsilon$

$S \Rightarrow a \, \mid \, b$

나머지 논터미널 기호는 불필요한 기호가 되어 제거된다. (1,2번 모두 정답)

5. 다음 문법에서 좌재귀를 제거한 후, 좌인수분해를 수행하세요.

1단계. 직접 좌재귀 제거

$S \rightarrow AaS’$

$S’ \rightarrow baS’ \, \mid \, \epsilon$

$A \rightarrow Bb$

$B \rightarrow Cc$

$C \rightarrow Dd \, \mid \, e$

$D \rightarrow Ab$

 

2단계. 간접 좌재귀 제거

문법의 전체 논터미널 기호의 순서를 $S, S’, A, B, C, D$ 로 정렬한다.

$S’$ 보다 작은 $S$ 에 대하여 $S’ \rightarrow S\gamma $ 꼴의 생성 규칙이 있는지 확인한다 : 없음.

$A$ 보다 작은 $S, S’$ 에 대하여 $A\rightarrow S\gamma, \, A\rightarrow S’\gamma$ 꼴의 생성 규칙이 있는지 확인한다 : 없음.

$B$ 보다 작은 $S, S’, A$ 에 대하여 $B \rightarrow S\gamma, B \rightarrow S’\gamma, B \rightarrow A\gamma $ 꼴의 생성 규칙이 있는지 확인한다 : 없음.

$C$ 보다 작은 $S, S’, A, B$ 에 대하여 $C \rightarrow S\gamma, C \rightarrow S’\gamma, C \rightarrow A\gamma, C \rightarrow B\gamma$ 꼴의 생성 규칙이 있는지 확인한다 : 없음.

$D$ 보다 작은 $S,S’,A,B,C$ 에 대하여 $D \rightarrow S\gamma, D \rightarrow S’\gamma, D \rightarrow A\gamma, D \rightarrow B\gamma, D \rightarrow C\gamma,$ 꼴의 생성 규칙이 있는지 확인한다.

  • $D \rightarrow A\gamma$ 꼴의 생성 규칙을 제거한다.

$S \rightarrow AaS’$

$S’ \rightarrow baS’ \, \mid \, \epsilon$

$A \rightarrow Bb$

$B \rightarrow Cc$

$C \rightarrow Dd \, \mid \, e$

$D \rightarrow Bbb$

  • $D \rightarrow B\gamma$ 꼴의 생성 규칙을 제거한다.

$S \rightarrow AaS’$

$S’ \rightarrow baS’ \, \mid \, \epsilon$

$A \rightarrow Bb$

$B \rightarrow Cc$

$C \rightarrow Dd \, \mid \, e$

$D \rightarrow Ccbb$

  • $D \rightarrow C\gamma$ 꼴의 생성 규칙을 제거한다.

$S \rightarrow AaS’$

$S’ \rightarrow baS’ \, \mid \, \epsilon$

$A \rightarrow Bb$

$B \rightarrow Cc$

$C \rightarrow Dd \, \mid \, e$

$D \rightarrow Ddcbb \, \mid \, ecbb$

 

3단계. 직접 좌재귀 제거

$S \rightarrow AaS’$

$S’ \rightarrow baS’ \, \mid \, \epsilon$

$A \rightarrow Bb$

$B \rightarrow Cc$

$C \rightarrow Dd \, \mid \, e$

$D \rightarrow ecbbD’ $

$D’ \rightarrow dcbbD’ \, \mid \, \epsilon $