컴파일러구성 - [제10강] CLR 구문분석

컴파일러구성 - [제10강] CLR 구문분석

SLR 충돌문제와 lookahead ·closure와 GOTO 함수 ·CLR 파싱표와 구문분석

컴파일러 용어정리

• LR
  Left to right scanning and Right parse
• SLR 구문분석
  Simple LR 구문분석은 LR 구문분석 방법 중 가장 간단하게 구현될 수 있는 방법이다. SLR 파싱표를 만드는 방법은 LR(0) 항목의 집합과 FOLLOW를 이용한다.
• CLR 구문분석
  Canonical LR 구문분석은 SLR 의 충돌문제를 해결한 구문분석 방법이다. lookahead를 이용하는 방법인데, lookahead를 구해야 하므로 과정이 복잡하고 시간이 오래 걸리며 파싱표가 커진다.
• LR(1)
  LR(0)항목에서 lookahead 정보를 첨가한 것.
  LR(1) 항목은 [A → α․β, a]형태를 가지며
  여기서 A → αβ ∈ P이고 a ∈ V_T ∪ {$} 이다.
  A → α․β를 core라 부르며 LR(0) 항목과 같은 의미이다.
• lookahead
  LR(1) 항목 [A → α․β, a]에서 a를 항목의 lookahead라 부르며, reduce 항목 일 때 그 기호에 대해서 reduce 행동을 하는 것을 뜻한다. 

요점정리

1. 한 상태에서 어떤 논터미널 기호 다음에 나올 수 있는 터미널 기호들을 lookahead라 부르는데 이를 이용하려고 하는 것이 바로 CLR 방법이다.
2. LR(0) 항목에서 lookahead 정보를 첨가한 것이 LR(1) 항목이며 [A → α․β, a] 형태를 가지며 여기서 A → αβ ∈ P이고 a ∈ V_T ∪ {$} 이다. 첫 번째 부분 A → α․β를 core라 부르며 LR(0) 항목과 같은 의미이다. 두 번째 부분 a를 항목의 lookahead라 부르며, reduce 항목 일 때 그 기호에 대해서 reduce 행동을 하는 것을 뜻한다.
3. CLR 파싱표를 구성하기 위해서는 LR(1) 항목 집합의 canonical collection을 구해야 하는데, 이것 역시 closure 함수와 GOTO 함수가 필요하다. GOTO 함수는 LR(0) 항목 집합의 canonical collection을 구할 때와 같으며 closure 함수는 lookahead 정보 때문에 약간 수정해야 한다.
4. CLR방법은 한 상태에서 어떤 논터미널 기호 다음에 나올 수 있는 터미널 기호인 lookahead를 이용하는 방법인데, lookahead를 구해야 하므로 과정이 복잡하고 시간이 오래 걸리며 파싱표가 커지는 단점이 있다.

• 

  다음은 CLR 그래프를 이용하여 파싱표를 구성하고 구문분석을 하는 과정이다.
  빈칸 ‘가’에 알맞은 것은?
  

  

  
  
  < CLR 파싱표 >
  

  상태	구문분석기의 행동			GOTO 함수
  	c	d	$	S	C
  0	S3	(가)		1	2
  1			acc
  2	S6	S7			5
  3	S3	S4			8
  4	r3	r3
  5			r1
  6	S6	S7			9
  7			r3
  8	r2	r2
  9			r2

  

  

  

  답을 체크하세요

  1. S4
  2. S7
  3. 2
  4. r3

  정답 :

  ①

  CLR 그래프에서 터미널기호에 의해서 전이되는 것은 shift
  논터미널 기호에 의해서 전이되는 것은 goto 로 파싱표를 구성하면 된다.
  항목집합0 에서 터미널 기호 d를 따라가 보면 4번 항목집합이 나온다.
  따라서 shift 4 가 된다. 

