왜 필요한가?
위와 같은 생성 규칙이 있다고 하자.
우리는 FIRST라는 것을 알기 때문에 FIRST(S) = {b, c}이고 FIRST(A) = { epsilon }이라는 정보가 있다.
이때 입력 문자열로 "b"가 들어왔다고 하면,
1. FIRST(S) = {b, c}에서 b가 있으므로 $S \to Ab$ 를 선택한다.
2. $A$는 무조건 $\epsilon$ 으로 유도된다.
위와 같이 당연하게(결정적으로) "b"를 유도시킬 수 있다.
이번엔 위와 같은 생성 규칙이 있다고 하자.
이때 S, A의 FIRST는 아래와 같다.
FIRST(S) = {a, b}
FIRST(A) = {a, epsilon}
이번에도 입력 문자열로 "b"가 들어왔다고 하자.
1. FIRST(S) = {a, b}에서 b가 있으므로 $S \to Ab$ 를 선택한다.
2. A를 유도할 차례인데, 이때 FIRST(A)를 보면 {a, null} 이다.
S를 Ab로 유도할때까지만 해도, S의 FIRST로 'b'가 올 수 있음을 알았다.
그러나 막상 A를 특정 생성규칙을 통해 유도하려고 보니
A의 FIRST에는 A의 첫번째로a또는 null이 온다는 정보만 존재하고, b로 유도할 수 있다는 정보는 전혀 없다.
모든 non-terminal들의 FIRST만으로는 매번 결정적으로 선택하기 쉽지 않다.
그럼 어떻게 더 결정적으로 생성규칙을 선택할 수 있을까?
위의 두번째 예시를 봤을때, A다음에 b가 온다는 것만 알았더라면 $A \to \epsilon$ 를 고를 수 있었을것이다.
FOLLOW
정말 단순하게도 특정 non-terminal 바로 오른쪽에 어떤 terminal이 오는 지 알고자 하는 것이 FOLLOW다.
FOLLOW를 구하기 위한 세 가지 규칙에 대해 알아보자.
첫번째 규칙. 시작 non-terminal의 경우
시작 non-terminal의 경우, FOLLOW에 문장의 마지막을 의미하는 $를 추가한다.
$는 유도된 문자열의 마지막을 의미한다.
위 그림과 같이 S로부터 생성규칙이 선택되어 어떤 문자열로 유도가 되었다고 하자.
유도가 마무리되었기 때문에 문자열의 맨 오른쪽에는 $가 붙게 된다.
그래서 위 그림에서 S의 오른쪽에 $가 존재하는 것이다.
따라서 시작 non-terminal의 FOLLOW는 $로 초기화한다.
FOLLOW(S) = {$}
두번째 규칙. Non-terminal 오른쪽에 terminal 또는 nonterminal이 오는 경우
구하려는 non-terminal이 포함된 생성규칙들을 봤을때,
해당 non-terminal의 오른쪽에 terminal 또는 non-terminal이 존재한다면
오른쪽에 있는 terminal 또는 non-terminal의 FIRST에서 $\epsilon$을 제외한 것들을 FOLLOW에 추가한다.
위 생성규칙에서 A의 FOLLOW를 구해보자.
단순하게 A의 오른쪽에는 무엇이 올 수 있을까?
생성규칙을 봐도, 그래프를 봐도 A 다음으로는 b밖에 올수가 없다.
S의 FOLLOW는?
첫번째 규칙에 의해 S다음으로 $가 온다.
위 생성규칙에서 A의 FOLLOW를 구해보자.
A 다음에는 B가 오고있는데,
1. B는 a가 될 수도 있다.
2. B는 $\epsilon$이 될 수도 있다.
3. B가 가장 마지막에 유도되므로, B가 $\epsilon$이 된다면, 자연스레 $가 A다음에 올 수도 있다!
그래프로 보면 이해가 조금 더 쉬워진다.
따라서 FOLLOW(A)는 {a, $\epsilon$, $} 가 될 것이다.
일단 $\$$가 오는 경우는 생각하지 말고, a와 $\epsilon$이 오는 경우만 생각해보자.
A다음에 B라는 non-terminal이 오면, B로 유도할 수 있는 것들 중 가장 처음으로 나오는 terminal들의 집합이 A 다음에 올 수 있는 terminal들이 된다.
이때 B로 유도할 수 있는 것들 중, 가장 처음으로 나오는 terminal들의 집합은 B의 FIRST를 의미한다.
따라서 FIRST(B)가 FOLLOW(A)에 추가됨을 알 수 있다.
근데 FIRST(B)에서 $\epsilon$은 빼고 FOLLOW(A)에 추가하는 것이 규칙이 된다.
?? null 왜 빼?
A다음에 null이 존재한다고 해서, 최종적으로 A의 오른쪽에 아무것도 없을까?
아니다. 시작 non-terminal도 오른쪽에 $를 갖는다.
결국 FOLLOW로 null 포함될 수 없는 이유는
어떤 non-terminal이든 오른쪽에 무조건 $아니면 다른 terminal이 존재할것이기 때문이다.
따라서 최종적인 FOLLOW(A)는 {a, $} 가 된다.
결론적으로 A다음에 오는 것이 terminal이든 non-terminal이든 null만 아니라면!
1. FIRST를 구하고
2. 구해진 FIRST에서 $\epsilon$을 뺀것을
3. FOLLOW에 추가하면 된다.
즉, 생성 규칙의 형태가 $S \to \alpha A \beta$ 일때($\alpha, \ \beta$는 terminal일수도 있고, non-terminal일수도 있다.)
라고 할 수 있다.
세번째 규칙. Non-terminal다음에 아무것도 안오거나, nullable한 non-terminal이 오는 경우
FOLLOW를 구하려는 non-terminal이 포함된 생성규칙들을 봤을때,
해당 non-terminal의 오른쪽에 아무것도 안오거나, nullable한 non-terminal이 오는 경우,
"해당 non-terminal을 생성하는 non-terminal"의 FOLLOW를 FOLLOW에 추가한다.
쉽게 말하자면, 다음에 오는 terminal을 어떻게든 찾겠다는 것이다.
위의 생성규칙에서 B의 FOLLOW를 구한다고 했을때, 생성규칙만 봐서는 B의 오른쪽에 아무것도 없다는 것을 확인할 수 있다.
그러나 그래프로 확인해보면, B의 오른쪽에는 $가 있는데 이는 S의 FOLLOW와 같다.(첫번째 규칙에 의해)
다른 예시도 보자.
위의 생성규칙들을 보고, B의 FOLLOW를 구해보자.
이전 예시와 같이 B 다음에는 아무것도 없다.
그러나, 하나 타고 올라가서 B를 유도하는 A의 오른쪽에는 C가 존재한다.
결과적으로 B의 FOLLOW에는 A의 FOLLOW가 추가된다.
이제 A의 FOLLOW를 구해보자.
A의 다음에는 C가 오는데, 두번째 규칙에 의해 우선 A의 FOLLOW에 a가 추가(FIRST(C) - {$\epsilon$})된다.
C는 nullable하므로 C가 $\epsilon$이 되버리면, A의 다음에는 $가 오는 것을 볼 수 있다.
이는 S의 FOLLOW와 같다.
다음에 오는 terminal을 어떻게든 찾게된다.
이는 nullable한 non-terminal이 오른쪽에 오는 경우가 위 예시의 경우이다.
C가 $\epsilon$ 이 되면, $S \to AC$에서 $S \to A$로 변하는 것과 같게 된다.
결과적으로 A를 유도하는 S, S의 FOLLOW가 A의 FOLLOW에 추가된다.
위의 두번째 규칙을 설명할때, 두번째 예시에서 3번으로 소개된 부분이 바로 세번째 규칙에 의한 것임을 알 수 있다.
활용
각 non-terminal들의 FOLLOW를 구해보자.
먼저 모든 non-terminal들의 FOLLOW는 공집합으로 초기화하고 시작한다는 것을 꼭 알아두자.
E는 시작 non-terminal이므로 첫번째 규칙에 의해 $를 E의 FOLLOW에 추가한다.
그 뒤로 E가 생성규칙에 나타나는 일은 없으므로 E의 FOLLOW는 {$}가 된다.
L은
1. $E \to L$
2. $Q \to LQ'$
두곳에 나온다.
우선 두번째 규칙에 의해 $Q \to LQ'$ 에서 $FIRST(Q') - {\epsilon}$을 Q의 FOLLOW에 추가한다.
$E \to L$에서 한번 $Q \to LQ'$에서 Q'이 nullable하므로 한번, 총 두번 세번째 규칙을 적용시켜야한다.
따라서 L의 FOLLOW에 E의 FOLLOW와 Q의 FOLLOW를 추가해야한다.
E의 FOLLOW는 {$} 이고, Q의 FOLLOW는 현재 {} 이므로 L의 FOLLOW는 {$, +} 가 된다.
Q는
1. $L \to (Q)$
2. $Q' \to +Q$
두곳에서 나온다.
두번째 규칙에 의해 $L \to (Q)$에서 ")"를 Q의 FOLLOW에 추가한다.
$Q' \to +Q$에서는 세번째 규칙을 적용시켜야하므로 Q'의 FOLLOW를 Q에 추가해야한다.
아직 Q'의 FOLLOW는 현재 {} 이므로 Q의 FOLLOW는 {")"} 이다.
Q' 은
$Q \to LQ'$ 에서 나오고, 세번째 규칙을 적용시켜야하므로 Q의 FOLLOW를 Q'에 추가시킨다.
따라서 Q'의 FOLLOW는 {")"} 가 된다.
L의 FOLLOW 구할때는 Q의 FOLLOW가 공집합이었지만, 이후에 업데이트 됐으므로 L의 FOLLOW도 다시 업데이트 해줘야한다.
L의 FOLLOW는 {$, +} 였고, Q의 FOLLOW가 {")'}로 업데이트 됐으므로 이를 추가하면, {$, +, ")"} 가 된다.
Q의 FOLLOW를 구할때도 Q'의 FOLLOW가 공집합이었지만, 이후에 Q'이 업데이트 됐었다.
그러나 Q의 FOLLOW에 이미 ")"가 추가됐으므로 업데이트된 Q'의 FOLLOW를 추가해봐야 달라질게 없다.
따라서 최종적으로 구해진 FOLLOW는 다음과 같다.
