[Compiler Design] LR(0) / SLR / LR(1) / LALR

 

 

 

LR(0) 파싱이란, lookahead 단 하나도 없이 파싱하는 Shift-Reduce 형태를 의미한다.

파싱 테이블을 만들기 위해, LR(0) 아이템과 Closure를 활용해 파서 상태들 간의 상태 전이도를 만든다.

 

 

LR(0) 아이템

rhs 에 "." 심벌을 가진 생성 규칙을 의미한다.

A -> XYZ 규칙이 있다면 [A -> .XYZ] [A -> X.YZ] [A -> XY.Z] [A -> XYZ.] 는 LR(0) 아이템이다.

A -> null 이면 [A -> .] 가 LR(0) 아이템으로 추가된다.

 

 

Closure

LR(0) 아이템들을 모아놓은 집합에서 집합 크기를 크게 불리는 개념이다.

 

$$
\text{closure}(I) = I \cup \{[B \to \cdot g] \mid [A \to a \cdot Bb] \in \text{closure}(I),\ B \to g \in P\}
$$

 

"."심벌 다음이 Terminal이면 클로저를 적용해도 똑같다.

"."심벌 다음이 Non-Terminal이면 그 Non-Terminal을 정의하는 규칙들을 가져와서 "."심벌을 추가한다.

재귀적으로 가져온다. 추가한 규칙에 대해서도 계속해서 추가해 줘야 한다.

 

 

goto

goto는 closure로 정의된다. 

 

$$
\text{goto}(I, X)
= \text{closure}(\{[A \to aX \cdot b] \mid [A \to a \cdot Xb] \in I\})
$$

 

그냥 예제 따라가보면 쉽게 이해됨. 당연히 A -> null 에 대한 goto는 없다.

 

 

그냥 기계적으로 LR(0) 아이템을 구하는 방법을 알아봤는데.. 일단 아이템 구하는거는 프언개에서 했던 것 처럼 규칙을 믿고 그대로 따라가면 된다.

 

"."심벌의 의미를 생각해보자. 

a.b 는 a까지는 이미 매치됐음을 의미하고, 앞으로 b가 올 가능성이 있음을 의미한다. 즉, b는 마크심벌.

A -> a.Xb 는 a까지 parse 됐고 X를 parse 할 것으로 기대하는 상태를 의미한다.

 

이제 파서 상태가 도입된다.

LR 파서는 입력 문자열을 왼쪽부터 읽고, 지금까지 읽은 부분이 문법의 어느 위치까지 일치했는지를 상태로 저장한다.

즉, 각 상태는 지금까지 분석한 결과가 문법의 어디쯤까지 왔는가를 의미.

 

여기서 새로운 생성 규칙인 Augmented Grammar를 추가한다.

 

<기존 문법>
S → C C
C → c C | d

<추가된 문법>
S' → S
S  → C C
C  → c C | d

 

 

시작 상태는 S' -> . S 의 closure로 설정한다. 

그 다음 상태들은 여기서부터 goto를 계산해서 만들어준다. 

 

이렇게 얻어낸 모든 LR(0) 아이템을 C0라고 부른다.

 

 

 

---

 

 

 

LR(0) 파서는 lookahead가 하나도 없어 모호한 상황이 자주 발생한다. 

그래서 SLR이 도입됐다. Simple LR with 1 lookahead 파서.

 

LR(0) 파서랑 굉장히 유사하다.

Reduce도 FOLLOW가 등장한 순간에만 사용하도록 설정한다. LR(0)처럼 상태 전이 테이블을 만드는건 똑같고, Reduce 조건만 추가한 형태라고 보면 된다.

 

 

 

LR(0) 파싱 테이블과 SLR 파싱 테이블을 비교해보면 Reduce 부분이 훨씬 간단함을 확인할 수 있다.

 

 

 

 

---

 

 

 

 

 

 

이런 문법에서는 SLR 을 사용해도 Shift-Reduce Conflict를 피할 수 없다. (예시는.. 생각해보기..)

충돌을 해결하려면? 바로 다음 토큰 하나를 더 봐야 한다.

 

LR(1) 문법은 LR(1) parsing으로 parsing 할 수 있는 CFG를 의미한다.

사실 LR(0)랑 거의 비슷한데.. Item에서 하나만 추가된 형태.

 

Item 추가에 맞춰서 closure와 goto를 다시 구해주면 된다. 그냥 LR(0) 이나 SLR이나 계산하는 방식은 똑같음.. 그냥 Reduce 만 좀 다름.

예시 한 번 유도하고 이해하면 끝. 한번 해 보자.! 

 

 

---

 

 

 

LR(1) 파싱은 파서 상태 개수가 너무 많다. 

LALR 파싱은 LR에서 두 상태의 core가 똑같으면 하나의 상태로 묶어버리는 방식으로 파싱한다.

 

이론적으로는.. SLR보다 정교하고 LR(1)보다는 정교하지 않다.

상태 수는 SLR과 동일하고, LR(1)보다는 훨씬 적다.

 

LR(1)의 상태 전이도인 C1에서 만드는 방법과, LR(0)의 상태 전이도인 C0에서 만드는 방식이 있다.

LR(1)을 만들기 싫어서 LALR(1)을 만드는거다. 당연히 C0에서 만드는게 훨씬 편하다.

 

파싱 테이블에서 Shift Accept Goto는 SLR과 똑같고, Reduce만 수정하는 방식이다.

Trace 하면서 Reduce할 때, 어떤 심벌에서 Reduce 할지만 정하는거니까.. 

 

 

 

 

 

LL(1) 문법 - LL(1) 테이블에 conflict가 없음

LR(0) 문법 - LR(0) 테이블에 conflict가 없음 ... 

그냥 본인의 문법으로 만든 파싱 테이블에 conflict가 없다고 생각하면 된다. 

 

LL은 LL 끼리.. LR은 LR끼리 비교하자.

 

문법을 만드는 사람이 있고.. 컴파일러를 만드는 사람이 있다면 

문법을 제대로 만들어주면 컴파일러를 만들 때 편하다. LR(0)으로 해도 되고.. 선택지가 많아지는 것 

 

 

지금까지 한 건 Syntax Analysis.

어휘분석기는 문자열을 입력받고 토큰을 반환한다.

이제 지금까지 배운 구문분석기(파서)가 토큰을 입력받고 Parse Tree를 출력한다.

 

이 구문분석기를 만드는 방식으로 Top-Down 방식과 Bottom-Up 방식이 있다.

Top-Down 방식은 유도를 계속해서 Parse Tree를 만드는 방식인데.. 백트래킹을 없애기 위해 문법을 잘 설정해야했다.

Bottom-Up 방식은 컴퓨터 친화적이지만 어떨 때 Reduce 하고 어떨 때 Shift 할 지를 결정해야했다.