[Compiler] Thompson`s Construction Algorithm (RE -> NFA)

지난 포스트를 토대로 Nondeterministic FA와 Deterministic FA를 구별해보았다. 간단히 요약해보면 경로를 찾는데 있어서 가능성 주목한 방식이 NFA가 될 것이고, 진짜 정답을 찾는 방식이 DFA가 될 것이다. 그래서 저번에 계층적으로도 표현했었지만 우리가 Lexical Analysis를 하는 궁극적인 목적은 Regular Expression 식을 NFA를 거쳐서 아주 간략한 DFA를 거치는 것이 되겠다.

 그럼 먼저 해야 되는 작업이 RE를 NFA 형식으로 바꾸는 방식이 되는데 여기에는 Thompson`s Construction Algorithm (TCA) 라는 방법으로 정의되어 있는게 있다. 이 방법은 Regular Expression을 가장 기본적인 단위로 쪼개어 NFA에서 정의한 방식대로 합치는 것이다. 여기서 설명하는 가장 기본적인 단위는 다음과 같다.

즉 시작점과 출발점이 있을때 RE에 포함되어 있는 해당 요소를 위와 같이 표현하는 것이다. 다르게 말하면 처음 상태에서 포함된 요소를 선택하면 다음 state로 넘어간다 정도로 이해하면 좋을 것 같다. 그러면 아래와 같이 s의 NFA인 N(s)와 t의 NFA인 N(t)가 있다고 가정을 해보자.

그럼 우리가 찾고자 하는 것은 s와 t가 결합된 형태를 어떻게 찾느냐는 것이다. 우리가 찾는 문자는 s와 t가 concatenate된 형태 일 수도 있고, 혹은 Union 된 형태일 수도 있다. 

첫번째로 Union 혹은 Alternation된 형태를 찾고자 할때는 TCA로 표현하면 다음과 같다. 

원래 찾고자 하는 문자 r이 s|t의 형태라면 현재 state에서 다음 state로 넘어갈 때 N(s)나 N(t)로만 가면 된다. 그 대신 s나 t가 어떤 문자로 구성되어 있는 집합이 아니기 때문에 임의로 Ɛ - transition을 이용해서 연결해준다. 모든 Symbol의 subset으로는 항상 Ɛ 이 들어가 있기 때문이다. 반면 Concatenate은 다음과 같이 표현해준다.

i가 f로 가기 위해서는 반드시 N(s)와 N(f)를 거쳐야 된다는 의미인 것이다. 물론 두 NFA의 연속된 상태이므로 이에 따른 state 전개도 다시 따져볼 수 있다. 즉 N(s)의 final State는 N(t)의 initial State라고 할 수 있고 f는 N(t)의 final state라고도 바꿔 말할 수 있다. 

 다음은 Kleene Closure이다. 

자 이건 잘 따져보자. Kleene Closure 자체는 같은 요소가 반복된 형태이다. positive closure가 아닌 이상 당연히 Ɛ 도 포함된 상태이며, N(s)에서도 같은 문자가 반복된 형태는 위와 같이 Ɛ transition이 되돌아가는 형태를 띄게 될 것이다. 그럼 예를 한번 들어보겠다. 

위와 같이 N(a)와 N(b)가 주어져 있는 상태이다. 여기서 TCA를 사용해서 (a|b)*abb의 NFA 형식을 구하는 것이 목적이라고 가정해본다. 

그럼 우리가 이 RE 형태에서 발견할 수 있는 기본적인 요소들은 뭐가 있을까? 뻔히 보이겠지만 union도 있고 kleene closure도 있고, abb라는 concatenate 형태도 들어 있다. 그럼 그 기본 요소들을 TCA로 표현할 수 있다. 맨처음은 a|b의 형태이다. 앞에서 언급한 것처럼 어느 state를 통과해서든지 final state로 transition되는 형태이기 때문에  다음과 같이 표현할 수 있다. 

initial state가 1이고 final state가 6인 상태는 위와 같이 표현할 수 있다. 이제 다음 형태는 Kleene closure의 형태인데 위의 형태는 단순히 a|b를 구성하는 요소 중 하나이므로 새로 initial state와 final state를 삽입해서 표현해준다. 

개인적으로 Kleene closure는 Ɛ - transition만 잘 표현해주면 구하기 쉽다고 생각한다. 여기서 이제 abb와의 concatenate를 구하면 된다. 그런데 앞에서 설명했다시피 concatenate은 연속된 집합의 나열의 형식이며 abb 자체는 이미 path가 정해져 있다고 볼 수 있다. 그래서 union이나 concatenate를 고려할 필요가 없는 것이다. 

그래서 이게 TCA를 통한 (a|b)*abb의 NFA 형식이 되겠다. 다시 말하면 r = (a|b)*abb라는 Regular Expression인데 N(r)을 구할 수 있는 쉬운 방법이 바로 TCA가 되는 것이다. 

이렇게 TCA를 통해서 구한 NFA는 다음과 같은 특징을 지닌다

- 보통 한 요소의 final state를 accepting State라고도 하는데 NFA는 반드시 한개의 start state와 한개의 accepting State로 구성되어 있다.

- 한개의 state에서는 최대 2개의 branch transition을 가질 수 있다.

- TCA를 통한 NFA는 원래 state의 최대 2배까지 많은 state를 가진다. 여기에 대해서 부연 설명을 하자면 원래 r을 구성하는 요소인 a와 b의 maximum state number는 5 이다. 그런데 NFA를 구하고 난 뒤의 Final State Number를 보면 10이 되어 있음을 알 수 있다. 보통 이정도의 값을 가진다고 한다.

이렇게 쉽게 NFA를 구했으니 이제 이 NFA를 DFA로 바꿔야 하는데 여기에는 다시 Subset Construction Algorithm이라는 게 사용된다. 이 부분은 다음 포스트에서 언급하고자 한다.