구문 분석 : 상향식 구문 분석 / CLR 구문 분석

SLR 방법에서 파싱표 작성 시 FOLLOW에 속하는 기호에 대해 감축 행동을 만들었음

그러나, 어떤 상태에서는 감축 항목 [A → α•]에 대한 FOLLOW(A)에는 속하지만 그 상태에서 A 다음에 나올 수 없는 기호가 존재

반면에 한 상태에서 어떤 논터미널 기호 다음에 나올 수 있는 정확한 터미널 기호를 lookahead라 하는데, 이를 이용하는 방법이 CLR 구문 분석

- LR(0) 항목에서 lookahead 정보를 첨가한 것이 LR(1) 항목

 

* 간단히 lookahead는, lookahead가 a이면

- [ 만약 reduce 하게 되면 입력이 a일 때만 reduce 가능함 ]의 의미

 

LR(1) 항목

- LR(1) 항목은 [A → α•β, a] 형태 ( A → αβ ∈ P이고 a ∈ {VT  ∪ $} )

- 첫번째 부분인 A → α•β를 코어라 하고, LR(0) 항목과 같은 의미

- 두번째 부분인 a를 lookahead라 하고, 이는 감축 항목일 때 그 기호에 대해 감축 행동을 하라는 것

 

 

CLR 파싱표 작성

- LR(1) 항목 집합의 정규 항목 집합으로 구성

- CLOSURE 함수와 GOTO 함수가 필요

- GOTO 함수는 LR(0)와 같으나, CLOSURE 함수는 lookahead 정보 때문에 수정 필요

 

CLOSURE(I) = I ∪ { [B → •γ , b]  
                   | [A → α•Bβ , a] ∈ CLOSURE(I),
                     B → γ ∈ P,
                     b ∈ FIRST(βa)
                  }

 

1. 이미 있는 항목들은 유지한다(I)

2. 그중에서 점(•) 뒤에 B가 있는 항목을 찾는다

3. B의 모든 생산식 B→γ 에 대해

4. [B → •γ , b] 를 추가한다

 

LR(0)와 차이는 b가 같이 붙는 거( b ∈ FIRST(βa) )

lookahead 첨가

- [A → α•Bβ, a]에서 마크 기호 B다음에 오는 β의 FIRST가 항목 [B → •γ ]의 lookahead

- 만일 β가 ε을 유도 가능 시, [A → α•Bβ]의 lookahead인 a도 lookahead

=> βa의 FIRST가 [B → •γ ]의 lookahead

 

예시

S' -> S

S -> CC

C -> cC

C -> d

문법에서 [S' -> •S, $] 에 대한 CLOSURE를 구하기

 

CLOSURE( [S' -> •S, $] )

= { [S' -> •S, $], [S' -> •CC, $], [C -> •cC, c/d], [C -> •d, c/d] }

* c/d는 둘 다 있는데 축약한 거

* •CC에서 뒤쪽 C의 FIRST가 c, d

 

정규 항목을 만드는 방법을 LR(0)와 동일

 

 

예시

S -> CC

C -> cC

C -> d

이 문법에서의 LR(1) 항목의 정규 항목 집합 및 구문 분석

 

(1) 증가 문법

0. S' -> S

1. S -> CC

2. C -> cC

3. C -> d

 

(2) CLR 정규 항목 집합과 GOTO 그래프

 

 

(3) 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

 

(4) 문장 ccdd의 구문 분석

단계	스택	입력 기호	구문 분석 내용
0	0	ccdd$	s3
1	0c3	cdd$	s3
2	0c3c3	dd$	s4
3	0c3c3d4	d$	r3
4	0c3c3C	d$	GOTO 8
5	0c3c3C8	d$	r2
6	0c3C	d$	GOTO 8
7	0c3C8	d$	r2
8	0C	d$	GOTO 2
9	0C2	d$	s7
10	0C2d7	$	r3
11	0C2C	$	GOTO 5
12	0C2C5	$	r1
13	0S	$	GOTO 1
14	0S1	$	acc

 

 

CLR 방법은 SLR 방법보다 매우 강력

하지만 lookahead를 구해야 해서 과정이 복잡하고 시간이 오래 걸리고, 파싱표가 커짐

이러한 단점을 보완하기 위해 LR(1)처럼 감축 행동은 lookahead를 이용하고 파싱표의 크기는 되도록 작게 구성..

-> LALR