[컴파일러] FOLLOW(𝞪)의 개념과 예제

FIRST(𝞪)와 FOLLOW(𝞪)는 모두 결정적 구문 분석을 하기 위한 구문임을 판단할 때 사용되는 개념이다. 결정적 구문 분석으로 비결정적 구문 분석보다 더 효율적으로 구문 분석이 가능하기에 주로 결정적 구문 분석을 사용한다. 결정적 구문 분석 방식 중 하나인 LL 파싱이 존재하며, FIRST(𝞪)와 FOLLOW(𝞪)에 대한 개념이 LL 파싱을 수행할 수 있는 구문임을 파악하기 위한 조건(LL condition)으로 나오게 된다. 그 중에서 FOLLOW(𝞪)에 대해 자세히 알아보자

 

FIRST(𝞪)와 LL 파싱에 대한 자세한 내용은 아래의 포스팅을 참고해주세요!

[컴파일러] FIRST(𝞪)의 개념과 예제

 

---

1. FOLLOW(𝞪)의 개념

FOLLOW(X)를 간단하게 말하자면, 이는 X 다음에 나오는  터미널 심볼의 집합이다. FOLLOW(X)를 구하는 방법에 대해 자세히 알아보자

X는 FIRST(X)와 다르게 논터미널 심볼일 경우에만 FOLLOW 개념을 다룬다.

 

X가 논터미널 심볼이기 때문에, X에 대한 생성 규칙이 존재하며 각각의 생성 규칙과 심볼의 종류에 따라 FOLLOW(X)를 구할 수 있다.

심볼의 종류에 따라    

(a) X가 시작 심볼인 경우에는 초기 값으로 입력 스트링의 끝을 표시하는 마커 심볼($)을 가진다.
(b) 이외의 심볼인 경우 초기 값으로 공집합(φ)을 가진다.

 

생성 규칙에 따라 

생성 규칙의 형태에 따라 X 다음에 나오는 터미널 심볼이 달라진다. ε-생성 규칙으로 인해 ε이 나타나기에 FOLLOW(X)를 가지는데 조금 복잡해진다. 지난 FIRST(X)에서는 생성규칙의 우변(LFS)에서 X를 찾아 판단하였지만, FOLLOW(X)에서는 생성 규칙의 좌변(RFS)에서 X를 찾아 판단하여야 한다. 이제 FOLLOW(X)를 구해보자.

 

1. A→ aXb (b ≠ ε) 형태 

A→ aXb 형태는 간단한 형태로 b가 ε이 아닌 터미널 심볼이 나오는 경우이다. 식을 통해서 X 다음에 나오는 터미널 심볼은 간단히 b에서 첫번째로 유도되는 터미널 심볼, FIRST(b)가 된다. 이때, ε이 아닌 터미널 심볼임을 전제로 하였기에 {FIRST(b) - ε}를 추가해주어야 한다. 또한, 주목할 것은 FIRST와 다르게 X가 어떻게 유도되는지 표현한 생성 규칙(X→ ...)이 아니라 X가 생성 규칙의 우변(RFS)에 존재하는 생성 규칙을 보고 판단한다는 점이다.

FOLLOW(X) = FOLLOW(X) ∪ {FIRST(b) -  ε}

 

2. A→ aX, A→ aXb (b ⇒* ε)형태

A→ aX와 A→ aXb (b ⇒* ε) 형태는 X 뒤에 ε이 올 수 있는 경우이다. X 다음에 ε이 올 경우, X 다음에 올 터미널 심볼은 생성 규칙의 좌변(LFS)인 논터미널 심볼 A의 다음에 올 터미널 심볼과 같다. 즉, ε이 유도될 경우 FOLLOW(X)는 FOLLOW(A)와 같으므로 FOLLOW(X)는 FOLLOW(A)를 포함한다. 

FOLLOW(X) = FOLLOW(X) ∪ FOLLOW(A)

 

 

2. FOLLOW(𝞪)의 예제

주어진 생성 규칙에서 모든 심볼에 대해 FOLLOW를 구해보자.

 

          E → TE'

          E' → +TE' | ε

          T → FT'

          T'→ *FT' | ε

          F → (E) | id  

---

먼저, 심볼의 종류에 따라 초기 값을 계산하면 다음과 같다.

• 시작 심볼 : FOLLOW(E) = {$}
• 이외의 심볼 : FOLLOW(E') = {φ}, FOLLOW(T) = {φ}, FOLLOW(T') = {φ}, FOLLOW(F) = {φ}

 

다음으로, 각 심볼에 따라 생성 규칙을 바탕으로 FOLLOW를 계산해보자.

 

   E는 생성 규칙 F→ (E)에서 A→ aXb (b ≠ ε) 형태로 나타난다. 

• F→ (E) ⇒ FOLLOW(E) = FOLLOW(E) ∪ { FIRST()) - ε }

  그러므로, FOLLOW(E) = { ), $ }이다.

 

   E'는 생성 규칙 E → TE'과 E' → +TE'에서 모두 A→ aX 형태로 나타난다. 

• E → TE' ⇒ FOLLOW(E') = FOLLOW(E') ∪ FOLLOW(E)
• E' → +TE' ⇒ FOLLOW(E') = FOLLOW(E') ∪ FOLLOW(E')

  그러므로, FOLLOW(E') = { ), $ }이다.

 

   T는 생성 규칙 E → TE'과 E' → +TE'에서  A→ aXb (b ≠ ε)과 A→ aXb (b ⇒* ε) 형태로 나타난다. 

• E → TE' ⇒ FOLLOW(T) = FOLLOW(T) ∪ { FIRST(E') - ε } ∪ FOLLOW(E) 
• E' → +TE' ⇒ FOLLOW(T) = FOLLOW(T) ∪ { FIRST(E') - ε } ∪ FOLLOW(E)

  그러므로, FOLLOW(T) = { +, ), $ }이다.

 

   T'는 생성 규칙 T → FT'과 T'→ *FT'에서  A→ aX 형태로 나타난다. 

• T → FT' ⇒ FOLLOW(T') = FOLLOW(T') ∪ FOLLOW(T) 
• T'→ *FT' ⇒ FOLLOW(T') = FOLLOW(T') ∪ FOLLOW(T')

  그러므로, FOLLOW(T') = { +, ), $ }이다.

 

   F는 생성 규칙 T → FT'과 T'→ *FT'에서  A→ aXb (b ≠ ε)과 A→ aXb (b ⇒* ε) 형태로 나타난다. 

• T → FT' ⇒ FOLLOW(F) = FOLLOW(F) ∪ { FIRST(T') - ε }  ∪  FOLLOW(T)
• T'→ *FT' ⇒ FOLLOW(F) = FOLLOW(F) ∪ { FIRST(T') - ε }  ∪  FOLLOW(T')

  그러므로, FOLLOW(T') = { *, +, ), $ }이다.