2장. 스캐너

소스 코드 문자 흐름을 토큰의 흐름으로 잘라 주는 부품. 정규표현식에서 NFA, NFA에서 DFA, 그리고 최소 DFA까지 — 컴파일러 프론트엔드 첫 관문의 이론과 구현.

2.1 들어가며 — 스캐너가 하는 일

컴파일러가 소스 코드를 처음 만나면 가장 먼저 하는 일은 글자 한 줄 한 줄을 읽어서 의미 있는 단어 단위(토큰)로 자르는 것이다. 이걸 하는 부품이 스캐너(scanner), 다른 말로 어휘 분석기(lexical analyzer)다. 영어 문장을 보면서 "if는 한 단어, while은 다른 단어, x123은 식별자"라고 분류하는, 말하자면 컴파일러의 음절 분석가다.

컴파일러 안에서 스캐너의 위치는 독특하다. 모든 글자를 빠짐없이 만지는 유일한 패스(pass)다. 그래서 스캐너의 입력 크기는 다른 어떤 패스보다도 크고, 한 글자당 비용이 1ms만 늘어도 전체 컴파일 속도가 눈에 띄게 느려진다. 이 때문에 컴파일러 작성자는 스캐너의 속도에 강박적으로 집착한다 — 다행히 스캐너가 하는 일이 단순해서 충분히 빠르게 만들 수 있다.

로드맵

이 장에서 다루는 흐름은 다음과 같다.

• 2.2 단어 인식 — "단어를 알아본다"는 게 형식적으로 무엇인지. 전이 다이어그램과 유한 오토마타(FA).
• 2.3 정규표현식 — 어휘 구조를 적는 표기법. 합집합·연결·클로저 세 가지 연산.
• 2.4 RE → 스캐너 — 톰슨 구성(NFA), 부분집합 구성(DFA), Hopcroft 최소화.
• 2.5 스캐너 구현 — 테이블 기반, 직접 코드, 손코딩 세 가지 전략.
• 2.6 고급 주제 — DFA → RE, Brzozowski 알고리즘, 클로저 없는 RE.

실무 컴파일러는 의외로 손으로 짠 스캐너를 많이 쓴다. 자동 생성된 스캐너보다 인터페이스 오버헤드를 더 줄일 수 있어서다. 그래서 이 장은 자동 생성과 수작업 양쪽을 모두 다룬다.

2.2 단어 인식하기

가장 단순한 인식기 알고리즘은 글자 하나하나를 검사하는 코드다. 키워드 new를 알아본다고 해 보자. NextChar()가 다음 글자를 돌려준다고 가정하면, 이런 식의 중첩 if문을 짤 수 있다.

// "new"를 인식하는 단순 코드
c ← NextChar();
if (c = 'n') then begin
   c ← NextChar();
   if (c = 'e') then begin
      c ← NextChar();
      if (c = 'w') then report success;
      else try something else;
   end;
   else try something else;
end;
else try something else;

이 코드를 그림으로 옮기면 깔끔한 전이 다이어그램(transition diagram)이 된다. 각 원이 상태고, 화살표 위에 적힌 글자가 그 상태에서 그 글자가 들어왔을 때 다음 상태로 넘어간다는 뜻이다.

   ┌────┐  n   ┌────┐  e   ┌────┐  w   ╔════╗
   │ s₀ │ ───▶ │ s₁ │ ───▶ │ s₂ │ ───▶ ║ s₃ ║
   └────┘      └────┘      └────┘      ╚════╝
                                       (수락 상태)

여러 단어를 동시에 인식하려면 가지(branch)를 늘리면 된다. 예컨대 new와 not이라면 s₁에서 e로 가는 길과 o로 가는 길을 둘 다 만들면 된다. while까지 합쳐 한 그래프에 넣으면 가지가 더 풍성해질 뿐, 원리는 같다.

2.2.1 인식기의 형식론 — 유한 오토마타

