SLR Parsing / CLR Parser

Example ) 다음 문법에 대한 SLR parsing table을 만들어보자.

 

P:

① S → L = R

② S → R

③ L → ＊R

④ L → id

⑤ R → L

 

 

1. Augmented grammar 를 만든다.

 

S' -> S 를 추가해주면 끝이다.

 

P:

 S' -> S

① S → L = R

② S → R

③ L → ＊R

④ L → id

⑤ R → L

 

 

2. Canonical collection 을 계산한다.

 

I0 = CLOSURE([S' -> •S])

    = {[S' -> •S], [S -> •L = R], [S -> •R], [L -> •*R], [L ->•id], [R -> •L]}

 

GOTO(I0, S) = CLOSURE([S' -> S•])

                    = {[S' -> S•]} = I1

GOTO(I0, L) = CLOSURE({[S -> L •= R], [R -> L•]})

                    = {[S -> L •= R], [R -> L•]} = I2

GOTO(I0, R) = CLOSURE([S -> R•])

                    = {[S -> R•]} = I3

GOTO(I0, *) = CLOSURE([L -> *•R])

                   = {[L -> *•R], [R -> •L], [L -> •*R], [L -> •id]} = I4

GOTO(I0, id) = CLOSURE([L -> id•])

                     = {[L -> id•]} = I5

 

I1 는 GOTO 할 수 없다.

 

GOTO(I2, =) = CLOSURE([S -> L = •R]) 

                   = {[S -> L = •R], [R -> •L], [L -> •*R], [L ->•id]} = I6

 

I3 는 GOTO 할 수 없다.

 

GOTO(I4, R) = CLOSURE([L -> *R•])

                    = {[L -> *R•]} = I7

GOTO(I4, L) = CLOSURE([R -> L•])

                    = {[R -> L•]} = I8

GOTO(I4, *) = CLOSURE([L -> *•R])

                   = {[L -> *•R], [R -> •L], [L -> •*R], [L -> •id]} = I4

GOTO(I4, id) = CLOSURE([L -> id•])

                     = {[L -> id•]} = I5

 

I5 는 GOTO 할 수 없다.

 

GOTO(I6, R) = CLOSURE([S -> L = R•]) 

                    = {[S -> L = R•]} = I9

GOTO(I6, L) = CLOSURE([R -> L•])

                    = {[R -> L•]} = I8

GOTO(I6, *) = CLOSURE([L -> *•R])

                   = {[L -> *•R], [R -> •L], [L -> •*R], [L ->•id]} = I4

GOTO(I6, id) = CLOSURE(L -> id•)

                     = {[L -> id•]} = I5

 

I7 는 GOTO 할 수 없다.

 

I8 는 GOTO 할 수 없다.

 

I9 는 GOTO 할 수 없다.

 

Canonical collection 을 계산하였다.

 

GOTO graph를 그려보면 다음과 같다.

 

 

3. FOLLOW 를 계산한다.

 

(1) FOLLOW 를 계산하기 위해선 FIRST가 필요하다.

 

직관적으로 FIRST는 Ring Sum을 이용하지 않고 바로 구할 수 있어 보인다.

 

FIRST(S) = {*, id}

FIRST(L) = {*, id}

FIRST(R) = {*, id}

 

(2) FIRST 를 이용하여 FOLLOW 를 계산한다.

 

(2) - (1)

먼저 FOLLOW(S) = {$} 를 해준다.

 

(2) - (2)

(FIRST(=) - {ε}) ⊂ FOLLOW(L) 

뿐이므로 FOLLOW(L) = {=} 이다.

 

(2) - (3)

FOLLOW(S) ⊂ FOLLOW(R)

FOLLOW(L) ⊂ FOLLOW(R)

FOLLOW(R) ⊂ FOLLOW(L)

 

FOLLOW(S) = {$}, FOLLOW(R) = {$, =}, FOLLOW(L) = {$, =} 이 만들어 졌다.

 

 

4. Parse table 을 만든다.

 

State	Action				GOTO
	=	*	id	$	S	R	L
0		s4	s5		1	3	2
1				Accept
2	s6, r5			r5
3				r2
4		s4	s5			7
5	r4			r4
6		s4	s5			9	8
7	r3			r3
8	r5			r5
9				r1

 

 

Shift-reduce conflict

 

앞의 parse table 에서 2번 상태 :

- ACTION[2, =] = shift 6

- ACTION[2, =] = reduce 5

 

“Shift-reduce conflict”

- State 2 에서 다음 입력으로 =를 만나게 되면 충돌이 발생한다.

  그런데 실제로는 rhs에서 R 다음에 =이 나타나는 rule은 없다.

  따라서 2번 상태에서 reduce는 유효하지 않다.

  이러한 것을 non-deterministic 하다고 한다.

 

- Deterministic LR parsing을 위해 CLR 파싱과 LALR 파싱이 제안되었다

 

 

CLR parser

 

 

SLR parsing table:

- FOLLOW에 속하는 기호들에 대해 reduce action을 만들었다.

- 이 때, reduce item [A → α•]에 대해서, FOLLOW(A)에는 속하지만 nonterminal A 다음에 나오지는

  않는 기호들이 존재할 수 있다. 이 문제로 인해 파싱이 불가능한 경우가 생긴다.

- 따라서 A 다음에 나올 수 있는 기호에 대해서만 reduce를 하는 것이 타당하며, 이를 수행하는 것이

  CLR parsing 이다.

 

Terminology:

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

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

 

[정의] LR(1) item

LR(1) item은 [A → α•β, a] 형태이며, 여기서 A → αβ ∈ P이고 a ∈ {VT U $}이다.

- 첫 번째 부분인 A → α•β를 코어(core)라 하며, LR(0) item과 같은 의미이다.

- 두 번째 부분인 a를 lookahead라 하며, 코어가 reduce item일 때 기호 a에 대해 감축 행동을 하라는 것이다.

 

 

Parse table을 구현하려면 LR(1) item set의 canonical collection이 필요하다.

 

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 U {[B → •𝛄, b] | [A → α•Bβ, a] ∈ CLOSURE(I), B→ 𝛄 ∈ P, b ∈ FIRST(βa)}

 

 

Example ) 다음 문법에서 LR(1) item [S′ →•S, $]에 대한 CLOSURE를 구해보자.

 

P:

S′ → S

S → CC

C → cC

C → d

 

여기서 core : S′ →•S,  lookahead : $ 이다.

 

CLOSURE([S' →•S, $])

= {[S' →•S, $], [S →•CC, $], [C →•cC, c], [C →•cC, d], [C →•d, c], [C →•d, d]}

 

lookahead가 어떻게 변하는지 분석해보도록 하자.

 

[S →•CC, $] 이전에 [S' →•S, $] 에 대해서 FIRST(ε$) = {$} 이므로 lookahead는 $ 이다.

 

[C →•cC, c/d] 이전에 [S →•CC, $] 에 대해서 FIRST(C$) 는 다음과 같이 구할 수 있다.

 

먼저 FIRST(C) = {c, d} 이므로 Ring Sum 공식에 의하면 FIRST(C$) = {c, d} 이다.

 

따라서 lookahead는 c, d 이다.