[컴개/CI] Bottom-Up 구문 분석, 파싱 테이블과 SLR 파서

Shift와 Reduce의 의미

입력으로 '((a),b)'이 들어 온 경우 아래와 같이 파싱할 수 있다.

 

SLR Parser

앞선 LR(0)의 파싱 테이블은 conflict가 발생한다.

왜냐하면 reduce 시에 모든 셀에 대해 reduce를 채우기 때문이다.

따라서 이러한 LR(0)의 충돌을 줄이기 위해 SLR(Simple LR) Parser가 등장했다.

 

SLR 파싱 테이블은 약간의 노력을 더해 LR(0)의 conflict를 줄이고 정교하게 만들어 주는 것으로

I1이 [X -> β.]를 포함할 때, M[I1, a] = 'reduce X -> β'이다 (단, a ∈ FOLLOW(X))

즉, 파싱 테이블에서 X의 팔로우에 속하는 터미널에 대해서만 reduce를 진행한다는 의미이다.

나머지는 LR(0)과 동일하다.

 

예시를 보자.

위와 같은 생성 규칙이 존재한다.

해당 생성 규칙을 바탕으로 SLR 파싱 테이블을 만들면 아래와 같다.

(단, FOLLOW(S) = {$, ), ','}, FOLLOW(L) = {), ','})

 

마지막으로 조금 더 어려운 예시를 보겠다.