[컴파일러] LL파싱과 Follow set

LL 파싱할 때 정보가 될 수 있는 것은 First set뿐만 아니라 Follow set도 있다.

 

↓ 저번에 first set 공부할 때 follow set이 필요한 이유에 대해 그냥 주절주절 써놓은 내용 캡쳐다.

사실 아직 LL파싱에 대해 배우는 극초기 부분이라서

배운대로 이정도만 알고 있겠다.

규칙 두개 (예를 들면 A->a | b)가 있다고 하자.

input x만 보고 어떤 규칙을 택할지 결정하게 할 수 있을까?

=> first, follow가 그 정보를 준다

 

참고) 그때 쓴 내용

 

 

---

 

∨ Intro : 예제 & follow 개념

 

Let : 생성규칙

S->Aa

A->bB

 

< follow ?? >

S->Aa에서는 일단 FOLLOW(A) ∋ a임이 잘 보인다. 

 

한편 이 생성규칙으로 S=>bBa 과 같이 유도될 수 있다.

이렇게 보면 FOLLOW(B) ∋ a 임이 보인다.

 

즉 a는 FOLLOW(A)의 원소도 되지만, FOLLOW(B)의 원소도 된다는 것이 잘 보인다.

 

---

Follow set을 찾는 방법

 

 

1▶ 시작심벌은 $를 초기값으로 갖는다.

FOLLOW(S) = {$}

 

 

↓ 2, 3 : FOLLOW(B) 찾기

 

2▶ 생성 규칙의 형태가 A -> αBβ, β ≠ ε일 때, FIRST(β) - {ε} 를 FOLLOW(B)에 추가한다.

즉 FOLLOW(B) = FOLLOW(B)∪(FIRST(β) - {ε})

그렇겠지.. A->αBβ를 딱 봐도.. β의 FIRST가 B의 Follow가 될 테니까..

 

3▶ 생성 규칙의 형태가 A -> αB이거나 A -> αBβ & β = ε일 때,

즉 β => ε (β가 nullable)일 때,

A의 FOLLOW 전체를 B의 FOLLOW에 추가한다.

즉 FOLLOW(B) = FOLLOW(B)∪FOLLOW(A)

그치.. A는 나중에 αB, αBε로 유도될 수 있으니까

A의 Follow가 곧 B의 Follow겠네!

β가 nullable이니까 B뒤에 오는게 어차피 A뒤에 오는거자너

 

 

∨ 다시 말해서, 세번째 방법의 경우 Follow를 구할 때 남의 Follow로 정의한다.

따라서 앞서 본 First때와 같은 맥락으로,

Follow set 찾다가 Follow set이 업뎃되었다면 계속 영향받는 set들을 계속 업뎃해나가면 된다.

Follow가 변함 없을 때까지 진행한다..!!

한번 Follow 슥 구했다고 끝내면 안된다.

 

 

∨ 특징:

A->αB, B->αA 형태의 생성규칙을 가지고 있으면

FOLLOW(A) = FOLLOW(B) 이다. (검산용으로 활용 가능)

∵ 위에서 언급한 Follow찾기 세번째 내용에 의하여, 

  FOLLOW(A)⊆FOLLOW(B) & FOLLOW(A)⊇FOLLOW(B) 이다.

 

---

★ 문제 - FOLLOW 구해보기

 

Let:

생성규칙

E -> TE'

E' -> +TE' | ε

T -> a

First는 이렇게 주어져있다. 

