[컴파일러] 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로 정의한다.
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인경우의 합집합
= { *, +, $, ) }
더이상 변동사항이 없다. 끝!