이 그림이 곧 유한 오토마타(finite automaton, FA)의 그림이다. 형식적으로 FA는 다섯 개짜리 묶음 (5-tuple) 이다.

FA가 문자열 x = x₁x₂...xn을 받아들인다는 말은, s₀에서 출발해 글자를 차례로 먹으며 전이했을 때 마지막에 도착한 상태가 수락 상태에 속한다는 뜻이다. 형식적으로:

δ(δ(...δ(δ(s₀, x₁), x₂)..., xn-1), xn) ∈ SA

FA 동작 비용은 입력 문자 1개당 전이 1번 — 즉 O(입력 길이)다. 이게 핵심이다. 정규표현식이 아무리 복잡해도 실행 비용은 입력 길이에만 비례한다.

2.2.2 더 복잡한 단어 — 무한 집합 인식

이제 "부호 없는 정수"처럼 무한히 많은 단어가 속한 집합을 인식하고 싶다고 하자. 정의는: "0 자체이거나, 1~9로 시작해서 0~9가 0개 이상 따라붙은 것."

이걸 직선 그래프로 그리면 상태가 끝없이 늘어난다. 해법은 간단하다 — 사이클을 허용하면 된다.

              ┌──────── 0..9 ────────┐
              ▼                      │
   ┌────┐ 1..9  ╔════╗               │
   │ s₀ │ ────▶ ║ s₂ ║ ──────────────┘
   └─┬──┘       ╚════╝
     │  0
     ▼
   ╔════╗
   ║ s₁ ║   ← "0" 하나만 받는 경로
   ╚════╝

이 사이클이 핵심이다. 직선 if-else 중첩으로는 사이클을 표현할 수 없으니, 이젠 while 루프로 구현해야 한다.

char  ← NextChar();
state ← s₀;
while (char ≠ eof and state ≠ se) do
   state ← δ(state, char);
   char  ← NextChar();
end;
if (state ∈ SA)
   then report acceptance;
   else report failure;

여기서 전이 함수 δ는 보통 2차원 테이블로 표현한다. 행은 상태, 열은 입력 글자. 원래 표는 0,1,...,9,Other로 11개 열을 갖지만, 1~9 열이 모두 동일하므로 압축해서 0 / 1..9 / Other 3열로 줄일 수 있다. 메모리를 아끼는 첫 번째 트릭이다.

식별자 같은 건 더 단순하다 — "알파벳 한 글자 + 0개 이상의 영숫자"는 두 상태짜리 FA로 끝난다.

2.3 정규표현식 (RE)

FA가 받아들이는 문자열의 집합을 언어(language)라고 하고 L(F)로 쓴다. 사람이 FA를 직접 그리는 건 번거로우니, 같은 언어를 더 간결하게 적는 표기법이 필요하다 — 그게 정규표현식(regular expression, RE)이고, RE로 적을 수 있는 언어를 정규 언어(regular language)라 한다.

2.3.1 RE의 세 가지 기본 연산

RE는 알파벳 Σ 위에서, 빈 문자열 ε을 추가하여, 다음 세 연산만으로 만들어진다.

편의를 위해 다음 약어도 자주 쓴다.

• R⁺ = RR* — 양의 클로저(positive closure), "1번 이상 반복"
• Ri — 유한 클로저, "i번 반복" (예: R³ = RRR)
• [a..z] — 글자 범위 약어, 사실상 a|b|c|...|z
• ^c — 보집합(complement) 연산자, "c가 아닌 모든 글자"

우선순위는 괄호 > 클로저 > 연결 > 합집합 순서. 그래서 a|b*는 a | (b*)이지 (a|b)*가 아니다.

2.3.2 실전 예시

프로그래밍 언어에서 자주 마주치는 RE 다섯 가지를 보자.