FIRST(E) = {a}, FIRST(E') = {+, ε}, FIRST(T) = {a}

 

Then: Follow를 구하자

E->TE' 

FOLLOW(E) = {$} (★방법1)

FOLLOW(T) = {} ∪ (FIRST(E') - {ε}) ∪ FOLLOW(E') = {+} ∪ FOLLOW(E) = {+, $} (★방법2, 3)

FOLLOW(E') = FOLLOW(E') ∪ FOLLOW(E) = {} ∪ {$} = {$}  (★방법3)

 

더이상 변동사항에 영향받지 않는다.

 

∴ 최종은,

FOLLOW(E) = {$}

FOLLOW(E') = {$}

FOLLOW(T) = {+, $}

 

---

문제 - 각 non-terminal의 FOLLOW 구하기

 

1.

S-> aB | Bb

B-> aB | ε

<풀이>

초기 : FOLLOW(S) = FOLLOW(B) = {}

FOLLOW(S) = {$}

FOLLOW(B) = (FOLLOW(B) ∪ FOLLOW(S)) ∪ {b}

                    =  {$, b}

---

2.

S-> (S)S|ε

<풀이>

초기 : FOLLOW(S) = {}

FOLLOW(S) = {$, )}

FOLLOW(S) = FOLLOW(S) ∪ FOLLOW(S) = {$, )}

 

---

3.

E -> a | L

L -> (Q)

Q -> LQ'

Q' -> ,Q | ε

 

<풀이>

초기 : FOLLOW(E) = FOLLOW(L) = FOLLOW(Q) = FOLLOW(Q') = {}

FOLLOW(E) = {$}

FOLLOW(L) = (FIRST(Q') - {ε}) ∪ FOLLOW(Q)

FOLLOW(Q) = { ) } ∪ FOLLOW(Q') = { ) }  ◆┐

FOLLOW(Q') = FOLLOW(Q) = { ) }             ◆┘더보기 참고!

∨ 특징:

A->αB, B->αA 형태의 생성규칙을 가지고 있으면

FOLLOW(A) = FOLLOW(B) 이다. (검산용으로 활용 가능)

∵ 위에서 언급한 Follow찾기 세번째 내용에 의하여, 

  FOLLOW(A)⊆FOLLOW(B) & FOLLOW(A)⊇FOLLOW(B) 이다.

 

갱신 :

FOLLOW(L) =  (FIRST(Q') - {ε}) ∪ FOLLOW(Q) = { ',' , ) }

 

더이상 변동사항은 없다.

그럼 답이

FOLLOW(E) = {$}

FOLLOW(Q) = { ) }

FOLLOW(Q') = { ) }

FOLLOW(L) = {',' , ) } 

 

※ 주의해야 할 점

=> FOLLOW(L)을 구할 때!

규칙 Q -> LQ'를 보면 [Q'가 nullable이 아닐 때] FOLLOW(L)은 (FIRST(Q') - {ε})를 포함한다

여기서 규칙 Q' -> ,Q | ε를 보면, Q'는 nullable이다. 

그럼 Q -> LQ'에서 [Q'가 nullable일 때] FOLLOW(L)은 FOLLOW(Q)를 포함한다.

 

즉 간단한 내용이다. 

 Q -> LQ'에서 FOLLOW(L)을 찾을 때,

Q'가 nullable인가를 꼭 생각해보자는 거였다.

 

---

위 주의점을 유의하고 하나 더 풀어보자

E -> TE'

E' -> +TE' | ε

T -> FT'

T' -> *FT' | ε

F -> (E)

F -> id

 

별거 없구 저기 저 ε의 경우를 주의하자는 거다.

 

FOLLOW(E) = { $, ) }

FOLLOW(E') = FOLLOW(E) = { $, ) }

FOLLOW(T) = FIRST(E') <= null  주의!

                     = {+} ∪ FOLLOW(E')  <= E'가 null아닌경우와 null인경우의 합집합

                     = {+} ∪ { $, ) } = { +, $, ) }

FOLLOW(T') = FOLLOW(T) = { +, $, ) }

FOLLOW(F) = FIRST(T') <= null 주의!

                     = { * } ∪ FOLLOW(T) <= T'가 null아닌경우와 null인경우의 합집합

                     = { *, +, $, ) } 

 

더이상 변동사항이 없다. 끝!

 

---