[컴파일러 이론] 2. FSA, DFA, NFA

2025.11.20 - [컴파일러] - [컴파일러] 1. lexical analysis, scanner, regular expression

[컴파일러] 1. lexical analysis, scanner, regular expression

 
 
이전 글에서 RE를 사용해 각 token의 pattern을 만드는 것까지 알아봤었다.
이번에는 이 pattern들을 인식하는 법을 알아보자.

---

Finite State Automata(FSA)

먼저 Finite State Automata(FSA)라는 개념에 대해 알아야 한다.

기본적으로 input state에서 시작하고, 들어오는 input에 따라 다른 state로 이동한다.
두줄로 표시된 노드는 accepting state로 최종적으로 이 노드로 간다면 이 그래프가 나타내는 표현에 해당한다는 것이다.
말은 좀 복잡할 수 있지만 아래 3가지의 예시를 보면 이해하기 쉽다.
 
<예시>
case1 : input state인 state0에서 시작한다.
input의 첫글자가 B이므로 state1로,
이어서 A로 인해 state0으로,
다시 A로 인해 state0으로,
마지막 A로 인해 최종적으로 state0에서 끝난다.
이 state0은 accepting state가 아니므로 BAAA는 이 그래프가 나타내는 문법에 해당되지 않는 것이다.

case2 : 앞의 세글자 BAB에 의해 state는 0 → 1 → 0 → 1이 된다.
state1에서 네번째 글자를 input으로 받으면 해당 transit이 없으므로 여기서 멈춘다.
accepting state에서 멈췄지만 input이 끝나서 멈춘 것이 아니므로 이 경우도 input은 문법에 해당되는 string이 아닌것이다.
 
case3 : 이 경우는 직접 해보면 accepting state에서 정확히 끝나는 것을 확인할 수 있다.
 
FSA에는 두 종류가 있다. 각각 DFA와 NFA이다.
 

---

DFA와 NFA

<DFA>
DFA는 Deterministic finite automata의 약자이다.
DFA는 state하나 당 transition이 하나만 있는 것이다. 즉, 화살표가 노드 당 하나이다.
또 ε transition이 없다. 이는 아무 input 소모 없이 다른 state로 이동할 수 있는 것을 의미한다.
 
아래 그림은 정규표현식 AA* | B | AB를 accept하는 DFA이다.

 
<NFA>
NFA는 반대로 state하나에서 나오는 화살표가 여러 개 일 수 있다.
ε 무브도 있을 수 있다.
우리가 주목할 특징인 RE를 NFA로 나타내는 것이 쉽다는 특징도 있다.
 
여기서는 ε무브는 언제든 이동할 수 있기 때문에 그것까지 고려해야한다.
한글자의 input에 대해 여러개의 state로 transition이 될 수 있다.

---

<전체 흐름>
따라서 전체 흐름을 보면
① token들을 RE로 표현하고,
② RE를 NFA로 표현하고,
③ NFA를 DFA로 바꾸고,
④ 이 DFA에서 transition을 어떻게 할지 써놓은 표를 만들어서 실제 구현을 하는 방식이다.
 
우리는 현재 ①과정까지 하는 법을 알아봤다.

 

---

RE → NFA

이제 위의 전체 흐름 중 ② 단계인 RE를 NFA로 바꾸는 법을 알아보자.
아래 그림에 따라 기계적으로 바꾸면 되기 때문에 앞서 얘기했듯 변환은 어렵지 않다.

하나의 예시를 들어서 확실히 이해를 해보자.
아래 그림은 (+|-)?d+ 라는 RE에 대한 NFA이다.

---

NFA에서 DFA로의 변환

위에서 얘기한 ③번 과정이다.
 
NFA에서는 하나의 상태에서 여러개의 transition 선택지가 있다.
이렇게 딱 하나로 정해지지않는 non-deterministic transition들을 없애야 한다.
 
< ε-closure >
NFA에서 어떤 state에서 ε 무브만 해서 도달할 수 있는 모든 state들의 집합을 ε-closure라고한다.
아래 NFA는 a*b*라는 RE를 나타낸 것이다.

여기서
ε-closure(0) = {0,1,2}
ε-closure(1) = {1,2}
ε-closure(2) = {2}
와 같이 표현할 수 있다.
 
<Delta($\Delta$) transition>
한가지 더 알아야할 것이 있다.
 