마지막 ILOC 예시를 음미해보면 — "0~31 사이 숫자"를 정확히 표현하려고 RE가 갑자기 복잡해진다. 같은 의미를 단순하게 쓰려면 r0 | r1 | r2 | ... | r31처럼 32개를 늘어놓는 방식도 있다. 컴파일러 작성자는 이 둘 사이에서 "표현의 우아함 vs 상태 폭증" 트레이드오프를 골라야 한다. 다행히 둘 다 한 글자당 1전이라는 비용은 똑같다.

2.3.3 RE의 클로저 성질 (closure properties)

RE에는 매우 유용한 닫힘 성질들이 있다. 두 RE에 어떤 연산을 적용해도 결과가 또 RE라는 뜻이다.

• 연결·합집합·클로저 아래 닫힘 — 정의상 당연하다. 그래서 우리가 각 구문 범주(예: 키워드, 식별자, 숫자)에 대해 a₀, a₁, ..., aₙ 각각의 RE를 갖고 있다면, 합집합 a₀ | a₁ | ... | aₙ이 곧 전체 어휘의 RE가 된다. 이게 스캐너 자동 생성의 출발점이다.
• 유한 언어는 곧 정규 언어 — 합집합 닫힘 덕분에, 단어 100개를 늘어놓아도 그대로 RE다.
• 보집합 아래 닫힘 — 완전한 FA(complete FA, 모든 오류 전이를 명시한 FA)에서 수락/비수락 상태를 뒤집기만 하면 보집합 언어를 인식하는 FA가 된다. 그래서 lex에 ^ 연산자가 있다.

이 성질들이 다음 절의 구성 알고리즘들이 잘 작동하는 이유를 떠받친다.

2.4 RE에서 스캐너로 — 구성의 사이클

실제 스캐너를 자동으로 만들려면, RE → FA → 코드까지 가는 변환이 필요하다. 이 변환은 세 단계의 사이클을 이룬다.

                  Thompson 구성
       ┌─────────────────────────────▶ NFA
       │                                │
       │                                │ 부분집합 구성
       RE                                ▼
       ▲                               DFA  ──── 코드 ────▶ 스캐너
       │                                │
       │     Kleene 구성                  │ Hopcroft 최소화
       └─────────────────────────────── ◀┘ (DFA→DFA)

2.4.1 결정적 vs 비결정적 FA

NFA의 동작을 이해하는 직관은 두 가지가 있다.

1. 전지전능 모델 — NFA가 매 갈림길에서 "정답으로 향하는 길"을 알고 정확히 그 길로 간다. 마술 같지만 정의는 깔끔하다.
2. 복제 모델 — 갈림길에서 NFA가 자기 자신을 복제해 모든 가능성을 동시에 추적한다. 어느 클론이 수락 상태에 도달하면 받아들임. 이때 "현재 활동 중인 상태들의 집합"을 NFA의 구성(configuration)이라 부른다.

놀라운 사실: 표현력은 둘이 같다. 모든 NFA는 동등한 DFA로 변환할 수 있다(부분집합 구성으로 증명). DFA는 NFA의 특수한 경우이므로 역방향은 자명하다.

NFA의 구성은 NFA 상태 집합의 부분집합이므로 최대 2|N|개. 따라서 동등한 DFA는 NFA보다 지수적으로 클 수 있지만 유한하다 — 시간 문제가 아니라 공간 문제다.

2.4.2 RE → NFA: Thompson 구성

