[컴파일러] FSM(유한상태기계, 유한상태오토마타(FSA)) | 정규표현식 인식 방법
·
컴파일러
어떤 입력이 들어오면 상태를 바꿔야 할 수 있다. 예를 들면 : A상태에서 어떤 입력이 들어오면 B상태로 전이하고 싶은 경우 이 경우 '상태 전이도'로 나타낼 수 있고, 유한상태오토마타(FSA)로 상태전이를 표현할 수 있다. 지금부터 정규표현식을 인식하는 과정을 FSA로 나타낼 것이다. 정규표현식을 상태 전이도를 통해 인식하겠다는 것이다. 어떤상태에서 어떤 입력(표현)이 들어오면 다음 상태로 전이하고, 무언가에서 또 어떤 입력(표현)이 들어오면 다음상태로 전이하고... 이런 전이도를 통해 정규표현식을 인식해낼 수 있다. FSA는 컴파일러 제작에도 쓰인다. 컴파일러 제작시 token을 인식해야 한다. 지금부터 token 인식을 예시로 FSA를 공부해보겠다. token은 식별자, 키워드, 상수, 연산자, 문..