[컴개/CI] Bottom-Up 구문 분석, Shift-Reduce Parsing

위 사진은 앞 포스트에서 보여준 reduce 과정이다.

이 과정을 stack을 통해 시행해보자.

초기 상태는 스택에 $, 입력 버퍼에는 입력 스트링과 $를 모두 넣는다.

accept 상태는 스택의 top에 시작 심벌이 있고 입력은 모두 읽은 상태이다.

스택의 top 모습을 보고 reduce와 shift를 한다.

이때 reduce 할 때는 입력 버퍼에 영향이 없다.

 

이때, 우리는 shift와 reduce를 어떻게 판단할 수 있을까?

스택에 β가 있고 입력 글자가 b일 때, β = αγ이고, X -> γ가 있다면,

스택을 αX로 만들 것인지, βb로 만들 것인지에 대한 고민에 빠진다.

 

또, 여러 가지 reduce가 있는 경우 스택 중 어디까지 handle로 봐야 하는 것일까.즉, 스택이 β = αγ일떄, X -> γ에 의한 reduce 시 가능한 γ의 길이가 여러 가지일 수 있다.

우리는 이러한 고민을 LR Parsing Engine을 통해 해결할 수 있다.

 

LR Parsing Engine

LR Parsing Engine은 '파서 상태'라는 것을 사용한다.

스택에 입력 심벌을 shift할 때, 관련 파서 상태를 함께 넣는 것이다.

ex) 0 ( 6 E 10 + 5 (붉은 글씨가 상태 번호이다.)

이 파서 상태가 무엇인지에 따라 reduce 할 것인지, shift 할 것인지

결정할 수 있고, 어디까지를 handle로 볼 것인지 결정할 수 있다.

즉, 애매할 일이 없다.

 

파싱 테이블도 <상태> X <심벌>의 형태이다.

파서는 파싱 테이블을 통해 현재 상태와 임력 심벌을 보고

shift할지, reduce할지(action table) 결정하고,

파서 상태도 변경(goto table)시킨다.

 

LR Parsing Table

위 파싱 테이블을 통해 현재 상태 S와 입력 상태 a를 보고 다음과 같은 행동을 취할 수 있다.

1. M[S, a] = shift S'라면 shift: push(a), push(S')

2. M[S, a] = reduce X -> α라면 reduce: pop(2*|α|), S' = pop(), push(X), push(M[S', X])

 

아래 예시를 보자.

규칙은 위와 같고

파싱 테이블은 위와 같다.

 

시작 상태는 0이며, 입력 문자열은 a, a이다.

위 그림에서 시작 상태 0으로 시작하고 0과 a의 조합을 고민한다.

상태가 0일 때 입력으로 a가 들어오면 파싱 테이블에서는 s3을 가리키므로 스택에 a와 3을 함께 넣는다.

 

이후 a와 3이 스택에 존재할 때 reduce S -> a가 파싱 테이블을 통해 매칭되므로

a와 3을 모두 pop하고 S를 넣어준다.

 

이후의 stack의 모습을 보면 스택의 top에 상태 번호가 없고 non-terminal이 존재한다.

이때는 goto table을 통해 상태를 넣어주면 된다.

스택 안에 0과 S가 있으므로 goto table을 통해 2번 상태를 넣어준 후

S와 2를 매치하며 또 다시 reduce L -> S를 진행하고

스택의 top에 non-terminal이 존재하여 0과 L을 매치하여 1번 상태를 넣는다.

위와 같은 과정을 반복하면 문자열은 accept된다.

 

이때, 느꼈을 지 모르겠지만 상태 번호는 한 번 읽으면 모두 pop되고,

reduce가 등장하면 항상 goto가 등장한다.

 

이때, parsing table은 어떻게 만들까?

 

LR Parsing Table 만들기

LR(0) 파싱 테이블을 만드는 방법은 아래와 같다.

1. 파서 상태가 될만한 것들을 정한다. (LR(0) item, Closure)

2. 각 파서 상태들 간의 상태 전이도(DFA)를 만든다. (GOTO 이용)

   (DFA = Deterministic Finite Automata)

3. 이것을 parsing table에 담으면 된다.

 

LR 파서 중간 정리

LR(k)

Left-to-Right 스캔, 우측 유도, k개의 lookahead 문자

기본적으로 LR(0), LR(1)이고 k가 커질수록 더 정교해진다.

사용하기 위해 변형한 것으로는 SLR, LALR(1) 등이 있다.

 

LR(0)

lookahead없이 파싱하고 shift-reduce형태이다.

우리가 지금까지 보아 왔던 것이 LR(0)이다.