컴파일러구성

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

작성자 편입생3학년 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물
아이피 192.♡.55.131
작성일 2021.02.17 00:34

조회 9,009
목록

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점). 단계 스택 입력기호 구문분석 내용

단계	스택	입력기호	구문분석 내용
0	0	id \* id + id $	shift 5
1	0id5	* id + id$	reduce 6
2	0F	* id + id$	goto 3
3	0F3	* id + id$	reduce 4
4	0T	* id + id$	goto 2
5	0T2	* id + id$	shift 7
6	0T2 * 7	id + id$	shift 5
7	0T2 * 7id5	+ id$	reduce 6
8	0T2 * 7F	+ id$	goto 10
9	0T2 * 7F10	+ id$	reduce 3
10	0T	+ id$	goto 2
11	0T2	+ id$	reduce 2
12	0E	+ id$	goto 1
13	0E1	+ id$	shift 6
14	0E1 + 6	id$	shift 5
15	0E1 + 6id5	$	reduce 6
16	0E1 + 6F	$	goto 3
17	0E1 + 6F3	$	reduce 4
18	0E1 + 6T	$	goto 9
19	0E1 + 6T9	$	reduce 1
20	0E	$	goto 1
21	0E1	$	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점). 구문분석 과정

구문분석 과정

단계	스택	입력기호	구문분석 내용
0	0	dccd$	shift 4
1	0d4	ccd$	reduce 3
2	0C	ccd$	goto 2
3	0C2	ccd$	shift 6
4	0C2c6	cd$	shift 6
5	0C2c6c6	d$	shift 7
6	0C2c6c6d7	$	reduce 3
7	0C2c6c6C	$	goto 9
8	0C2c6c6C9	$	reduce 2
9	0C2c6C	$	goto 9
10	0C2c6C9	$	reduce 2
11	0C2C	$	goto 5
12	0C2C5	$	reduce 1
13	0S1	$	accept

형우님 풀이

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