$\Delta$(현재상태, 입력) = 다음 상태
처럼 사용한다.
위 그림에서 예를 들면 $\Delta$(1, a) = 1 처럼 사용가능하다.
state1에서 a를 입력으로 받으면 자기자신으로 돌아오기 때문이다.
 
여기서 현재상태와 다음상태는 집합이 올 수도 있다.
위의 ε-closure와 같이 사용하면,
$\Delta$(ε-closure(0), a)처럼 사용가능하다. 이 식의 결과는 무엇일까?
 
ε-closure(0) = {0,1,2}이므로 각 state에서 a를 만났을 때 가능한 모든 경우를 찾아봐야한다.
 
state0,state2에서 a를 만났을 때는 어떤 행동도 할 수 없다.
state1에서 a를 만났을 때는 자기자신인 state1으로 이동한다. 여기서 ε무브를 통해 state2까지 이동할 수 있다.
 
따라서 $\Delta$(ε-closure(0), a) = {1,2} = ε-closure(1) 처럼 쓸 수 있다.
 
<NFA to DFA>
이제 원래 목적인 NFA를 DFA로 바꾸는 방법을 예시를 통해 알아보자.
우리가 바꿔볼 NFA는 아래 그림의 NFA이다.

1. 시작 state인 state0의 ε-closure를 구한다.
ε-closure(0) = {0,1,2,4}
 
2. 이 closure로부터 가능한 모든 delta transition을 계산한다. 결과는 closure을 사용해 나타낸다.
$\Delta$(ε-closure(0), a) = {2,5} 인데, ε-closure(2) = {2}, ε-closure(5) = {5}이고, {2,5}= ε-closure(2|5)처럼 표시도 가능핟.
$\Delta$(ε-closure(0), a) = ε-closure(2|5)
b에 대해서도 구하면,
$\Delta$(ε-closure(0), a) = ε-closure(3)
 
3. 다시 2번을 적용할 수 있는 결과값에 대해서 다시 2번 과정을 수행한다. 
$\Delta$(ε-closure(3),)은 어떤 transition도 불가능하기 때문에 결과가 없다.
$\Delta$(ε-closure(2|5), a) = ε-closure(5)
$\Delta$(ε-closure(2|5), b) = ε-closure(3)
 
4. 새로운 결과값이 나오지 않을 때까지 반복한다.
$\Delta$(ε-closure(5), a) = ε-closure(5)
 
5. 델타 함수의 input으로 들어갔던 집합들을 DFA의 state로 삼아 DFA를 그린다.
ε-closure(0) [A], ε-closure(2|5) [B], ε-closure(5) [5], ε-closure(3) [3]

---

DFA Optimization

어떤 DFA들은 더 간단하게 최적화가 가능하다.
아래 그림에서 왼쪽 그래프는 오른쪽 그래프로 변경해도 동일한 내용을 표현한다.

왼쪽에서 state2와 state3은 모든 transition에 대해 결과가 동일하다는 것을 알 수 있다.
즉 a를 만나면 둘다 4로, b를 만나면 둘다 3으로 간다.
이럴 경우 두 노드를 합칠 수 있다.
 
하지만 매번 이렇게 노가다로 찾을 수는 없기 때문에, 아래의 방법이 개발되었다.
 
1. 먼저 non-accepting state와 accepting state의 두 그룹으로 나눈다.
{0,3,5}, {1,2,4}
 
2. 각각의 그룹에 대해 어떤 input을 넣으면 다른 state로 transition하는 state를 분리한다.
말이 좀 어렵긴 한데 {0,3,5}그룹을 예시로 보자.
0,3은 b를 만나면 accepting state로 가는데, 5는 그렇지 않다.
따라서 0,3과 5를 나눌 수 있다.
{1,2,4}그룹의 경우에 어떤 input을 넣어도 셋이 같은 결과를 가지기 때문에 분리되지 않는다.
{0,3}, {5}, {1,2,4}
 
3. 이를 그룹에 변화가 없을 때까지 반복한다.
최종 : {0,3}, {5}, {1,2,4}

즉 최종 결과의 각 그룹은 하나의 state로 합칠 수 있다.
이후 테이블로 바꾸면 모든 과정이 끝난다.

---

이렇게 코드를 문자열로 입력받아 token들로 나눠주는 컴파일러의 첫번째 단계, Scanner를 알아보았다.