• 

  다음은 LR(1) 항목 집합의 canonical collection 들이다. 보기에서 I₀ 는?
  

  (1) 증가문법
              0) S' → S
              1) S → CC
              2) C → cC
              3) C → d
  (2) Canonical Collection.
              I₀ = closure ([S' → ·S, $])
              I₁ = GOTO (I₀, S)
              I₂ = GOTO (I₀, C)
  
  [보기]   (가) [S' → ·S, $], [S → ·CC, $],
                   [C → ·cC, c/d],[C → ·d, c/d]
            (나) [S → C·C, $], [C → ·cC, $],
                   [C → ·d, $]
           (다) [S' → S·, $]
           (라) [C → d·, c/d]

  답을 체크하세요

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

  정답 :

  ①

  I₀ = closure ([S' → ·S, $])
     = {[S' → ·S, $], [S → ·CC, $], [C → ·cC, c/d],
       [C → ·d, c/d] }

• 

  다음은 CLR 파싱표를 이용하여 구문분석하는 과정이다. 빈칸 ‘가’에 알맞은 것은?
  

  상태	구문분석기의 행동			GOTO 함수
  	c	d	$	S	C
  0	S3	S4		1	2
  1			acc
  2	S6	S7			5
  3	S3	S4			8
  4	r3	r3
  5			r1
  6	S6	S7			9
  7			r3
  8	r2	r2
  9			r2

  
  
  문장 cdcd에 대한 구문분석의 일부이다.
  
  

  단계	스택	입력기호	구문분석 내용
  0	0	cdcd$	shift 3
  1	0c3	dcd$	shift 4
  2	0c3d4	cd$	reduce3
  3	0c3C	cd$	goto 8
  4	0c3C8	cd$	reduce 2
  5	0C	cd$	( ‘가’ )
  6	0C2	cd$	shift 6
  7	0C2c6	d$	shift 7
  8	0C2c6d7	$	reduce 3

  답을 체크하세요

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

  정답 :

  ④

  CLR 파싱표에서 상태=0, 입력기호=C를 찾아보면 goto 2
  
  

  단계	스택	입력기호	구문분석 내용
  0	0	cdcd$	shift 3
  1	0c3	dcd$	shift 4
  2	0c3d4	cd$	reduce3
  3	0c3C	cd$	goto 8
  4	0c3C8	cd$	reduce 2
  5	0C	cd$	goto 2
  6	0C2	cd$	shift 6
  7	0C2c6	d$	shift 7
  8	0C2c6d7	$	reduce 3

• 

  다음은 CLR 그래프를 이용하여 파싱표를 구성하는 과정이다. 빈칸 ‘가’에 알맞은 것은?
  

  
  

  

  
  
  < CLR 파싱표 >
  

  상태	구문분석기의 행동			GOTO 함수
  	c	d	$	S	C
  0	S3	S4		1	2
  1			acc
  2	S6	S7			5
  3	S3	S4			8
  4	r3	r3
  5			r1
  6	S6	S7			9
  7			(가)
  8	r2	r2
  9			r2

  

  

  

  답을 체크하세요

  1. r1
  2. r2
  3. r3
  4. r4

  정답 :

  ③

  I₇은 $에 의해서 도달하는 곳은 [C → ·d, $] 즉, reduce 항목이다. 문법규칙은 3번 규칙이므로 r3 이 된다. 

• 

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

  

  
  
  < CLR 파싱표 >
  

  상태	구문분석기의 행동			GOTO 함수
  	c	d	$	S	C
  0	S3	S4		1	2
  1			(가)
  2	S6	S7			5
  3	S3	S4			8
  4	r3	r3
  5			r1
  6	S6	S7			9
  7			r3
  8	r2	r2
  9			r2

  

  

  

  답을 체크하세요

  1. S6
  2. S7
  3. r3
  4. acc

  정답 :

  ④

  I₁에서 $를 만나면 accept가 된다.