CLR parser

CLR parser

SLR parser는 reduce item [A->ɑ·]에 대해서, FOLLOW(A)에는 속하지만 nonterminal A 다음에 나오지는 않는 기호들이 존재할 때 파싱이 불가능해진다.이를 해결하기 위해 Lookahead와 LR(1)을 이용한 CLR parser를 사용해야 한다.

 

Lookahead : 한 state에서 어떤 논터미널 기호 다음에 나올 수 있는 터미널 기호

LR(1) item : LR(0) item에 lookahead 정보를 첨가한 것

 

LR(1) item set의 Canonical collection C1

• CLOSURE 함수와 GOTO 함수가 필요
• GOTO 함수는 LR(0) item set의 canonical collection C0를 구할 때와 동일
• CLOSURE 함수는 lookahead 정보를 활용하는 다른 방식으로 구현

LR(1) item set I에 대한 CLOSURE function

CLOSURE(I)= I ∪ { [B->·𝛾,b] | [A->ɑ·Bβ,a] ∈ CLOSURE(I), B->𝛾∈P, b ∈ FIRST(βa) }

여기서 a는 lookahead를 의미하고 FIRST,FOLLOW 모두 구할 줄 알아야한다.

 

LR(1) item

• LR(1) item은 [A->ɑ·β,a] 형태이며, 여기서 A->ɑβ ∈ P이고, a ∈ { Vt ∪ $ }이다.
• 첫 번째 부분인 A->ɑ·β를 코어(core)라 하며, LR(0) item과 같은 의미이다.
• 두 번째 부분인 a를 lookahead라 하며, 코어가 reduce item일 때, 기호 a에 대해 감축 행동을 하라는 것이다.

3번째 production C-> cC로 수정

 

LR(1) item sets의 canonical collection을 구하는 것은 SLR과 같다.

 

위의 문법의 LR(1) item sets의 canonical collection

---

CLR Parse Table

CLR Parse Table 만드는 법

1. G'에 대한 LR(1) item의 canonical collection C1={I0,I1,...,In}을 구성한다.

2. State i는 li 에서 구성되고, state i를 위한 parsing action은 다음과 같다.

• 만약 LR(1) item [A->ɑ·aβ,b]∈Ii, GOTO(Ii,a)=Ij이면 action 표의 M[i,a] = Shift j
• 만약 LR(1) item [A->ɑ·,a]∈Ii 이면 action 표의 M[i,a] = Reduce A-> ɑ
• 만약 LR(1) item [S'->S·,$]∈Ii이면 action 표의 M[i,$] = Accept

3. 만약 LR(1) item [A->ɑ·Bβ,a] ∈ Ii 이고 GOTO(Ii,B)=Ij이면 GOTO표의 M[i,B] = j

4. Augmented production rule의 LR(1) item [S'->·S,$]를 포함하는 state는 initial state.

State	Action			GOTO
	c	d	$	S	C
0	s1	s4		1	2
1			acc
2	s6	s7			5
3	s3	s4			8
4	r3	r3
5			r1
6	s6				9
7			r3
8	r2	r2
9			r2

---

Example

Step	Stack	Input buffer	Parsing
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