컴파일러구성 - [제8강] 순위관계에 의한 구문분석

컴파일러구성 - [제8강] 순위관계에 의한 구문분석

여러가지 순위분석연산자 순위 구문분석 단순순위 구문분석

컴파일러의 용어정리

연산자 문법 : 연산자 문법은 ε-생성규칙을 갖지 않고, 생성규칙의 오른쪽에 2개 이상의 논터미널이 연속해서 나올 수 없음.

연산자 순위문법 : 연산자 문법이면서 두 개의 터미널 기호 사이에 많아야 한 개의 연산자 순위관계를 갖는 것을 말하고, 이 문법에 의해 정의된 언어를 연산자 순위언어라 함.

단순순위문법 : ε-생성규칙을 갖지 않고, 오른쪽 부분이 같은 생성규칙은 존재하지 않는다. 또한 기호 사이에 많아야 한 개의 Wirth-Weber 순위관계를 가짐.

순위문법의 종류 : 순위문법들에는 연산자 순위문법(operator precedence grammar), 단순 순위문법(simple precedence grammar), 확장 순위문법(extended precedence grammar), 한정 순위문법(weak precedence grammar), 혼합 순위문법(mixed strategy precedence) 등이 있다.

순위관계 : 순위관계는 ⋖, ≗, ⋗의 세 관계로 표기되며, handle은 ⋖ 와 ⋗ 사이에 있게된다.

요점정리

1. handle을 이용한 shift-reduce 구문분석 과정은 handle을 어떻게 찾을 것인가와 찾은 handle에 대해서 생성규칙이 여러 개 존재한다면 어떤 것을 적용할 것인가 하는 문제점을 내포하고 있다. 이와 같이 handle을 어떻게 찾을 것인가에 대한 해결방법으로 순위문법들이 등장하게 된다.
2. handle을 생성규칙의 문법기호 상호간에 순위관계(precedence relation) 에 의해서 찾는 방법들로서 순위 구문분석 방법이 있다. 그리고 이와 같은 방법을 적용하려면 순위문법이 있어야 한다.
3. 순위관계는 ⋖, ≗, ⋗의 세 관계로 표기되며, handle은 ⋖ 와 ⋗ 사이에 있게 된다. 즉, S ‗⇒ αβw가 있을 때 순위관계가 α⋖ β⋗ w이면 β가 handle이 된다. 이와 같은 순위 관계를 이용하여 파싱표를 구성할 수 있다.
4. 순위문법들(precedence grammars)에는 연산자 순위문법(operator precedence grammar), 단순 순위문법(simple precedence grammar), 확장 순위문법(extended precedence grammar), 한정 순위문법(weak precedence grammar), 혼합 순위문법(mixed strategy precedence) 등이 있다.
5. 순위문법에 의한 구문분석은 한계가 있다. 결국은 LR 구문분석으로 해결하게 된다.
6.  

연습문제

• 

  ε-생성규칙을 갖지 않고, 생성규칙의 오른쪽에 2개 이상의 논터미널이 연속해서 나올 수 없는 문법은?

  답을 체크하세요

  1. 연산자 문법
  2. 단순 순위 문법
  3. 확장 순위 문법
  4. 연산자 순위 문법

  정답 :

  ①

  연산자 문법에 대한 설명이다. 

• 

  다음 중 단순 순위문법과 관계없는 것은?

  답을 체크하세요

  1. ε-생성규칙을 갖지 않는다.
  2. 오른쪽 부분이 같은 생성규칙은 존재하지 않는다.
  3. 두 개의 기호 사이에 많아야 한 개의 순위 관계를 갖는다.
  4. 두 문자열 사이에 많아야 한 개의 순위관계를 갖는다.

  정답 :

  ④

  두 문자열 사이에 많아야 한 개의 순위관계를 갖는다.=> 확장순위문법에 대한 설명이다. 

