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

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

 

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

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

 

---

1. FIRST(𝞪)의 개념

FIRST(X)를 간단하게 말하자면, 이는 X로 처음 유도 가능한 터미널 심볼의 집합이다. FIRST(X)를 구하는 방법에 대해 자세히 알아보자

X는 모든 심볼 집합의 원소가 올 수 있으므로 X는 경우에 따라 터미널 심볼과 논터미널 심볼로 나누어진다.

터미널 심볼 (Terminal Symbol)

: X가 터미널 심볼인 경우, FIRST(X)는 X 자체가 처음 유도 가능한 터미널 심볼이기에 FIRST(X)는 X 자기 자신이 된다.

(a) X가 터미널 심볼이라면, FIRST(X) = {X}로 자기 자신이 된다 ⇒ FIRST(X) = {X}

 

논터미널 심볼 (Non-Terminal Symbol)

 X가 논터미널 심볼인 경우, X에 대한 생성 규칙이 존재하며 생성 규칙의 형태에 따라 다르게 FIRST(X)를 구할 수 있다.

(a) X → a𝛼 형태의 생성 규칙이 존재하면, a는 FIRST(X)에 포함된다 ⇒ FIRST(X) = FIRST(X) ∪ {a}
(b) X → ε 형태의 생성 규칙이 존재하면, ε는 FIRST(X)에 포함된다 ⇒ FIRST(X) = FIRST(X) ∪ {ε}
(c)  X → ABCD...Z 형태의 생성 규칙이 존재할 때
       #1.  AB...F ⇒* ε 이면, ε을 제외한 A부터 G까지의 FIRST가 모두 FIRST(X)에 포함된다
              ⇒ FIRST(X) = FIRST(X) ∪ (FIRST(A부터 F)의 합집합 - {ε}) ∪ FIRST(G)
       #2. AB...Z ⇒* ε 이면, ε는 FIRST(X)에 포함된다
              ⇒ FIRST(X) = FIRST(X) ∪ {ε}

 

먼저, (a)의 X → a𝛼 형태는 X의 생성 규칙에서 가장 처음 나오는 심볼이 터미널 심볼 a인 경우이다. FIRST(X)의 정의에 따라 X로 처음 유도 가능한 터미널 심볼은 자연스레 a가 되므로 a는 FIRST(X)에 포함된다.

 

다음으로, (b)의 X → ε 형태는 X가 ε-생성 규칙을 가지는 경우이다. 이 경우에도 위와 비슷한 방식으로 ε는 FIRST(X)에 포함된다.

 

마지막으로, (c)의 X → ABCD...Z 형태는 X의 생성 규칙이 여러 논터미널 심볼로 이루어져 있는 경우이다. (c)의 1과 2 모두 X가 ε으로 유도되는 경우를 말하지만, 어느 논터미널 심볼에서 ε이 유도되는지에 따라 나뉜다.

• (c)-1번의 경우, X → ABCD...Z 중에서 중간에 존재하는 논터미널 심볼인 F에서 ε이 유도된다. X → ABCD...F에서 ε이 유도될 수 있으므로 FIRST(X)는 논터미널 심볼 A, B, ... F에서 나올 수 있으며 FIRST(A부터 F)의 합집합이 포함된다. 이때, 합집합에서 ε을 제외해주어야 하는 이유는 중간 논터미널 심볼 과정 까지 ε이 나온 것이 나머지 뒤에 있는 논터미널 심볼에서 ε이 나온다는 보장이 되지 않기 때문이다. 또한, A부터 F까지의 논터미널 심볼이 ε이 된다면 처음 유도 가능한 터미널 심볼은 F 다음의 논터미널 심볼인 G에서 나오기 때문에 FIRST(G)도 포함하게 된다.
• (c)-2번의 경우, X → ABCD...Z로 모든 논터미널 심볼인 Z까지 했을 때 ε이 유도되는 경우이다. (c)-1번에서는 ε이 나온다는 보장이 없어서 제외해주었지만,  AB...Z ⇒* ε 임이 성립하기 때문에 이제서야 ε을 FIRST(X)에 포함해주는 것이다.

여기서 터미널 심볼과 논터미널 심볼에 대해 FIRST(X)를 구할 때 터미널 심볼은 FIRST(X) 자기 자신으로 정의되는 반면에 논터미널 심볼은 FIRST(X)에 포함된다는 형태로 정의되는 것을 볼 수 있다. 이는 심볼의 종류에 따라 X가 유도될 수 있는 터미널 심볼의 개수에 차이가 있기 때문이다. 터미널 심볼은 오직 하나의 터미널 심볼로 X가 유도된다. 하지만, 논터미널 심볼은 하나의 논터미널 심볼에도 여러 개의 생성 규칙이 존재할 수 있으므로 여러 개의 터미널 심볼로 유도될 수 있으며 합집합으로 확장되며 FIRST(X)를 구할 수 있다.

2. FIRST(𝞪)의 예제

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

 

          S → aRTb | bRR

          R → cRd | ε

          T → RS | TaT

---

  FIRST(S)는 논터미널 심볼 S와 2개의 생성 규칙으로 S → aRTb, S → bRR로 (a)의 형태로 이루어져 있다.

• S → aRTb ⇒ FIRST(S) = FIRST(S) ∪ {a}
• S → bRR  ⇒ FIRST(S) = FIRST(S) ∪ {b}

  그러므로, FIRST(S) = {a, b}이다.

 

  FIRST(R)는 논터미널 심볼 R와 2개의 생성 규칙으로 R → cRd, R → ε로 각각 (a)와 (b)의 형태로 이루어져 있다.

• R → cRd ⇒ FIRST(R) = FIRST(R) ∪ {c}
• R → ε  ⇒ FIRST(R) = FIRST(R) ∪ {ε}

  그러므로, FIRST(R) = {c, ε}이다.

 

 FIRST(T)는 논터미널 심볼 T와 2개의 생성 규칙으로 T → RS, T → TaT로 각각 다음과 같은 형태로 이루어져 있다.

 T → RS는 모두 논터미널 심볼로 이루어져 있어 (c)에 해당하게 되고 R → ε를 가져 (c)-1에 해당한다.

 T → TaT는 재귀적으로 자기 자신을 호출하고 있으므로 FIRST(T)와 동일하다.

• T → RS ⇒ FIRST(T) = FIRST(T) ∪ (FIRST(R) - {ε}) ∪ FIRST(S) = ({c, ε} - {ε}) ∪ {a, b}= {a, b, c}
• T → TaT  ⇒ FIRST(T) = FIRST(T)

  그러므로, FIRST(T) = {a, b, c}이다.