DFA 구현: hardwired 코드와 table-driven scanner를 같은 상태 머신으로 읽기

이 글은 개인 학습 아카이브에 보관된 컴파일러 강의 PDF·슬라이드·코드 예제를 교차 검토해 새로 구성한 학습 노트입니다. 오래된 표기, 오탈자, 실행되지 않는 예시는 본문에서 별도로 바로잡았으며 원본 파일이나 내부 경로는 공개하지 않습니다.

목표 언어부터 고정하기

다음 식별자 규칙을 구현한다고 하자.

letter (letter | digit)*

첫 문자는 letter여야 하고 이후에는 letter 또는 digit이 0회 이상 온다. 오토마타의 핵심 상태는 간단하다.

• START: 아직 아무것도 읽지 않음
• IN_ID: 첫 letter를 읽었으며 현재까지 식별자
• ACCEPT: 식별자 뒤의 구분자를 lookahead로 확인
• ERROR: 첫 문자가 규칙을 만족하지 않음

여기서 이론적 DFA와 lexer 구현을 구분해야 한다. 완전 DFA는 모든 상태와 입력 기호에 transition이 있다. 실제 scanner에는 “이 문자는 다음 token의 시작이므로 확인만 하고 소비하지 않는다”는 커서 정책이 추가된다. 이것은 언어 인식의 수학적 transition과 입력 버퍼 운용을 결합한 구현 규칙이다.

hardwired 구현

상태별 동작을 코드 분기로 직접 적는 방식이다.

function scanIdentifier(input: string, start: number) {
  let state = "START";
  let cursor = start;

  while (true) {
    const ch = input[cursor]; // undefined means EOF

    if (state === "START") {
      if (!isLetter(ch)) return { kind: "error", cursor };
      state = "IN_ID";
      cursor += 1;
      continue;
    }

    if (isLetter(ch) || isDigit(ch)) {
      cursor += 1;
      continue;
    }

    return {
      kind: "identifier",
      lexeme: input.slice(start, cursor),
      nextCursor: cursor, // delimiter is observed, not consumed
    };
  }
}

장점은 작은 automaton의 의미가 코드에 바로 보이고 state별 특수 처리를 넣기 쉽다는 점이다. 단점은 token 종류가 늘수록 중복 분기와 상태 번호가 퍼져 수정하기 어렵다는 점이다.

table-driven 구현

동일한 상태 머신을 데이터로 옮길 수 있다.

class:        LETTER  DIGIT  OTHER  EOF
START:        IN_ID   ERROR  ERROR  ERROR
IN_ID:        IN_ID   IN_ID  ACCEPT ACCEPT

const transition = {
  START: { LETTER: "IN_ID", DIGIT: "ERROR", OTHER: "ERROR", EOF: "ERROR" },
  IN_ID: { LETTER: "IN_ID", DIGIT: "IN_ID", OTHER: "ACCEPT", EOF: "ACCEPT" },
} as const;

const advance = {
  START: true,
  IN_ID: true,
  ACCEPT: false,
  ERROR: false,
} as const;

실행 루프는 현재 state와 입력의 character class로 다음 state를 찾는다. Accept[state]는 그 상태에서 token을 반환할 수 있는지, Advance[state]는 방금 본 문자를 소비할지 나타낼 수 있다. 표와 실행기가 분리되므로 generator가 만든 큰 DFA에 적합하다. 반면 행·열 번호가 어긋나거나 accepting과 advance 표가 다른 상태 순서를 쓰면 코드가 실행되어도 틀린 token을 만든다.

a9 실행 추적

입력이 문자 a, 숫자 9, 공백 순서라고 하자.

반환되는 token은 ID("a9")이고 next cursor는 공백 위치다. 바깥 scanner loop가 다음 token을 찾으며 공백을 건너뛴다. ACCEPT로 이동할 때 공백까지 소비해 버리면 단순 공백에서는 우연히 괜찮아 보여도 name+1의 +를 잃는 버그가 된다.

최장 일치와 마지막 accepting 지점

identifier 하나만 보면 “구분자를 만날 때 반환”으로 충분하다. 여러 token 규칙을 한 DFA로 합치면 현재 state가 non-accepting이 되기 직전까지 읽은 뒤 가장 최근 accepting state와 cursor로 되돌아가야 한다.

lastAcceptState  = none
lastAcceptCursor = start

while transition exists:
  move and maybe consume
  if current state accepts:
    remember state and cursor

if remembered:
  rewind to lastAcceptCursor and emit its token
else:
  report lexical error

이것이 maximal munch다. 동률이면 보통 rule priority로 keyword와 identifier처럼 겹치는 규칙을 해결한다. 다른 방법은 모든 이름을 먼저 identifier로 읽고 symbol/keyword table에서 if, while 등을 다시 분류하는 것이다.

“00을 포함하는 문자열” DFA로 디버깅하기

아카이브의 실행 화면에는 alphabet {0,1}에서 substring 00을 포함하는 문자열을 인식하는 별도 예제가 있다.

• P(start): 아직 연속된 0을 보지 못함. 1이면 P, 0이면 q
• q: 마지막 문자가 0 하나. 1이면 P, 0이면 r
• r(accepting): 이미 00을 봄. 이후 0과 1 모두 r

0011은 P→q→r→r→r로 accept한다. 0101은 P→q→P→q→P라서 reject한다. 이 예제는 hardwired와 table-driven 결과를 비교하는 좋은 oracle이다. 화면의 전이표 버전처럼 두 구현의 결과가 다르면 이론을 바꿀 것이 아니라 다음을 확인한다.

1. state 번호와 표의 행 순서가 같은가?
2. 입력 '0'을 열 0으로, '1'을 열 1로 정확히 분류했는가?
3. 입력을 모두 읽은 뒤 최종 state를 검사하는가?
4. accepting 배열이 같은 state numbering을 쓰는가?
5. 없는 transition을 음수 index로 다시 참조하지 않는가?

production scanner에 추가할 경계

• EOF를 일반 문자와 구별하되, IN_ID에서는 정상 accept할 수 있어야 한다.
• letter의 범위를 ASCII로 제한할지 Unicode 식별자를 지원할지 언어 명세로 정한다.
• newline과 위치를 추적해 진단에 line/column 또는 byte offset을 남긴다.
• 빈 입력, 숫자로 시작, 매우 긴 identifier, Unicode 조합 문자, name+1을 테스트한다.
• 오류 transition 뒤 transition table을 -1로 indexing하지 않는다.
• C/C++ 예제의 gets, void main, 범위 없는 배열 접근은 현대적인 안전 코드로 교체한다.

핵심은 “switch냐 표냐”가 아니다. 상태 전이, accepting, 입력 소비, token 우선순위를 서로 다른 책임으로 보이게 만드는 것이 검증 가능한 scanner를 만든다.