[컴파일러] FSM(유한상태기계, 유한상태오토마타(FSA)) | 정규표현식 인식 방법

어떤 입력이 들어오면 상태를 바꿔야 할 수 있다.

예를 들면 : A상태에서 어떤 입력이 들어오면 B상태로 전이하고 싶은 경우

이 경우 '상태 전이도'로 나타낼 수 있고, 유한상태오토마타(FSA)로 상태전이를 표현할 수 있다.

출처 : 위키백과 - 유한상태기계 (https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%95%9C_%EC%83%81%ED%83%9C_%EA%B8%B0%EA%B3%84)

 

 

지금부터 정규표현식을 인식하는 과정을 FSA로 나타낼 것이다.

정규표현식을 상태 전이도를 통해 인식하겠다는 것이다.

어떤상태에서 어떤 입력(표현)이 들어오면 다음 상태로 전이하고, 

무언가에서 또 어떤 입력(표현)이 들어오면 다음상태로 전이하고...

이런 전이도를 통해 정규표현식을 인식해낼 수 있다.

 

 

FSA는 컴파일러 제작에도 쓰인다. 

컴파일러 제작시 token을 인식해야 한다. 지금부터 token 인식을 예시로 FSA를 공부해보겠다.

token은 식별자, 키워드, 상수, 연산자, 문자열로 구분할 수 있는데,

특히 식별자, 상수, 문자열은 어디까지가 token인지 정확히 매치되는 성격이 아니므로

정규표현식을 통해 기술할 수 있겠다.

 

그럼 정규표현식으로 표현된 token을 인식하는 FSA의 상태 전이를 확인해보자.

 

---

∨식별자의 인식

let. 식별자 규칙 : 대소영문자로 시작 & 영문과 숫자로 조합

식별자 규칙을 정규표현식으로 나타낸다면 [a-zA-Z]([a-zA-Z][0-9])* 이다.

즉 [a-zA-Z]가 먼저 1번이상 입력되고 ([a-zA-Z][0-9])*가 0번이상 입력된다.

 

이러한 정규표현식으로 나타내는 식별자를 어떤 FSM을 통해 인식할까?

시작 상태 S라고 하자. 상태 A가 식별자로 인식되는 상태다.

1. S상태에서 [a-zA-Z] 입력 => A상태로 전이  (인식)

2. A상태에서 [a-zA-Z] 또는 [0-9] 입력 => A상태로 전이  (인식)

 

 

 

∨정수의 인식

let. 정수표현 : +, - 부호와 정수값 조합

정수를 정규표현식으로 나타낸다면 ('+'|-|ε)d+ 이다. (d=[0-9])

부호(+, -, 표시x) 이후에 정수가 1개이상 나타난다.

 

이러한 정규표현식으로 나타내는 정수는 어떤 FSM을 통해 인식할까?

시작상태 S라고 하자. 상태 C가 정수로 인식되는 상태이다.

1. S상태에서 + 입력 => A상태로 전이

ㄴA상태에서 정수 입력 => C상태로 전이  (인식)

2. S상태에서 - 입력 => B상태로 전이

ㄴB상태에서 정수 입력 => C상태로 전이  (인식)

3. S상태에서 정수 입력 => C상태로 전이  (인식)

4. C상태에서 정수 입력 => C상태로 전이  (인식)

 

 

∨실수의 인식

let. 실수표현 : 31.435 또는 2342.34e+3 또는 0.432e-13과 같이 표현된다.

정규표현식으로는 (d+.d+)|(d+.d+e(ε|+|-)d+)이다.

 

이러한 정규표현식으로 나타내는 실수는 어떤 FSM를 통해 인식할까?

시작상태 S라고 하자. 상태 C, E가 실수로 인식되는 상태이다.

1. S상태에서 정수 입력 => A상태로 전이

ㄴA상태에서 정수 입력 => A상태로 전이

2. A상태에서 . 입력 => B상태로 전이

ㄴB상태에서 d 입력 => C상태로 전이  (인식)

3. C상태에서 d 입력 => C상태로 전이  (인식)

ㄴC상태에서 e 입력 => D상태로 전이

4. D상태에서 + 입력 => F상태로 전이

ㄴF상태에서 d 입력 => E상태로 전이  (인식)

5. D상태에서 - 입력 => G상태로 전이

ㄴ F상태에서 d 입력 => E상태로 전이  (인식)

6. D상태에서 d 입력 => E상태로 전이  (인식)

7. E상태에서 d 입력 => E상태로 전이  (인식)

 

 

∨문자열의 인식

문자열은 정규표현식으로 "(a|\c)*" 이다.

이때 a는 "와 \ 이외의 모든 문자이고 c는 에스케이프문자라고 하자.

 

시작상태 S라고 하자.

1. S상태에서 " 입력 => A상태로 전이

2. A상태에서 a 입력 => A상태로 전이

3. A상태에서 \ 입력 => C상태로 전이

4. C상태에서 c 입력 => A상태로 전이

5. A상태에서 " 입력 => B상태로 전이 (인식)

 

 

---

이와 같이 token인식을 위해서는 정규표현식을 FSA로 변환하고, 이 전이도대로 인식한다.

그리고 전이도를 코드로 표현하여 컴파일러를 구현하면 된다.

 

 

+ FSA를 알았다면 DFA도 알자

 

DFA는 FSA의 한 종류이다. 

finite automata긴 한데 deterministic finite automata이다.

위에서는 정규표현식을 FSA로 변환했다.

그렇지만 FSA는 non-DFA 즉 NFA일 수 있다.

그럼 이 NFA를 DFA로 변환시키고, 이 DFA를 따라 토큰인식을 해야 한다.

NFA는 프로그래밍 불가능하고, DFA는 프로그래밍 가능하기 때문이다.

 

그럼 NFA랑 DFA가 무슨 차이가 있는지 알아야 한다.

▶ DFA는 각 상태에서 다른 상태로 가는 엣지가 입력되는 문자에 의해 유일하게 결정된다.

- 예시) A --a--> B와 A --a-->C 두개가 공존하는 것은 NFA에서는 가능하지만 DFA에서는 불가능하다. 

▶ DFA는 A에서 B로 전이할 때 입력값이 단 하나이다.

- 예시) A --1--> B와 A --0--> B 처럼 입력값이 여러개일 수 없다. 

▶ DFA는 ε 입력을 다루지 않는다.