[컴파일러] LR(0) 파싱 | SLR 파서에서 FOLLOW를 적용하는 이유와 SLR파서의 약점

사전 지식

∨ (가장 기본) LR 파싱이란?

shift-reduce의 문제점

(관련 글: https://splendidlolli.tistory.com/524)

Bottom-up 파싱이란? 그리고 shift-reduce parsing (이동-감축 구문분석)

 

① 핸들을 어떻게 찾을 건데?

    == shift를 더 할지, 그만 reduce할지 선택 문제

 

② 찾은 핸들에 어떤 생성규칙을 적용할 건데?

    == reduce 방법이 여러가지 있는 경우

    == 스택 탑에서 어디까지를 handle로 볼지의 문제

    (문법이 모호하지 않더라도 이런 상황이 가능함)

 

위 두가지가 문제이다!

그치만 해결 방안으로 LR 파싱이 있다 - 가장 보편적인 파싱 방법이다.

 

.

.

LR parsing

 

▶ LR이 의미하는 것

- Left to right & Right parse

- 즉 스캐닝을 → 방향으로 하고 & 우파스를 생성한다는 것

- LR은 LR(1)을 의미한다. lookahead인 1을 생략하자는 것이다.

 

▶ LR 파싱의 분류

: 파싱 테이블을 구성하는 방법에 따라 다르다!

① SLR 파싱 (simple LR) ㅡ 구현이 쉬운데 매우 강력하지 않다. LR(0) 사용한다.

② CLR 파싱 (canonical LR) ㅡ 구현이 매우 어렵지만 가장 강력하다. LR(1)은 강력하고, LR(1)을 사용한다.

③ LALR 파싱 (lookahead LR)  ㅡ 그 중간쯤이다! 가장 많이 이용되고 꽤 강력!

                                                  얘는 LR(1)으로도 파싱테이블을 구성할 수도 있고, LR(0)으로 구성할 수도 있다.

 

 

∨ LR(0) 파서

- lookahead 없이 파싱

- :파서 상태를 변경시키며 shift-reduce 액션을 한다.

 

∨ LR(0) 항목

[ Intro ]

- 생성규칙 오른쪽 (right hand side, rhs)에 점 기호를 가진 생성규칙들이 LR(0)의 항목이다.

- 만약 A → B.CD라면, 점으로 mark하여 이렇게 나뉜다 : B는 읽은 기호이고 C는 앞으로 읽을 기호(마크심볼)이다.

- A → BCD. 처럼 점이 맨 끝에 온 경우 : BCD로 감축한다.

[ 좀 더 자세히 .. ]

- LR(0) 항목의 종류는 3가지다

① kernel item : A → α.β

(커널 항목 - 단 "α가 null이 아님" 또는 "A가 시작심볼")

② closure item : A → .α

(클로저 항목 - 점 기호가 생성규칙 처음에 있음)

③ reduce item : A → α.

(감축 항목 - 점 기호가 생성규칙 끝에 있음)

 

 

∨ C0란?

Augmented grammar에 의해 추가된 생성규칙 S'→S 로부터 closure와 goto를 적용해나가며 나올 수 있는 모든 LR(0) item 집합들을 말한다. 즉 C0 = {I0, I1, ..., In}으로 나타내는데 I0는 closure(S'→S)이고, 각 Ik는 각 마크심볼에 대한 goto를 타고 가서 나오는 상태이다. 

 

 

---

사전지식 & intro

 

  Buttom-up 파싱, 즉 LR파싱을 하기 위하여 파싱테이블을 만들 때, 파서 상태와 심볼들을 통해 파싱테이블을 구성한다.

LR 파싱테이블을 구성하는 방법은 SLR파싱, CLR파싱, LALR파싱 방법에 따라 다르다.

그러나 공통적으로 LR 파싱테이블은 '파서 상태'가 행이고, Terminal과 Non-terminal 심볼이 열이 되며, 각각은 action테이블과 goto테이블을 만든다.

 

지금은 LR(k)중에 lookahead가 0인 LR(0)문법에 대한 파싱방법을 공부한다.

LR 파싱 방법 중 가장 간단하게 구현할 수 있는 SLR 파싱은 LR(0) 항목들을 가지며, 생성규칙의 Non-terminal의 FOLLOW를 가지고 감축을 결정한다. 

 

그런데 왜 FOLLOW를 사용하여 감축을 결정해야 할까?

그냥 LR(0) 기본대로 '파서 상태'와 '기호'들로만 감축을 결정할 수는 없을까?

아래 예제를 보며 SLR 파싱에서 FOLLOW가 필요한 이유를 알아보자.

 

---

LR(0) 그대로는 전혀 강력하지 않아서 FOLLOW까지 적용한다

이 제목이 결론이다. 

LR(0) 파싱은 lookahead도 없고, 파서상태와 shift, reduce만 활용하는 파싱법이다.

이런 LR(0) 파싱법만 사용하면 어떤 상황이 일어날지 확인해보자.

 

 

예를 들어, 아래 문법이 있다.

S' -> S

S -> E + S

S -> E

E -> num

 

다음 문법의 C0 (=> LR(0) transition)을 나타내면 이렇다.

먼저 말하자면 이 LR(0) 파서에서 이 문법은 애매하다.

