분류 컴파일러구성

[과제]컴파일러 기말 과제물

컨텐츠 정보

본문

1. 교재 202쪽 (예5-16)의 문법에 대하여 (1) 문장 id*id+id 를 우단유도 하라(10점). 문법


1) E → E + T
2) E → T
3) T → T * F
4) T → F
5) F → (E)
6) F → id
우단 유도

  E
→ E + T
→ E + F
→ E + id
→ T + id
→ T * F + id
→ T * id + id
→ F * id +id
→ id * id + id
(2) (예5-17)을 참고하여 id*id+id 의 구문분석 과정을 표로 작성하라(15점). 단계 스택 입력기호 구문분석 내용 

단계스택입력기호구문분석 내용
00id \* id + id $shift 5
10id5* id + id$reduce 6
20F* id + id$goto 3
30F3* id + id$reduce 4
40T* id + id$goto 2
50T2* id + id$shift 7
60T2 * 7id + id$shift 5
70T2 * 7id5+ id$reduce 6
80T2 * 7F+ id$goto 10
90T2 * 7F10+ id$reduce 3
100T+ id$goto 2
110T2+ id$reduce 2
120E+ id$goto 1
130E1+ id$shift 6
140E1 + 6id$shift 5
150E1 + 6id5$reduce 6
160E1 + 6F$goto 3
170E1 + 6F3$reduce 4
180E1 + 6T$goto 9
190E1 + 6T9$reduce 1
200E$goto 1
210E1$accept
 2. 교재 218쪽 (예5-20)의 문법에 대하여 (1) 문장 dccd 를 우단유도 하라(10점). 문법

1) S → CC
2) C → cC
3) C → d
우단유도

S
→ CC
→ CcC
→ CccC
→ Cccd
→ dccd
(2) (예5-20)에서 구문분석 예제를 참고하여 dccd 의 구문분석 과정을 표로 작성하라(15점). 구문분석 과정 

구문분석 과정

단계스택입력기호구문분석 내용
00dccd$shift 4
10d4ccd$reduce 3
20Cccd$goto 2
30C2ccd$shift 6
40C2c6cd$shift 6
50C2c6c6d$shift 7
60C2c6c6d7$reduce 3
70C2c6c6C$goto 9
80C2c6c6C9$reduce 2
90C2c6C$goto 9
100C2c6C9$reduce 2
110C2C$goto 5
120C2C5$reduce 1
130S1$accept

 형우님 풀이


26e15f1098933743b98578d4e5ecda0f_1613489931_1423.png
26e15f1098933743b98578d4e5ecda0f_1613489931_1594.png

 


canonical collection


I0 = closure([S’ → ‧S, $]) = {[S’ → ‧S, $], [S → ‧CC, $], [C → ‧cC, c/d], [C → ‧d, c/d]}
GOTO(I0, S) = I1 = closure([S’ → S‧, $]) = {[S’ → S‧, $]}
GOTO(I0, C) = I2 = closure([S → C‧C, $]) = {[S → C‧C, $], [C → ‧cC, $], [C → ‧d, $]}
GOTO(I0, c) = I3 = closure([C → c‧C, c/d]) = {[C → c‧C, c/d], [C → ‧cC, c/d], [C → ‧d, c/d]}
GOTO(I0, d) = I4 = closure([C → d‧, c/d]) = {[C → d‧, c/d]}
GOTO(I2, C) = I5 = closure([S → CC‧, $]) = {[S → CC‧, $]}
GOTO(I2, c) = I6 = closure([C → c‧C, $]) = {[C → c‧C, $], [C → ‧cC, $], [C → ‧d, $]}
GOTO(I2, d) = I7 = closure([C → d‧, $]) = {[C → d‧, $]}
GOTO(I3, C) = I8 = closure([C → cC‧, c/d]) = {[C → cC‧, c/d]}
GOTO(I3, c) = I3
GOTO(I3, d) = I4
GOTO(I6, C) = I9 = closure([C → cC‧, $]) = {[C → cC‧, $]}
GOTO(I6, c) = I6
GOTO(I6, d) = I7
3.다음은 교재 202쪽 (예5-16)의 문법에서 5) F → (E) 규칙을 삭제한 문법이다. LR(0) 항목 집합의 canonical collection을 구하라(20점).

canonical collection
I0 = closure([S’ → ‧E]) = {[S’ → ‧E], [E → ‧E+T], [E → ‧T], [T → ‧T*F], [T → ‧F], [F → ‧id]}
GOTO(I0, E) = I1 = closure([S’ → E‧], [E → E‧+T]) = {[S’ → E‧], [E → E‧+T]}
GOTO(I0, T) = I2 = closure([E → T‧], [T → T‧*F]) = {[E → T‧], [T → T‧*F]}
GOTO(I0, F) = I3 = closure([T → F‧]) = {[T → F‧]}
GOTO(I0, id) = I4 = closure([F → id‧]) = {[F → id‧]}
GOTO(I1, +) = I5 = closure([E → E+‧T]) = {[E → E+‧T], [T → ‧T*F], [T → ‧F], [F → ‧id]}
GOTO(I2, *) = I6 = closure([T → T*‧F]) = {[T → T*‧F], [F → ‧id]}
GOTO(I5, T) = I7 = closure([E → E+T‧], [T → T‧*F]) = {[E → E+T‧], [T → T‧*F]}
GOTO(I5, F) = I3
GOTO(I5, id) = I4
GOTO(I6, F) = I8 = closure([T → T*F‧]) = {[T → T*F‧]}
GOTO(I6, id) = I4
GOTO(I7, *) = I6

관련자료

  • 서명
    방송통신대학교 컴퓨터 과학과 단톡 https://open.kakao.com/o/gSLabj6 온라인으로 유학하는 사람들 https://ongongsa.com
댓글 0
등록된 댓글이 없습니다.
Total 19 / 1 Page
번호
제목
이름

방송통신대학교 컴퓨터 과학과 단톡

https://open.kakao.com/o/gSLabj6

최근글


새댓글


  • 댓글이 없습니다.
알림 0