Thompson 구성(Thompson's construction)은 RE의 각 연산자에 대응하는 작은 NFA 조각들을 합쳐 큰 NFA를 짓는다. 핵심은 각 RE 연산자마다 한 가지 합치기 패턴만 알면 된다는 점.

(a) 한 글자 a:           (c) 연결 ab:
   ┌──┐ a  ╔══╗           ┌──┐ a  ┌──┐ ε  ┌──┐ b  ╔══╗
   │s_i│──▶║s_j║           │s_i│──▶│s_j│──▶│s_k│──▶║s_l║
   └──┘    ╚══╝           └──┘    └──┘    └──┘    ╚══╝

(d) 합집합 a|b:                    (e) 클로저 a*:
            ε   ┌──┐ a  ┌──┐ ε                ε
       ┌──────▶│s_i│──▶│s_j│──┐                ┌────────────────┐
   ┌──┐│       └──┘    └──┘  ▼┌──┐         ┌──┐│ ε  ┌──┐ a  ┌──┐ ε ╔══╗
   │s_m│                      │s_n│         │s_p├──▶│s_i│──▶│s_j├─▶║s_q║
   └──┘│       ┌──┐ b  ┌──┐ ε ▲└──┘         └──┘    └──┘    └──┘   ╚══╝
       └──────▶│s_k│──▶│s_l│──┘                ▲        ε             │
            ε   └──┘    └──┘                   └─────────────────────┘

Thompson 구성으로 만든 NFA는 매우 규칙적인 모양을 갖는다. 시작 상태 1개, 수락 상태 1개. 각 상태로 들어오는 ε-전이는 최대 2개, 나가는 ε-전이도 최대 2개, 알파벳 글자 전이는 들어오고 나가는 게 각각 최대 1개. 이 규칙성이 다음 단계(부분집합 구성) 구현을 단순화한다.

2.4.3 NFA → DFA: 부분집합 구성

부분집합 구성(subset construction)의 아이디어 한 줄: "NFA의 가능한 구성(상태들의 부분집합) 하나하나가 DFA의 한 상태가 된다." 그래서 동시에 추적되던 평행우주들을 하나의 결정적 상태로 응축시킨다.

이 알고리즘은 두 개의 보조 함수를 사용한다.

• ε-closure(S) — 상태 집합 S에서 ε-전이만 따라 도달 가능한 모든 상태를 포함시킨 집합. "입력 없이 갈 수 있는 곳까지 미리 다 가둬두기."
• Delta(q, c) = ∪s∈q δN(s, c) — 구성 q의 모든 상태에서 글자 c로 갈 수 있는 NFA 상태들의 합집합.

// 부분집합 구성 알고리즘
q₀ ← ε-closure({n₀});
Q  ← {q₀};                // DFA 상태 모음
WorkList ← {q₀};

while (WorkList ≠ ∅) do
   q를 WorkList에서 꺼낸다;
   for each 글자 c ∈ Σ do
      t ← ε-closure(Delta(q, c));
      T[q, c] ← t;        // DFA 전이 기록
      if t ∉ Q then
         t를 Q에 추가, WorkList에 추가;
      end;
   end;
end;

이 알고리즘은 고정점 계산(fixed-point computation)의 전형이다. 새로운 상태를 발견할 때만 작업이 늘어나고, 가능한 상태(NFA 상태 부분집합) 수가 유한하므로 반드시 종료한다. 최악의 경우 2|N|번 반복.

예: a(b|c)*에 부분집합 구성 적용

Thompson 구성으로 a(b|c)*의 NFA를 만들면 ε-전이가 잔뜩 들어간 큰 그래프가 나온다. 거기에 부분집합 구성을 적용하면 다음 4개의 DFA 상태가 나온다.

   d₀ = ε-closure({n₀})              ← 시작
   d₁ = ε-closure(Delta(d₀, a))      ← 'a' 보고 진입
   d₂ = ε-closure(Delta(d₁, b))      ← 'b' 보고
   d₃ = ε-closure(Delta(d₁, c))      ← 'c' 보고

   결과 DFA:
                       ┌─ b ─┐
                       │     ▼
   ┌──┐ a  ╔══╗ b  ╔══╗
   │d₀│──▶ ║d₁║──▶ ║d₂║
   └──┘    ╚══╝    ╚══╝
            │ c     ▲
            ▼       │ b
           ╔══╗ ────┘
           ║d₃║ ─── c (자기 자신)
           ╚══╝

2.4.4 DFA → 최소 DFA: Hopcroft 알고리즘

부분집합 구성의 결과 DFA는 종종 중복 상태를 포함한다. 같은 행동을 하는 상태들을 합쳐 더 작은 DFA를 얻고 싶다 — 캐시에 들어가는 작은 인식기는 빠르다. Hopcroft 최소화의 아이디어:

이 정의는 순환적이지만, 분할(partition) 정련으로 푼다. 처음엔 거칠게 둘로 나누고, 서로 다른 행동을 보이는 상태들을 발견할 때마다 분할을 더 잘게 쪼갠다.

// Hopcroft DFA 최소화
T ← { DA, D - DA };   // 수락/비수락으로 초기 분할
P ← ∅;
while (P ≠ T) do
   P ← T;
   T ← ∅;
   for each 부분 p ∈ P do
      T ← T ∪ Split(p);  // p를 더 잘게 쪼갤 수 있으면 쪼갬
   end;
end;

// Split: c라는 글자에 대해 서로 다른 부류로 가는 상태를 찾으면 분할
Split(S):
   for each c ∈ Σ do
      if c가 S를 s₁, s₂로 쪼갠다면
         return {s₁, s₂};
   end;
   return S;

왜 처음에 수락/비수락으로 나누나? 수락 상태와 비수락 상태가 같은 부류에 들어가면 절대 안 된다. 이렇게 시작하면 그 불변식이 자연스럽게 유지된다.

예: fee | fie 최소화

원래 DFA:
              e         e
    ┌──▶ s₂ ──▶ ╔══╗
   ┌──┐ f      ║s₃║
   │s₀│──▶s₁              s₃와 s₅는 입력 e로 들어와서
   └──┘            \      더 이상 전이 없음 → 행동이 같음
              ┌──▶ s₄ ──▶ ╔══╗
              i       e   ║s₅║

분할 진화:
  step 0: {s₀,s₁,s₂,s₄}, {s₃,s₅}        ← 비수락/수락
  step 2: e로 인해 {s₀,s₁,s₂,s₄}에서 s₂,s₄가 분리
  step 3: f로 인해 {s₀,s₁}에서 s₁ 분리
  최종:   {s₀}, {s₁}, {s₂,s₄}, {s₃,s₅}

최소 DFA:
   ┌──┐ f  ┌──┐ i,e ┌──┐ e  ╔══╗
   │s₀│──▶│s₁│ ──▶  │s₂│──▶ ║s₃║
   └──┘    └──┘     └──┘    ╚══╝

2.4.5 DFA를 인식기로 사용 — 최장 일치(maximal munch)

이제 DFA로 어떻게 실제 스캐너를 만드는가? 여러 RE r₁, r₂, ..., rₖ를 하나로 묶어 (r₁ | r₂ | ... | rₖ)의 DFA를 만든 뒤 사용한다.

스캐너의 핵심 동작은 "입력을 가능한 한 길게 먹어서 가장 긴 매칭 토큰을 만들어 내라" — 최장 일치(longest match / maximal munch) 규칙이다. 구현은 이렇다.

1. DFA를 글자가 더 이상 전이할 수 없을 때까지 굴린다.
2. 지금 상태가 수락 상태면? 토큰 인식 성공.
3. 지금 상태가 비수락 상태인데, 도중에 거쳐 간 수락 상태가 있다면? 가장 최근 그 수락 상태로 롤백(roll back)해서 그때까지의 글자열을 토큰으로 잡는다.
4. 도중에 한 번도 수락 상태에 들른 적이 없다면? 어휘 오류.

한 가지 합병증: 한 수락 상태가 NFA의 여러 수락 상태(여러 RE)에 대응할 수 있다. 예컨대 new는 키워드 new의 RE에도, 식별자 RE에도 매칭한다. 이때 보통 우선순위(priority) 규칙을 적용한다 — lex는 RE를 적은 순서가 우선순위다. 키워드를 식별자보다 먼저 적으면 키워드가 이긴다.

2.5 스캐너 구현 — 세 가지 길

같은 DFA를 코드로 옮기는 방법은 크게 셋이다.

1. 테이블 기반(table-driven) — 보편 스켈레톤 + 언어별 테이블
2. 직접 코드(direct-coded) — DFA 상태마다 코드 조각, goto로 점프
3. 손코딩(hand-coded) — 사람이 직접 작성, I/O 인터페이스까지 최적화

점근 복잡도는 셋 다 글자당 O(1) — 즉 입력 길이에 비례. 차이는 상수 비용에 있다.

2.5.1 테이블 기반 스캐너

스캐너 생성기는 RE 목록을 받아 (1) 분류기 테이블 CharCat, (2) 전이 테이블 δ, (3) 토큰 타입 테이블 Type을 출력한다. 스켈레톤 코드는 언어 독립이고, 테이블만 갈아끼우면 다른 언어로 변신한다.

// ILOC 레지스터 r[0..9]+에 대한 테이블 기반 스캐너
NextWord():
   state  ← s₀;
   lexeme ← "";
   clear stack;
   push(bad);

   // 메인 루프: DFA 시뮬레이션
   while (state ≠ se) do
      NextChar(char);
      lexeme ← lexeme + char;
      if state ∈ SA
         then clear stack;
      push(state);
      cat   ← CharCat[char];
      state ← δ[state, cat];
   end;

   // 롤백 루프: 마지막 수락 상태까지 되돌림
   while (state ∉ SA and state ≠ bad) do
      state ← pop();
      truncate lexeme;
      RollBack();    // 입력 포인터 1글자 되돌림
   end;

   if state ∈ SA
      then return Type[state];
      else return invalid;

매 글자에 두 번의 테이블 룩업: (글자 → 카테고리), 그리고 (상태, 카테고리 → 다음 상태). CharCat는 ASCII면 256엔트리, 작아서 캐시에 잘 들어간다. 전이 테이블 δ는 (상태 수 × 카테고리 수)인데, 카테고리로 압축되어 있어 순수 글자별 테이블보다 훨씬 작다.

2차 폭주 방지 — 최대 먹기 스캐너

병적인 경우 롤백이 2차(quadratic) 비용으로 폭주할 수 있다. RE ab | (ab)*c를 입력 ababab에 대해 돌리면, 매번 끝까지 갔다가 처음으로 돌아오는 패턴이 반복된다. 해결책: 실패한 (상태, 입력 위치) 쌍을 비트 배열 Failed에 기록하여, 같은 위치에 같은 상태로 다시 오면 즉시 멈춘다.

// 최대 먹기(maximal munch) 스캐너의 핵심 변경
while (state ≠ se) do
   NextChar(char);
   InputPos ← InputPos + 1;
   lexeme   ← lexeme + char;

   if Failed[state, InputPos]
      then break;        // 이미 가본 막다른 길
   ...
end;

while (state ∉ SA and state ≠ bad) do
   Failed[state, InputPos] ← true;   // 실패 기록
   ...
end;

대부분의 프로그래밍 언어 어휘는 이 폭주가 일어날 만큼 복잡하지 않아서 일반 테이블 기반으로 충분하다. 하지만 가능성을 알면 대비할 수 있다.

2.5.2 직접 코드 스캐너

테이블 기반의 두 가지 오버헤드: 테이블 주소 계산 + 메모리 로드. 직접 코드 스캐너는 이걸 없앤다 — DFA의 상태와 전이 그래프를 코드 자체로 표현한다. 각 상태마다 작은 코드 조각이 있고, 한 조각의 끝에서 goto로 다음 조각으로 점프한다.

// r[0..9]+의 직접 코드 스캐너

s_init: lexeme ← "";
        clear stack;
        push(bad);
        goto s₀;

s₀:     NextChar(char);
        lexeme ← lexeme + char;
        if state ∈ SA then clear stack;
        push(state);
        if char = 'r' then goto s₁;
        else goto s_out;

s₁:     NextChar(char);
        lexeme ← lexeme + char;
        if state ∈ SA then clear stack;
        push(state);
        if '0' ≤ char ≤ '9' then goto s₂;
        else goto s_out;

s₂:     NextChar(char);
        lexeme ← lexeme + char;
        if state ∈ SA then clear stack;
        push(state);
        if '0' ≤ char ≤ '9' then goto s₂;
        else goto s_out;

s_out:  // 롤백 + 결과 반환
        ...

이 스타일을 흔히 스파게티 코드(spaghetti code)라 부른다 — 보기에 어지럽지만 사람이 읽을 코드가 아니라 스캐너 생성기가 뱉어내는 코드다. 더 빠른 게 중요하지 가독성은 부차적이다.

왜 더 빠른가

• 전이 함수 호출이 단순 비교문으로 변함 — 테이블 주소 계산 없음.
• 각 상태에서 비교할 글자 종류가 적으면(예: r 하나만), 코드가 매우 짧아져 분기 예측이 잘 됨.
• state 변수 자체가 사라짐 — 제어 흐름 위치가 곧 상태.

2.5.3 손코딩 스캐너

실무 컴파일러(GCC 4.0 등) 상당수는 손으로 짠 스캐너를 쓴다. 직접 코드보다 더 빨라서가 아니라, 스캐너와 외부의 인터페이스 비용(I/O, 렉심 복사 등)을 더 잘 줄일 수 있어서다.

입력 버퍼링 — 이중 버퍼

한 글자씩 시스템 호출하는 건 너무 비싸다. 큰 버퍼를 한 번에 채우고 그 안에서 포인터를 옮긴다. 그러나 롤백을 지원하려면 이전 글자에도 접근 가능해야 한다. 해법: 이중 버퍼링(double buffering).

  ┌──────── Buffer 0 ──────────┬──────── Buffer 1 ────────┐
  │                            │                          │
  0                            n-1 n            ▲         2n-1
                                                │
                                          Input 포인터

// NextChar 구현
Char  ← Buffer[Input];
Input ← (Input + 1) mod 2n;
if (Input mod n = 0) then
   Buffer[Input : Input + n - 1]를 새로 채움;
   Fence ← (Input + n) mod 2n;
return Char;

// RollBack 구현
if (Input = Fence)
   then 롤백 한계 초과 오류;
Input ← (Input - 1) mod 2n;

Fence는 안전 한계 — n글자 이상 롤백하지 못하게 막는다. 버퍼 크기를 4096 같은 큰 값으로 두면 I/O 비용이 무시할 수준이 된다.

렉심 직접 변환

정수 토큰의 경우 굳이 글자열 lexeme을 쌓아 두었다가 나중에 atoi로 변환할 필요가 없다. 한 글자씩 받을 때마다 RegNum ← RegNum × 10 + (char - '0')으로 누산하면 된다. 손코딩의 묘미.

2.5.4 키워드 처리 — 두 가지 전략

키워드를 어떻게 인식할까? 두 길이 있다.

스캐너 생성기를 쓴다면 ①이 자연스럽다 — 추가 상태는 컴파일 시간이 아니라 메모리만 먹으니까. 손코딩에서는 완전 해싱(perfect hashing)으로 ②를 빠르게 만들기도 한다. 키워드 집합이 고정이므로 충돌 없는 해시를 미리 계산해 둘 수 있다.

2.6 고급 주제

2.6.1 DFA → RE: Kleene 구성

지금까지 RE → NFA → DFA 방향만 봤다. 역방향 — DFA에서 RE 만들기 — 도 가능하다. Kleene 구성은 DFA의 그래프를 경로 표현식 문제로 환원한다.

핵심 점화식: Rkij는 "상태 i에서 j까지 가는 경로 중, 중간 상태 번호가 k 이하만 거치는 경로들의 RE".

Rkij = Rk-1ik (Rk-1kk)* Rk-1kj | Rk-1ij

i에서 k를 거쳐 j로 가는 경로 = "i에서 k로" + "k에서 자기 자신을 0번 이상 돌고" + "k에서 j로", 이것에 "k 안 거치는 기존 경로"를 합집합. 모든 (i,j) 쌍에 대해 k = -1, 0, 1, ..., |D|-1로 키워가며 채워나간다.

최종 답: L = ⋃j ∈ DA R|D|-10j — 시작 상태에서 모든 수락 상태까지의 경로 표현식 합집합.

2.6.2 Brzozowski 알고리즘 — 우아한 DFA 최소화

Hopcroft 분할 알고리즘 외에 다른 길도 있다. Brzozowski의 매혹적인 한 줄짜리 공식:

여기서:

• reverse(n) — 모든 전이 방향을 뒤집고, 원래 시작 상태를 종료 상태로, 원래 종료 상태들을 새로운 시작 상태들로 만든 NFA.
• subset(n) — 부분집합 구성으로 만든 DFA.
• reachable(n) — 시작 상태에서 도달 가능한 부분만 남긴 그래프.

왜 이게 작동하는가? 안쪽 subset(reverse)는 원래 NFA의 중복 접미사(suffix)를 제거한다. 바깥쪽 subset(reverse)는 중복 접두사(prefix)를 제거한다. 두 번 뒤집으면서 양쪽을 깔끔히 정리하는 셈. 이론적으로 부분집합 구성을 두 번 부르니 비싸 보이지만, 실제로는 NFA의 좋은 성질 덕분에 종종 효율적으로 동작한다.

2.6.3 클로저 없는 RE — 비순환 DFA

w₁ | w₂ | ... | wₙ 형태의 RE — 즉 단순한 단어들의 합집합 — 은 특별한 의미를 갖는다. 이런 RE의 DFA는 사이클이 없다(acyclic). 사전, URL 필터, 해시 키 검사처럼 "고정된 단어 집합 매칭" 문제에 자연스럽게 들어맞는다.

비순환 DFA는 증분식(incremental)으로 짓기 좋다. 새 단어를 기존 DFA에 추가하려면, 시작 상태부터 글자를 따라가다가 더 이상 전이가 없는 지점부터 새 경로를 붙이면 된다. 비용은 새 단어 길이에만 비례.

이런 비순환 DFA는 완전 해싱의 대안이 된다. 충돌 없는 해시 함수를 만드는 대신, 글자별로 트라이(trie)를 따라가는 셈. 키 수가 늘면 캐시 효율이 떨어지므로 어느 시점부터는 해시가 더 빨라지지만, 작은 사전엔 좋은 선택이다.

2.7 정리 — 무엇을 얻었나

이 장에서 따라간 길은 한 줄 요약하면:

각 단계 모두 입력 글자당 O(1) 비용을 지키는 게 가능하다는 점이 본질이다. 정규 언어와 유한 오토마타 이론이 우리에게 준 선물 — "어휘를 적기는 RE처럼 우아하게, 실행은 DFA처럼 빠르게."

또한 이 장에서 두 번 등장한 고정점 계산(부분집합 구성, Hopcroft 분할)은 컴파일러 곳곳에서 다시 만난다. 데이터 흐름 분석(9장), SSA 구성, 타입 추론 — 모두 같은 패턴의 변주다. 단조 함수가 유한 격자(lattice) 위에서 반복되며 한 점에 정착하는 그림은 컴파일러 작성자의 기본기다.

마지막으로 실용적 노트 — 이론은 자동 생성을 향한다지만, 현장의 베테랑들은 손코딩을 즐긴다. 어휘 명세는 자주 바뀌지 않고, 손으로 짜면 I/O 인터페이스부터 끝까지 통제할 수 있어서다. tools first 또는 hands first 둘 다 합리적 선택이다.