곧 LR(0) 파싱테이블을 구성해보면 알겠지만,

저기 그림에서.. 상태 I1에서 E라는 non-terminal이 인식될 경우 어떻게 해야 하는지 LR(0) 파싱으로는 결정적이지가 않다.

즉 goto(I1, +)를 해야 하는지, reduce를 해야 하는지 (=> 어떤 action을 할지) 모르겠는 상태가 되는 거다.

 

 

위처럼 결정적이지 않은 상황을 파싱 테이블을 만들면 이렇다.

파싱 테이블을 보면 하나의 셀에 두개의 선택지가 존재한다. "충돌"이 일어난다!

 

++ 먼저 말하자면, 이러한 충돌의 이유는 어떤 파서상태에 reduce 항목이 존재할 경우, action table에서 모든 상황에 reduce 액션을 취하기 때문이다. SLR에서 FOLLOW 정보를 추가적으로 적용하면 이 경우처럼 reduce action을 무조건 적용하지 않게 된다. reduce item이 있을 경우 그 reduce하는 생성 규칙의 lhs에 있는 non-terminal 심볼의 FOLLOW를 보고 reduce행동을 한다는 것이 SLR 파싱의 특징이다. ++ 

 

그럼 LR 파싱을 할 떄 어떤 파싱 방법을 선택해야 (파싱 테이블을 어떤 원리로 만들어야)

좀 더 강력할까? (더 많은 문장을 받아들일 수 있을까?)

 

정답은 SLR 파싱 방법을 사용하는 것이다.

SLR 파싱은 감축을 결정하기 위해 non-terminal의 FOLLOW를 정보를 추가적으로 이용한다.

 

 

---

SLR(1) 파서

참고) SLR은 Simple LR을 의미한다

참고) LR 파서에서 괄호가 생략되면 (1)을 의미하며, SLR(1)도 SLR로 표기하겠다.

 

- LR 파싱법 중 가장 간단히 구현할 수 있다. 하지만 강력한 파싱법은 아니다!

- LR(0) 항목 집합과 FOLLOW를 이용하여 파싱테이블을 만든다.

- 감축 행위를 결정하기 위해 왼쪽의 non-terminal(즉 left hand side)의 FOLLOW를 계산한다.

 

 

SLR 파서에 의해 성공적으로 파싱되는 문법을 SLR문법이라고 한다. (즉 모든 SLR 문법은 모호하지 않다)

※참고 : 모호하면 어떻게 되는가? 

SLR파서에게 모호한 문법의 경우 SLR파서가 파싱하지 못하고 '충돌이 발생한다'.

위 예제와 비슷하게 두 액션 중 하나를 결정하지 못하는 상태가 충돌이고, 두가지 경우가 있다.

- reduce-reduce 충돌

- shift-reduce 충돌

↑ 이러한 충돌이 일어나는 이유는 SLR파서가 별로 강력하지 않은 파서이기 떄문이다.

 

참고) CLR이나 LALR 파서가 훨씬 강력하다.

- CLR : 가장 구현이 어렵지만 가장 강력하다. 강력한 LR(1) 항목을 이용한다!

- LALR : 강력한 정도는 중간쯤이다. LR(0) 항목과 lookahead 1을 사용한다.

 

 

---

SLR 파싱의 FOLLOW는 LR(0)의 어떤 충돌을 해결한다

LR 파서중 가장 약한 SLR 파서지만,

위와 같이 무작정 reduce action을 싹 다 추가하는 경우로 생기는 충돌은 개선할 수 있다.

 

아까 본 문법(↓)에 대한 SLR 파싱테이블을 만들어보자.

아까 LR(0) 파싱법만 적용했을 때에는 충돌이 일어났었다.

SLR 파싱법에서 FOLLOW를 이용하면 그 충돌은 없앨 수 있다!

 

∨ 문법

S' -> S

S -> E + S

S -> E

E -> num

 

∨ C0 표현해보기

C0는 아까 본 C0와 달라질 이유가 없다.

C0 의미를 되새겨보자..

추가된 augumented grammar S->S'로부터 closure랑 goto 적용하여 나올 수 있는 모든 LR(0) 항목 집합

 

달라진 점은 파싱 테이블을 만드는 방법이 달라졌다는 것이다!

파란 글씨의 내용처럼 FOLLOW를 고려하여 action table의 reduce action을 채운다.

 

∨ 위 C0에 따른 SLR 파싱테이블

아까 LR(0) 파싱에서 확인한 그 충돌을 해결했다.

그 충돌의 이유는 어떤 파서상태에 reduce 항목이 있는 경우면 무조건 reduce action을 취했기 때문인데,

FOLLOW 정보를 고려하여 reduce action을 결정함으로써 충돌을 해결한 것이다.

 

 

 

 

∨ LR(0)과 SLR(1)의 파싱테이블 비교하기

 

 

 

 

---

SLR 파싱의 또다른 충돌

그러나 SLR 파싱도 강력한 파싱법은 아니기 떄문에 아래 두가지 충돌이 자주 발생한다.

- shift-reduce 충돌 

- reduce-reduce 충돌

 

그래서 이제 SLR보다 (훨씬) 강력한 LALR 파싱을 배운다.