NFA와 DFA

NFA(Nondeterministic Finite Automaton)

DFA(Deterministic Finite Automaton)

 

컴파일러를 제작할 때 가장 먼저 해야 할 일이 어휘분석기(Lexical Analyzer 또는 Scanner)의 제작이며, 직접 구현하든 Lex/Flex 같은 제작도구를 이용하든 NFA, DFA와 밀접하게 연관되어 있다. 그렇기 때문에 모든 컴파일러 서적은 NFA와 DFA를 가장 먼저 다룬다. (드래곤북에서도 서장인 1, 2장 다음에 3장에서 바로 다룬다.)

일단, Finite Automaton(FA, 우리나라에선 '유한 오토마타' 라고 부름)이란 걸 먼저 알아야 한다. 간단하게 그냥 기계다. 입력을 받아서 맞다/틀리다 만 응답해주는 기계다. 어휘분석기 입장에서는 982가 숫자인지 아닌지, jman이 식별자(ID)인지 아닌지를 알려주는 기계라고 보면 된다. Finite State Machine(FSM)의 특수한 형태라고 여겨도 괜찮다.

 

FA는 또 다시 NFA와 DFA로 나뉜다. 우리나라에선 비결정적 유한 오토마타(NFA)와 결정적 유한 오토마타(DFA)라고 한다.

이 것 역시 단순하게 알아둬도 구현 관점에서는 큰 문제는 없다.

NFA는 입력에 대해 문자 하나씩 확인할 때 무언가를 확정해 놓지 않고 분석을 진행하는 기계다.

DFA는 입력의 첫문자를 받자마자 무엇인지 판정하고, 뒤이은 문자에 대해서도 이미 어디로 진행할지를 결정해 놓은 기계다.

예를 들어 NFA는 <= 을 입력 받았을 때, 첫글자 <에서 '작다' 로 짐작은 하지만 확정하지 않고, =까지 확인한 후, '작거나 같다' 라고 최종 확정한다. DFA는 반대로 <에서 이미 '작다' 로 판정한 후, =을 만나면서 '작거나 같다' 로 판정을 갱신한다.

 

이 차이가 큰 의미가 있나 생각할 수 있겠지만, 프로그래밍 관점에선 중요하다. NFA는 이론적 정의이며, DFA가 실질적 구현 방식이기 때문이다.

위 예를 구현 관점에서 살펴 보면 이해가 빠를 것이다. 간단한 제어문을 짜본다.

if(c == '<')
{
  token = LESS;
  if(c == '=')
  {
    token = LESS_EQUAL;
  }  
  else if(c == '<')
  {
    token = LEFT_SHIFT;
  }
  else
  { // no-op
  }
}

 

만약 이런 식으로 어휘분석기를 제작한다고 했을 때, <을 만나면 '작다' 로 판정을 미리 한다(중첩 제어문의 else에서 '작다' 로 판정해도 무방). 중첩된 if에서 =을 만나면 '작거나 같다', <을 만나면 '왼쪽 쉬프트' 로 판정을 갱신한다. NFA와 다른 점이 여기에 있다. 즉, < 뒤에 =을 만나는 경우와, <을 만나는 경우, 그리고 그 외 문자를 만나는 경우를 이미 정해 놓았다는 것이다. 즉, 자연스럽게 DFA 방식으로 구현을 진행하게 된다.

 

그럼 NFA는 언제 필요할까? 바로 언어의 어휘 설계 단계다. DFA는 설계 입장에선 모든 경우에 수를 나열해줘야 하기 때문에 골치가 아프다. 하지만, NFA는 정규식과 유사하게 축약된 표현만 해주면 되므로 설계가 간편하다. 내가 제작 중인 언어의 어휘 설계도 이 방식을 따른다. 아래 링크를 참조하시길.

ylang - 어휘 분석 단계 - NFA 기반 토큰 정의

 

---

학교에서 배우는 컴파일러 서적들은 이 부분을 꽤 깊이 있게 다룬다. 왜냐하면 그런 책들은 이미 교재로 이용될 것을 염두에 두고 집필한다. 무슨 뜻이냐면 시험에 나와야 하거든. 이 말인 즉슨 학교에서 배울 때는 대충 배우고 넘어갈 수 없다는 것이다. 하지만, 나처럼 그저 취미로 구현해볼까 하는 분들은 이 포스트 정도만 이해해도 문제 없이 구현 가능하실 것이다.

그리고, 개인적으로 드래곤북은 이 부분에서 너무 많은 내용을 다루다 보니 축약이 많고 설명이 불친절하다. 번역서라서 그럴 수도 있고. 만약 이 부분을 깊이 있게 공부하겠다면 드래곤북을 읽기 전에 오세만님이 쓰신 '컴파일러 입문' 을 읽어보길 추천한다.