• 

  다음은 단순순위문법을 이용해서 기호들 사이의 순위관계를 정하는 과정이다. 빈칸 ‘가’에 알맞은 것은?
  

  Ｆ→（Ｅ） （（ ≐ Ｅ，Ｅ ≐ ））
    →（Ｅ_１）（ （ ⋖ Ｅ_１，Ｅ_１ ⋗ ））
    →（Ｔ_１）（ （ ⋖ Ｔ_１，Ｔ_１ ⋗ ））
    →（Ｔ） （    ‘가’    ）
    →（Ｆ） （ ( ⋖ F, F ⋗ ) )

  답을 체크하세요

  1. ( ⋖ Ｔ
  2. ( ⋖ Ｔ, Ｔ ⋗ )
  3. T ⋖ (
  4. T ⋖ (， ) ⋗ T

  정답 :

  ②

  Ｆ→（Ｅ） （∴ （ ≐ Ｅ，Ｅ ≐ ））    →（Ｅ_１）（∴ （ ⋖ Ｅ_１，Ｅ_１ ⋗ ））
     →（Ｔ_１）（∴ （ ⋖ Ｔ_１，Ｔ_１ ⋗ ））
  여기서 문법의 4번 규칙 Ｔ_１→ Ｔ 을 적용하면
    →（Ｔ_１）→ （Ｔ） 이 된다.
  따라서 （ ⋖ Ｔ，Ｔ ⋗ ）의 관계가 성립한다. 

• 

  다음은 단순순위문법을 이용해서 기호들 사이의 순위관계를 정하는 과정이다. 빈칸 ‘가’에 알맞은 것을 고르시오.
  

              E → E1 → T1 → T → T*F
                      → T * id     ‘가’    
                      → F * id F ·〉 *
                      → id * id id ·〉 *

  답을 체크하세요

  1. T 〈· *
  2. * 〈· id
  3. T ·〉 *
  4. E → E＋Eid ·〉 *

  정답 :

  ②

  T * F
     → T * id 이므로
     * 〈· id 이다. 

• 

  다음은 SLR 파싱표를 이용하여 이용하여 문장 id+id*id을 구문분석하는 과정이다. 물음에 답하라
  빈칸 (   가   )의 내용은 ?
  

  연습문제 설명

  < 파 싱 표 >
  

  상태	구문분석기의 행동						GOTO 함수
  	id	+	*	(	)	$	E	T	F
  0	S5			S4			1	2	3
  1		S6				acc
  2		r2	S7		r2	r2
  3		r4	r4		r4	r4
  4	S5			S4			8	2	3
  5		r6	r6		r6	r6
  6	S5			S4				9	3
  7	S5			S4					10
  8		S6			S11
  9		r1	S7		r1	r1
  10		r3	r3		r3	r3
  11		r5	r5		r5	r5

  
  
  

  단계	스택	입력기호	구문분석 내용
  	0
  0		id+id*id$	shift 5
  	⋮
  ⋮	⋮	⋮	⋮
  ⋮		⋮	⋮
  15	0E1＋6T9＊7id5	$	reduce 6
  16	0E1＋6T9＊7F	$	goto 10
  17	0E1＋6T9＊7F10	$	(   가   )
  18	0E1＋6T	$	(   나   )
  19	0E1＋6T9	$	(   다   )
  20	0E	$	(   라   )
  21	0E1	$	accept

  답을 체크하세요

  1. reduce 3
  2. reduce 5
  3. goto 3
  4. shift 3

  정답 :

  ①

  파싱표에서 상태=10 입력기호=$ 를 찾아보면 reduce3 

• 

  다음은 SLR 파싱표를 이용하여 이용하여 문장 id+id*id을 구문분석하는 과정이다. 물음에 답하라
  빈칸 (   나   )의 내용은 ?
  

  연습문제 설명

  < 파 싱 표 >
  

  상태	구문분석기의 행동						GOTO 함수
  	id	+	*	(	)	$	E	T	F
  0	S5			S4			1	2	3
  1		S6				acc
  2		r2	S7		r2	r2
  3		r4	r4		r4	r4
  4	S5			S4			8	2	3
  5		r6	r6		r6	r6
  6	S5			S4				9	3
  7	S5			S4					10
  8		S6			S11
  9		r1	S7		r1	r1
  10		r3	r3		r3	r3
  11		r5	r5		r5	r5

  
  
  

  단계	스택	입력기호	구문분석 내용
  	0
  0		id+id*id$	shift 5
  	⋮
  ⋮	⋮	⋮	⋮
  ⋮		⋮	⋮
  15	0E1＋6T9＊7id5	$	reduce 6
  16	0E1＋6T9＊7F	$	goto 10
  17	0E1＋6T9＊7F10	$	(   가   )
  18	0E1＋6T	$	(   나   )
  19	0E1＋6T9	$	(   다   )
  20	0E	$	(   라   )
  21	0E1	$	accept

  답을 체크하세요

  1. shift 6
  2. reduce 6
  3. goto 9
  4. shift 9

  정답 :

  ③

  파싱표에서 상태=6 입력기호=T 를 찾아보면 goto 9 

• 

  다음은 SLR 파싱표를 이용하여 이용하여 문장 id+id*id을 구문분석하는 과정이다. 물음에 답하라
  빈칸 (   다   )의 내용은 ?
  

  연습문제 설명

  < 파 싱 표 >
  

  상태	구문분석기의 행동						GOTO 함수
  	id	+	*	(	)	$	E	T	F
  0	S5			S4			1	2	3
  1		S6				acc
  2		r2	S7		r2	r2
  3		r4	r4		r4	r4
  4	S5			S4			8	2	3
  5		r6	r6		r6	r6
  6	S5			S4				9	3
  7	S5			S4					10
  8		S6			S11
  9		r1	S7		r1	r1
  10		r3	r3		r3	r3
  11		r5	r5		r5	r5

  
  
  

  단계	스택	입력기호	구문분석 내용
  	0
  0		id+id*id$	shift 5
  	⋮
  ⋮	⋮	⋮	⋮
  ⋮		⋮	⋮
  15	0E1＋6T9＊7id5	$	reduce 6
  16	0E1＋6T9＊7F	$	goto 10
  17	0E1＋6T9＊7F10	$	(   가   )
  18	0E1＋6T	$	(   나   )
  19	0E1＋6T9	$	(   다   )
  20	0E	$	(   라   )
  21	0E1	$	accept

  답을 체크하세요

  1. goto 1
  2. reduce 1
  3. goto 10
  4. shift 9

  정답 :

  ②

  파싱표에서 상태=9 입력기호=$ 를 찾아보면 reduce1 

• 

  다음은 SLR 파싱표를 이용하여 이용하여 문장 id+id*id을 구문분석하는 과정이다. 물음에 답하라
  빈칸 (   라   )의 내용은 ?
  

  연습문제 설명

  < 파 싱 표 >
  

  상태	구문분석기의 행동						GOTO 함수
  	id	+	*	(	)	$	E	T	F
  0	S5			S4			1	2	3
  1		S6				acc
  2		r2	S7		r2	r2
  3		r4	r4		r4	r4
  4	S5			S4			8	2	3
  5		r6	r6		r6	r6
  6	S5			S4				9	3
  7	S5			S4					10
  8		S6			S11
  9		r1	S7		r1	r1
  10		r3	r3		r3	r3
  11		r5	r5		r5	r5

  
  
  

  단계	스택	입력기호	구문분석 내용
  	0
  0		id+id*id$	shift 5
  	⋮
  ⋮	⋮	⋮	⋮
  ⋮		⋮	⋮
  15	0E1＋6T9＊7id5	$	reduce 6
  16	0E1＋6T9＊7F	$	goto 10
  17	0E1＋6T9＊7F10	$	(   가   )
  18	0E1＋6T	$	(   나   )
  19	0E1＋6T9	$	(   다   )
  20	0E	$	(   라   )
  21	0E1	$	accept

  답을 체크하세요

  1. goto 0
  2. reduce 1
  3. goto 1
  4. shift 1

  정답 :

  ③

  파싱표에서 상태=0 입력기호=E 를 찾아보면 goto 1