컴파일러구성 - [제9강] LR 구문분석

컴파일러구성 - [제9강] LR 구문분석

증가문법 ·closure와 GOTO 함수 ·SLR 파싱표 와 구문분석

컴파일러 용어정리

• LR(k) 문법
  모든 엔트리(entry)에 대해, 유일하게 정의되는 파싱표를 만들 수 있는 문법을 말한다. 여기서 k를 lookahead의 길이라고 하며, 이는 handle을 결정하는 데 k개의 입력기호에 이르기까지 조사하는 것
• LR(0) 항목
  생성규칙의 오른쪽에 점기호(dot symbol)를 가진 생성규칙
• 증가문법
  G=(V_N,V_T,P,S)에서 G에 첨가된 문법
  즉, 시작기호 {S'→S} 를 하나 더 추가한 문법이다..
• Closure
  마크기호가 [A→ α․Bβ]와 같이 논터미널인 경우에 이 논터미널 B를 생성규칙의 왼쪽으로 갖는 LR(0) 항목을 구하는 것을 closure라고 한다. 이 closure는 반복적으로 계속 적용된다.
• GOTO 함수
  GOTO(I, X) ＝ closure({[A → αX․β]| [A → α․Xβ∈I})
  즉, 현재 마킹한 상태에서 구문분석을 하기 위해, 마크기호를 하나씩 읽는 것을 의미한다.
• Canonical collection
  LR(0) 항목 집합의 canonical collection은 C0로 표기하며
  C₀ ＝ {closure ([S'→ ․ S]) ∪ {GOTO (I, X)| I ∈ C₀, X∈V} 이다. 즉, closure ([S'→ ․ S])를 구한 후 반복해서 GOTO (I, X)를 적용한 것들의 집합이다. 

요약정리

1. 순위 구문분석에서는 handle을 찾기 위해서 여러 가지 제약조건들을 주었으나, 이런 제약조건들 때문에 일반적인 프로그래밍 언어의 구문구조를 표현하기에는 적당하지 못한 단점이 있었다. LR(Left to right scanning and Right parse) 구문분석은 일반적인 프로그래밍 언어의 구문구조를 표현하고 구문분석을 하기 위해서 나온 방법이다.
2. LR 파싱표를 구성하는 방법은 3가지가 있다. 첫째, LR(0) 항목의 집합과 FOLLOW로부터 파싱표를 만드는 Simple LR(SLR) 방법, 둘째, LR(1) 항목의 집합으로부터 파싱표를 만드는 방법인 Canonical LR(CLR) 방법, 셋째, LR(0) 항목의 집합과 lookahead로부터 또는 LR(1) 항목의 집합으로부터 구성하는 방법인 LookAhead LR(LALR) 방법 등이다.
3. 증가문법(augmented grammar)이란 G=(VN,VT,P,S)에서 G에 첨가된 문법으로 G'=(V_N∪{S'},V_T ,P∪{S' → S},S')를 뜻한다. 여기서 생성규칙 S' → S을 첨가하는 이유는 구문분석시 주어진 문장에 accept 되는 것을 S' → S로 reduce되는 경우로 취하기 위한 것이다.
4. 마크기호가 [A→ α․Bβ]와 같이 논터미널인 경우에 이 논터미널 B 를 생성규칙의 왼쪽으로 갖는 LR(0) 항목을 구하는 것을 closure라고 한다. 이 closure는 반복적으로 계속 적용된다. 이 closure는 반복적으로 계속 적용된다. 즉, 한 상태에서 valid한 모든 LR(0) 항목을 구하는 것이다.
5. SLR 구문분석은 LR 구문분석 방법 중 가장 간단하게 구현될 수 있는 방법으로서, SLR의 파싱표를 만드는 방법은 LR(0) 항목의 집합과 FOLLOW를 이용한다. SLR 파싱표는 shift와 GOTO 행동은 LR(0) 항목의 canonical collection으로부터 구해지고, reduce는 생성규칙의 논터미널 기호의 FOLLOW를 보고 결정한다. 

연습문제

• 

  다음은 LR(0) 항목 집합의 canonical collection을 구하는 과정이다. GOTO(I0, E) 를 보기에서 고르시오.
  

  1. canonical collection
  I₀ : closure ([S' → ·E]) ={[S' → ·E], [E → ·E+T], [E → ·T], [T → ·T*F], [T → ·F], [F → ·(E)],
  [F → ·id]}
  I₁ = GOTO (I₀, E)
  I₂ = GOTO (I₀, T)
  I₃ = GOTO (I₀, F)
  :
  I₇ = GOTO (I₂, * )
  
  [보기]
  (가) [T → F·]
  (나) [E → T·], [T → T·*F]
  (다) [S' → E·], [E → E·+T]
  (라) [T→ T*․F],[F→ ․(E)], [F→ ․id]

  답을 체크하세요

  1. (가)
  2. (나)
  3. (다)
  4. (라)

  정답 :

  ③

  I₀ ={[S' → ·E], [E → ·E+T], [E → ·T],
               [T → ·T*F], [T → ·F], [F → ·(E)], [F → ·id]}
  에서 ·E를 포함하고 있는 것은 [S' → ·E], [E → ·E+T] 이다.
  따라서
       I1 = GOTO (I0, E) = closure{[S'→ E․], [E → ·E+T]}
                          ＝ {[S'→ E․], [E → E․＋T]}
  보기 (다)가 된다.

• 

  다음은 LR(0) 항목 집합의 canonical collection을 구하는 과정이다. GOTO(I0, T) 를 보기에서 고르시오.
  

  I₀ : closure ([S' → ·E])
   ={[S' → ·E], [E → ·E+T], [E → ·T],
    [T → ·T*F], [T → ·F], [F → ·(E)], [F → ·id]}
  
  [보기]
  (가) [F → id·]
  (나) [T → F·]
  (다) [E → T·], [T → T·*F]
  (라) [S' → E·], [E → E·+T]

  답을 체크하세요

  1. (가)
  2. (나)
  3. (다)
  4. (라)

  정답 :

  ③

  GOTO (I₀, T) =closure{[E → ·T],[T → ·T*F]}={[E → T·], [T → T·*F]}

• 

  다음은 SLR 구문분석을 위해 LR(0) 항목 집합의 canonical collection을 구하는 과정이다. 다음 중 GOTO (I₀, F) 항목은?
  

  I₀ : closure ([S' → ·E]) ={[S' → ·E], [E → ·E+T],        [E → ·T], [T → ·T*F], [T → ·F], [F → ·(E)],
         [F → ·id]}

  답을 체크하세요

  1. [F→ id․]
  2. [E → T·], [T → T·*F]
  3. [S' → E·], [E → E·+T]
  4. [T→ F ․]

  정답 :

  ④

  I₀ 에서 F 앞에 ․이 있는 것을 고르면 된다.
  closure ([T → F·]) = { [T→ F ․] }

• 

  파싱표를 이용하여 문장 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$	shift 5
  1	0id5	+id$	reduce 6
  2	0F	+id$	(   가   )
  3	0F3	+id$	reduce 4
  4	0T	+id$	goto2
  ：	0T2	+id$

  답을 체크하세요

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

  정답 :

  ③

  상태가 0 이고 입력기호가 F 인 곳을 파싱표에서 찾아보면 3 이다. 

• 

  다음은 GOTO 그래프를 이용하여 SLR 파싱표를 구하는 과정이다.‘가’에 알맞은 내용은?
  

  
  

  

  
  
  
  < SLR 파 싱 표 >
  

  상태	구문분석기의 행동						GOTO 함수
  	id	+	*	(	)	$	E	T	F
  0	‘가’			S4			1
  1

  

  

  

  답을 체크하세요

  1. 1
  2. S4
  3. S5
  4. accept

  정답 :

  ③

  GOTO 그래프에서 I0 는 id 에 의해서 만나는 곳을 보면 I5 이다. 따라서 shift 5 이다.