[컴파일러] FSM(유한상태기계, 유한상태오토마타(FSA)) | 정규표현식 인식 방법
어떤 입력이 들어오면 상태를 바꿔야 할 수 있다.
예를 들면 : A상태에서 어떤 입력이 들어오면 B상태로 전이하고 싶은 경우
이 경우 '상태 전이도'로 나타낼 수 있고, 유한상태오토마타(FSA)로 상태전이를 표현할 수 있다.
지금부터 정규표현식을 인식하는 과정을 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는 ε 입력을 다루지 않는다.