[컴개/CI] Bottom-Up 구문 분석, LR(0) 파싱 테이블

LR Parsing: 파서 상태

파서는 파싱 테이블을 통해 현재 상태, 입력 심벌을 보고 shift 할 지,

reduce 할 지 결정하고(action), 파서의 상태로 변경한다.(goto)

그렇다면 '상태'란 무엇일까?

 

LR(0)  아이템

LR(0)은 lookahead 없이 파싱하는 shift-reduce 형태이다.

LR(0)의 파싱 테이블은 파서 상태를 정하고, 각 파서 상태들의 상태 전이도를 테이블에 담아내는 형태로 만들어진다.

 

이때,  LR(0)item이란 rhs에 점('.') 심벌을 가진 생성규칙이라고 할 수 있다.

생성 규칙의 형태가 A -> XYZ일 때,

[A -> .XYZ], [A -> X.YZ], [A -> XY.Z], [A -> XYZ.] 모두 LR(0) item이라 할 수 있다.

또, 생성 규칙의 형태가 A -> ε일때, LR(0) item은 [A -> .]이다.

 

Closure

LR(0)의 아이템을 모아둔 집합에 closure를 적용하면 집합의 크기를 키워줄 수 있다.

위의 정의에서 I에 해당되는 집합에 몇 개의 item이 들어가 있는지 확인 후

각각의 item에 대해 closure를 진행한다.

 

t가 terminal 심벌일 때, closure([A -> α.tβ]) = {[A -> αt.β]}이다.

X가 non-terminal 심벌일 때, X -> γ이면

closure([A -> α.Xβ]) = {[A -> αXβ], [X -> .γ]}이다.

즉, 생성된 것에 대해 다시 한 번 closure를 진행한다.(recursively)

 

예시를 보자

위의 생성 규칙이 있다.

closure({[S' -> .G]}) = {[S -> .G], [G -> .E = F], [G -> f],

                                        [E -> .E + T], [E -> .T], [T -> .T * f], [T -> .f]}

closure({E -> E.+T}) = {[E -> E.+T]}

 

또 다른 예시를 보자.

closure({[S' -> .S]}) = {[S' -> S], [S -> .(L)], [S -> .id]}

 

goto

goto(I, X) = closure({[A -> αX.β] | [A -> α.Xβ] ∈ I})

goto는 I 집합 내의 X 앞에 점(.)이 있는 경우

점(.)의 위치를 옮겨주며 closure를 진행하는 것이다.

 

예시를 보자.

I = {[G -> E.=E], [E -> E.+T]}일 때,

goto(I, +) = closure({[E -> E+.T]}) = {[E -> E+.T], [T -> .T*f], [T->.f]}

인데, 이는 I 안에서 + 앞에 점이 있는 경우에 대해 closure를 진행한 것이다.

 

하나의 팁을 주자면, terminal과 non-terminal은 보통 교차되며 나오므로

terminal을 건너가면 non-terminal을 만날 가능성이 높아진다.

또, A -> ε의 goto는 존재하지 않는다.

 

goto의 예시

위의 그림은 goto를 그림으로 나타낸 모습이다.

각 상태마다 점 뒤에 있는 심볼로 나가는 모습을 볼 수 있다.

파란색 박스 안에 존재하는 모든 점 뒤의 심볼은 L, S, (, id이다.

해당 박스로부터 모든 심볼이 다른 상태를 향해 갈 수 있다.

이때, 각 상태는 closure가 모두 구해진 상태임을 알 수 있다.

 

의미

[X -> α.β]는 α까지는 이미 매칭되었다는 뜻으로, 앞으로 β가 올 가능성이 있다는 의미이다.

(이때, β를 '마크 심벌'이라고 한다.)

 

즉, closure([X -> α.Xβ])는 α까지 parse되었고, X를 parse할 것으로 기대하는 상태이다.

 

그렇다면 파서의 상태를 만드는 방법에 대해 알아보자.1. 시작 상태에 대해 생성 규칙 S' -> S를 만드는데, 이를 Agumented Grammer이라고 한다.2. 시작 상태를 [S' -> .S]의 closure로 만든다. ([S' -> S.]가 accept된 상태이다.)3. 이후의 상태로부터 goto를 계산하는데, 이 과정에서 만들어진 것을 C0라고 한다.

 

C0

C0은 추가된 생성 규칙 S' -> S에서부터 차례로 closure와 goto를 적용하여 얻은모든 타당한 LR(0)의 아이템 집합이다.

C0 = {I0, I1, ..., In}이라면, I0는 {S' -> S}의 closure이고,

다른 것들은 여기서부터 각 마크 심벌에 따라 goto를 적용하여 만든 상태이다.

 

item의 분류

• [A -> X.Y]: X != ε일 때, kernel item이다. (보통 그래프 박스의 가장 상단 아이템)
• [A -> .X] : closure item (맨 앞에 .이 있는 경우)
• [A -> X.] : reduce item (.이 가장 뒤에 존재하여 out edge가 없는 경우)

앞서 제시한 예제에 item을 분류한 모습이다.

2, 4, 7 상태의 회색으로 칠해진 부분이 kernel item이고,

노란색 박스는 시작상태, 파란색 박스는 accept상태이다.

 

파싱 테이블

LR(0)의 파싱 테이블 구하기

파서 상태로 C0 = {I0, I1, ..., In}과 transition을 이용한다.

- goto(I1, a) = I2이면, M[I1, a] = 'shift I2' (터미널로 가는 goto인 경우)

- goto(I1, N) = I2이면, M[I1, N] = 'goto I2' (논터미널로 가는 goto인 경우)

- I1이 [X -> β.]를 포함하는 경우 M[I1, *] = 'reduce X -> β'이고

  모든 cell을 reduce로 채운다.

- I1이 [S' -> S]를 포함하는 경우 M[I1, $] := accept

 

파싱 테이블의 형태

생성 규칙이 위와 같을 때, 파싱 테이블의 형태는 아래와 같다.

C0을 참고하여 파싱테이블을 그리면

위 그림과 같다.