FIRST와 FOLLOW 쓰는 이유 및 원리 - Compiler Design

 

FIRST를 쓰는 이유

 

S -> cAd 

A -> bc | a 

 

input : cad  가 있을 떄 c를 읽고 다음 a를 읽을 때 논터미널 A는 bc또는 a로 구분된다. 하지만 이미 A에 대한 FISRT를 구해놨기 때문에 A의 FIRST인 a를 알고 있기때문에 bc로 한번 안빠지고 a로 바로 determine할 수 있다. 

 

체킹 시점을 줄일 수 있다.  즉, 특정 Non Terminal Symbol이 어떤 Production을 생성시킬 수 있는지 알 수 있다면 BackTracking없이 바로 갈 수 있다. 

 

Follow가 필요한 이유 일단 아래 생성규칙을보자.

 

S ->aAb 

A -> a | <epsilon> 

 

input : ab 가 있을 때 S -> aAb로 a를 일치시킨다. => (aAb, ab) => (Ab, b) 여기서 Non Terminal Symbol 'A'뒤에는 b가 따른다. 이는 input 값과 일치한다. 그럼 A를 없앨 방법을 모색하기위해 A는 <epsilon>을 택하게 된다. 이것이 Follow가 필요한 이유이다. 

 

FOLLOW를 살짝 정리하면 next input을 보고 하나의 생성규칙에서 NonTerminal다음에 따라오는 Symbol을 보고 해당 Non Terminal을 어떻게 처리해야하는지 알 수 있다. 

 

---

 

여기서 헷갈리는 FOLLOW의 규칙의 일부이다. 

 

1. 모든 Non Terminal의 FOLLOW에는 $(End Marker)를 붙여야한다. 

• 이유 

처음 Start Symbol의 FOLLOW에는 $가 붙는데 나머지에도 붙는 이유는 나머지 NonTerminal들이 Start Symbol로 부터 유도 되기때문에 FOLLOW(Start Symbol)의 값을 가지고 가는 것같음

 

2. 구하려는 Non Terminal의 뒤에 Terminal이 온다면 이 Terminal은 FOLLOW에 추가한다. 

 

 

3. 구하는 Non Terminal다음에 아무것도 오지 않는다면 LHS의 Non Terminal의 FOLLOW를 찾아서 넣는다. 

• 이유 

 

일단 생성규칙 E -> TE^ , T -> FT^ 를 보자 

여기서 FOLLOW(T^)를 구하고 싶다. FOLLOW는 해당 Non Terminal의 다음 값을 구하는건데 다음 값이 없다. 

 

그럼 T^ 이 있는 생성규칙의 LHS Non Terminal이 있는곳에 대입하면 된다. 

 

그럼 E -> FT^E^가 된다. 그럼 T^ 다음에는 E^이 나오게 되고 E^에대한 FIRST(E^)를 구하면된다. 

여기서 왜 FIRST(E^)냐면 E^가 Terminal로 대치되었을 때 어떤 값으로 대치될것인가 예측해야하기 떄문이다. 

 

 

4.  구하려는 Non Terminal 다음에 Non Terminal이 나온다면이 Non Terminal의 First를 구하면된다. 만약 다음 Non Terminal의 First가 <epsilon>이라면 이 3번 규칙을 다시 적용하면 된다. 

 

NonTerminal이 하위집합일수록 상위 NonTerminal에 부분 포함?

---

Predictable Parse Table을 구성할때 해당 Non Terminal이 FIRST를 구해서 Table에 작성한다. 

어떨때 보면 FIRST(Non-Terminal)을 구했는데 <epsilon>이 나온다면 이 Non Terminal이 <epsilon>유도 된다는 뜻이다. 

즉, 이 Non Terminal은 사라진다는 뜻인데 그럼 이 Non Terminal이 사라지고 난 다음 Next Symbol을 구해야하니까 

FOLLOW(Non-Terminal)을 구해서 Parsing Table에 채워넣는 것이다.