목차
📁 FIRST의 한계
LL파싱은 결정적 파싱이 되는 문법을 선별하여, 각 입력 문자당 적용될 생성규칙을 미리 뽑아두고 시작한다.
이를 위해 규칙으로부터 여러 정보들이 필요한데, FIRST 집합만으로는 한계가 있다.
A -> XXX과 같은 생성규칙이 있다고 할 때, Nonterminal A가 Nullable한 경우 FIRST만 가지고 생성규칙을 결정적으로 선택할 수 없다는 문제가 생긴다.
이때 FIRST 말고도, A의 다음에 나오는 심벌의 집합을 수집할 필요가 생기고 이를 FOLLOW 집합이라고 한다.
📁 FOLLOW
FOLLOW(A)란 시작 심벌로부터 유도될 수 있는 모든 문장 형태에서 A 다음에 나오는 terminal 심벌의 집합을 말한다.
이때 $는 입력 스트링의 끝을 표기하는 마커 심벌이다.
FIRST를 찾을 때는 Nonterminal이 LHS에 있는 경우를 찾았는데,
FOLLOW는 Nonterminal이 RHS에 있는 경우를 찾아야 한다.
📁 FOLLOW를 계산하는 방법
정의 1. 시작 심벌의 FOLLOW는 {$}라는 초기값을 갖는다.
정의 2. 생성 규칙의 형태가 A -> αBβ, β != ε일 때, FIRST(β)에서 ε을 제외한 terminal 심벌을 FOLLOW(B)에 추가한다.
이때 β != ε은 αBβ의 형태에서 β자리에 Nonterminal이나 terminal이 꼭 있어야한다는 뜻으로, β가 null로 전개될 수 있거나 β가 nullable한 것과는 별개이다.
정의 3. A -> αB이거나, A -> αBβ에서 FIRST(β)에 ε이 속하는 경우, 즉 β이 nullable한 경우 FOLLOW(A)를 FOLLOW(B)에 추가한다.
A -> αBβ에서 β이 nullable한 경우, 임의의 문장 형태에서 A 다음에 나올 수 있는 심벌은 모두 B 다음에 나올 수 있기 때문에 이와 같이 처리한다.
추가로, A -> αB, B -> αB와 같은 형태의 생성규칙을 갖고 있으면, FOLLOW 속성으로 인해 FOLLOW(A) = FOLLOW(B)가 된다.
예를 들어 아래 문법에 대해 FOLLOW(E), FOLLOW(E'), FOLLOW(T)를 구해보자.
E → TE’
E’ →+TE’ | ε
T → a
먼저 FIRST부터 구한다.
FOLLOW(E), FOLLOW(E'), FOLLOW(T) 모두 {}, 공집합으로 초기화한 후,
정의 1에 의해 FOLLOW(E)를 {$} 초기값으로 세팅한다.
다음으로 정의 2의 A -> αBβ, β != ε에 해당하는 규칙은 E → TE’ 이므로 FOLLOW(T)를 처리한다.
이후 정의 3에 해당되는 A -> αB이거나, A -> αBβ에서 FIRST(β)에 ε이 속하는 경우의 규칙은 E → TE’, E’ →+TE’이므로 FOLLOW(E')와 FOLLOW(T)를 처리한다.
위에서 FOLLOW(E') = {$}, FOLLOW(T) = {+. $)라고 도출된 결과를 가지고 정의 3 과정을 다시 반복한다.
다시 반복해도 결과가 변하지 않으므로, 이 결과가 최종이 된다.
