Thompson's Construction, Visible

title: "Thompson's Construction, Visible" date: 2026-04-20 category: regex-viz description: "regex 를 그래프가 아니라 타임라인으로 봅니다. Stage 1 — NFA 가 자라는 여섯 규칙을, slider 로 스크럽해서 직접 돌려보기." tech: ["Rust", "TypeScript", "React", "MDX", "dagre"] status: Active github: "https://github.com/Ricci-curvature/regex-viz" order: 1

Regexper, debuggex, regex101 은 regex 를 구조 그래프 로 그립니다. 최종 NFA 의 모양. 완성된 그림.

regex 의 어려움은 구조가 아닙니다. 시간 입니다. NFA 가 AST 를 따라 어떻게 자라는지, active state 집합이 입력 한 글자마다 어떻게 퍼져나가는지, backtracking 이 언제 폭발하는지. 이건 정지 이미지로는 보이지 않습니다.

regex-viz 는 그 빈자리를 채우려는 프로젝트입니다. regex 를 타임라인 으로 봅니다. 그리고 이 블로그는 정지 이미지가 아니라 스크럽 가능한 시각화 로 보여주기로 합니다. 그게 MDX 를 쓰는 이유.

아래 뷰어의 slider 를 움직여 봅시다. a|b*c 가 여섯 step 을 거쳐 완성되는 과정입니다.

상자 하나가 한 AST 노드의 emit 결과입니다. 왼쪽에서 시작한 a 조각과 오른쪽의 b*c 조각이 마지막 step (alternation) 에서 네 개의 ε 로 감싸지는 순간이 이 글의 핵심. 어떻게 저기까지 갔는지, 코드 차원에서 따라가봅시다.

프로젝트의 한 줄

Rust 가 계산한다. MDX 가 설명한다. SVG 가 설득합니다.

세 층, 각 층마다 한 가지 규율만 지킵니다.

• Rust crate + CLI — regex 파싱, NFA/DFA 구축, 매칭. regex crate 금지. nom/chumsky 금지. 바닥부터 짠다. 이 프로젝트의 존재 이유가 "내부가 보이게" 이므로, 편하자고 regex 를 import 하는 순간 목적 상실.
• 구조화된 Trace JSON — 모든 stage 가 Trace 를 emit 한다. step 의 시퀀스, 각 step 은 NFA 스냅샷 하나와 active state 집합 하나. Build trace (NFA 가 자라는 과정) 와 Run trace (NFA 는 고정, active 가 변함) 가 하나의 포맷을 공유 합니다.
• React TraceViewer 컴포넌트 — 200 줄 언저리. trace.json 을 받아 dagre 로 레이아웃 계산하고 SVG 를 직접 렌더. step slider 달아서 독자가 시간을 스크럽 한다. 위의 뷰어가 그것.
• MDX 포스트 — 서술 + <TraceViewer trace={...} /> 를 inline embed. 이 글이 그 첫 번째 입니다.

Repo: github.com/Ricci-curvature/regex-viz

이 글은 Stage 1 을 3 개 commit 으로 쪼개서 1:1 매핑 합니다.

Stage 0 — 결정 다섯 개

Commit: 5a07588 — readme: initial scaffold

코드 한 줄 없는 커밋. README.md 와 .gitignore 뿐. 그런데 이 커밋이 이후 Stage 1-6 의 모든 제약을 고정합니다. Stage 0은 문서 작성이 아니라 결정 다섯 개 였습니다.

1. Repo 이름: regex-viz. "regex engine" 이 아닙니다. engine 을 만들려는 유혹이 반복해서 올 텐데, 이름으로 막아둡니다.
2. 그래프 레이아웃: dagre. React Flow (@xyflow/react), viz.js (graphviz WASM), vis-network 을 후보로 검토하고 전부 탈락. 이유 — 이 프로젝트의 핵심은 "오토마타를 이해되게 보여주기" 지 "노드 에디터 UX" 가 아니기 때문. dagre 는 layout 계산만 하고 SVG 는 직접 렌더 — 위의 뷰어가 바로 그 결과물입니다. 하이라이트 색/점선/애니메이션 모두 내 손으로 조절 가능.
3. Rust edition 2024 stable. rustc 1.94.0 기준.
4. CI 초반 생략. tools/build_artifacts.sh 하나로 모든 artifact 가 재생성 가능해야 합니다. CI 는 나중에 "artifact 최신 여부 검증" 용으로만 붙입니다.
5. 블로그 포스트 위치: riccilab.dev repo 의 MDX. 이 글입니다. regex-viz repo 바깥. 이 repo 의 blog/ 폴더는 drafting 용이고 .gitignore 에 올라가 있습니다.

README.md 에 박은 아키텍처 다이어그램:

regex-viz/
├── Cargo.toml
├── src/
│   ├── lib.rs
│   ├── parser.rs           ← regex string → AST (recursive descent, ~160 loc)
│   ├── nfa.rs              ← AST → NFA (Thompson construction, ~210 loc)
│   ├── dfa.rs              ← subset construction (Stage 3)
│   ├── matcher.rs          ← NFA sim + backtracker (Stage 2 / 4)
│   └── trace.rs            ← Trace / Step / Nfa serde types
├── examples/
│   └── 01_build_nfa.rs     ← CLI: regex → build-trace JSON
├── artifacts/
│   └── stage01/*.json      ← committed, pinned traces (7 개)
├── viz/
│   ├── trace.ts            ← TypeScript mirror of trace.rs
│   ├── NfaGraph.tsx        ← dagre layout + hand-rolled SVG
│   └── TraceViewer.tsx     ← step slider + NfaGraph
└── tools/
    └── build_artifacts.sh

이 글의 모든 뷰어는 viz/TraceViewer.tsx 한 컴포넌트가, artifacts/stage01/ 의 JSON 파일 하나씩을 먹어서 렌더합니다.

Stage 1 — Thompson's Construction, Visible

Commit: 9f037d8 — stage 01: Thompson's construction with build trace

Rust 쪽 8 개 파일, 679 줄. 외부 의존성은 serde 와 serde_json 둘뿐.

Trace 포맷 먼저

타입을 먼저 고정하면 이후 파서/NFA 구현이 "무엇을 emit 해야 하는지" 를 알게 됩니다. src/trace.rs:

#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "lowercase")]
pub enum TraceKind { Build, Run }
 
pub struct Trace {
    pub kind: TraceKind,
    pub input: Option<String>,
    pub steps: Vec<Step>,
}
 
pub struct Step {
    pub description: String,
    pub nfa: Nfa,
    pub active: Vec<usize>,
    pub input_pos: Option<usize>,
}
 
pub struct Nfa {
    pub states: Vec<usize>,
    pub transitions: Vec<Transition>,
    pub start: usize,
    pub accept: usize,
}
 
pub struct Transition { pub from: usize, pub to: usize, pub label: String }

Build trace 와 Run trace 가 한 타입을 공유 합니다. 중복이 있습니다. Build 는 매 step 마다 NFA 스냅샷이 다르고 active 가 비어있고, Run 은 NFA 가 모든 step 에서 같고 active 만 변합니다. 그래도 한 React 컴포넌트가 두 종류를 모두 렌더할 수 있다는 이득이 중복을 덮습니다. toy 크기라서 가능한 사치.

TypeScript 쪽에도 동일 타입을 mirror 로 둡니다 — viz/trace.ts:

export type Trace = {
  kind: "build" | "run";
  input: string | null;
  steps: Step[];
};

두 파일이 짝 입니다. 한쪽을 바꾸면 다른 쪽도 바꾸고, artifacts/ 를 regenerate 합니다. 그래서 Trace 포맷 변경은 breaking change 로 취급합니다.

Parser — 100 줄 이하의 recursive descent

src/parser.rs. 문법은 PEG 스타일로:

alt    := concat ('|' concat)*
concat := repeat+
repeat := atom ('*' | '+' | '?')?
atom   := literal | '(' alt ')'

AST 는 flat 합니다. Alt(Vec<Ast>), Concat(Vec<Ast>), Star/Plus/Question(Box<Ast>), Literal(char). capture group 없음 — 단순 그루핑은 파싱 단계에서 투명하게 ('(' alt ')' 가 안쪽 AST 를 그대로 반환) 처리합니다. 괄호가 AST 에 남지 않습니다.

테스트 precedence_alt_lower_than_concat_and_star 가 검증하는 것:

// "a|b*c" → Alt[a, Concat[Star(b), c]]
assert_eq!(
    parse("a|b*c").unwrap(),
    Ast::Alt(vec![
        lit('a'),
        Ast::Concat(vec![Ast::Star(Box::new(lit('b'))), lit('c')])
    ])
);

| 의 우선순위가 concat 과 * 보다 낮습니다. recursive descent 는 "높은 우선순위를 안쪽 함수로" 놓으면 자연스럽게 맞습니다. parse_alt → parse_concat → parse_repeat → parse_atom. 트리 깊이 = 우선순위 역순.

Thompson 의 여섯 규칙, 보면서 읽기

src/nfa.rs. Builder 가 글로벌 state ID 카운터 하나 (next_id) 와 flat 한 transition 리스트 (transitions) 를 들고 있습니다. AST 를 재귀로 내려가면서 Fragment { start, accept } 를 반환하고, 매 AST 노드가 끝날 때마다 한 Step 을 emit 합니다.

fn emit(&mut self, description: impl Into<String>, frag: Fragment) {
    let nfa = self.snapshot(frag);
    self.steps.push(Step {
        description: description.into(),
        nfa,
        active: Vec::new(),
        input_pos: None,
    });
}

snapshot 은 누적 입니다. 지금까지 할당된 모든 state, 지금까지 추가된 모든 transition, 그리고 현재 fragment 의 endpoints 를 start/accept 로. 즉 a|b 의 두 번째 step ("literal 'b'") 에서도 화면에는 왼쪽에 a 조각이 같이 보입니다 — 아래 뷰어로 직접 확인 해 봅시다.

여섯 규칙을 하나씩.

1. Literal

Ast::Literal(c) => {
    let s = self.new_state();
    let a = self.new_state();
    self.add_transition(s, a, &c.to_string());
    let frag = Fragment { start: s, accept: a };
    self.emit(format!("literal '{}'", c), frag);
    frag
}

두 state, 한 transition. Trace 의 최소 단위.

2. Concat — ε-link

Ast::Concat(items) => {
    let mut iter = items.iter();
    let mut cur = self.build(iter.next().expect("concat is non-empty"));
    for item in iter {
        let next = self.build(item);
        self.add_transition(cur.accept, next.start, EPSILON);
        cur = Fragment { start: cur.start, accept: next.accept };
        self.emit("concat (ε-link)", cur);
    }
    cur
}

left 의 accept 에서 right 의 start 로 ε transition 하나. 그게 전부. Thompson 의 고전적 방식은 두 state 를 merge 하는 버전도 있는데, ε 하나로 두면 build trace 에서 "어디가 이어졌는지" 가 눈에 보입니다. 시각화를 위해 ε 을 명시적으로 남기기.

세 step. 마지막 step 의 state 1 → 2 점선 ε 이 이 규칙의 결과물.

3. Alternation — 4 ε

Ast::Alt(branches) => {
    let frags: Vec<Fragment> = branches.iter().map(|b| self.build(b)).collect();
    let new_start = self.new_state();
    let new_accept = self.new_state();
    for f in &frags {
        self.add_transition(new_start, f.start, EPSILON);
        self.add_transition(f.accept, new_accept, EPSILON);
    }
    let frag = Fragment { start: new_start, accept: new_accept };
    self.emit("alternation", frag);
    frag
}

state 4 가 새 start, 5 가 새 accept. 안쪽 두 fragment (0→1, 2→3) 는 건드리지 않고, ε 네 개로 감싸기만 합니다.

4. Star — 4 ε, loopback + bypass

Ast::Star(inner) => {
    let f = self.build(inner);
    let new_start = self.new_state();
    let new_accept = self.new_state();
    self.add_transition(new_start, f.start, EPSILON);
    self.add_transition(new_start, new_accept, EPSILON);
    self.add_transition(f.accept, f.start, EPSILON);
    self.add_transition(f.accept, new_accept, EPSILON);
    ...
}

네 ε:

• new_start → f.start — 진입
• new_start → new_accept — bypass (0 번 매칭)
• f.accept → f.start — loopback (한 번 더)
• f.accept → new_accept — 종료

bypass 덕분에 a* 가 빈 문자열을 삼킵니다.

5. Plus — 2 ε, loopback + exit only

Ast::Plus(inner) => {
    let f = self.build(inner);
    let new_accept = self.new_state();
    self.add_transition(f.accept, f.start, EPSILON);
    self.add_transition(f.accept, new_accept, EPSILON);
    let frag = Fragment { start: f.start, accept: new_accept };
    ...
}

star 와 다른 점: bypass 없음, new_start 도 없음. Plus 는 "최소 한 번" 이므로 빈 문자열을 허용하면 안 됩니다. inner 의 start 를 그대로 재사용 — 반드시 inner 를 적어도 한 번 통과해야 합니다.

start 노드가 새로 생기지 않고 state 0 이 그대로 start 로 남아있는 것을 확인.

6. Question — 3 ε

Ast::Question(inner) => {
    let f = self.build(inner);
    let new_start = self.new_state();
    let new_accept = self.new_state();
    self.add_transition(new_start, f.start, EPSILON);
    self.add_transition(new_start, new_accept, EPSILON);
    self.add_transition(f.accept, new_accept, EPSILON);
    ...
}

star 에서 loopback 만 뺀 모양. 0 번 혹은 1 번. Stage 1 의 pinned artifact 에는 ? 케이스를 따로 두지 않았습니다 — star / plus 를 이해하면 question 은 자명하기 때문. 굳이 보고 싶다면 cargo run --example 01_build_nfa -- "a?".

중첩 — (a|b)*

여섯 규칙은 composable 합니다. alternation 과 star 가 중첩되면:

step 1-3 에서 a|b 가 먼저 만들어지고, step 4 에서 그 전체를 star 가 감쌉니다. 중첩 하나에 state 두 개 (새 start, 새 accept) 만 추가되면서 ε 네 개로 구조가 확장됩니다.

Stage 1 — Pinned Artifacts

Commit: 8ca4a8f — artifacts: regenerate stage01

일곱 개 regex, 일곱 개 JSON. repo 에 커밋.

stage01_names=(a ab a_or_b a_star a_plus a_or_b_star a_or_b_star_c)
stage01_regex=('a' 'ab' 'a|b' 'a*' 'a+' '(a|b)*' 'a|b*c')

pinning 의 의미

artifact 는 정적 파일입니다. 이 MDX 는 특정 commit 의 JSON 을 import 해서 <TraceViewer /> 에 먹입니다. 즉 이 블로그 포스트는 8ca4a8f 에 고정 되어 있습니다. Stage 1 코드가 나중에 수정돼도 이 글의 시각화는 바뀌지 않습니다. 글과 코드의 시간을 분리하는 장치.

Trace 포맷이 바뀌면 artifacts/ 전체를 regenerate 해야 합니다. 그리고 관련 블로그 포스트도 함께 업데이트해야 합니다. 그래서 포맷 변경은 breaking change 로 취급하고, 코드 변경과 절대 섞지 않습니다. (artifacts: commit 이 code commit 과 분리된 이유).

다시 — a|b*c

맨 위의 메인 뷰어를 다시 보면, 이제는 각 step 이 어떤 규칙의 결과인지 보입니다.

1. literal 'a' — state 0, 1
2. literal 'b' — state 2, 3
3. star (a*) — state 4, 5 추가. b 를 네 ε 로 감싸기
4. literal 'c' — state 6, 7
5. concat (ε-link) — b* 의 accept (5) → c 의 start (6) ε
6. alternation — state 8, 9 추가. a 쪽과 b*c 쪽을 네 ε 로 감쌈

타임라인으로 읽으면 AST 의 후위 순회가 그대로 보입니다: a → b → b* → c → b*c → a|(b*c). 이게 Thompson construction 을 "보는" 것.

Stage 1 — Viewer

Commit: 700ef10 — stage 01: viz components (TraceViewer + NfaGraph)

지금까지 이 글에서 본 모든 뷰어가 이 한 commit 의 산물이다. 4 개 파일, 351 줄.

viz/
├── trace.ts         ← src/trace.rs 의 TypeScript mirror (~30 loc)
├── NfaGraph.tsx     ← dagre layout + hand-rolled SVG (~120 loc)
├── TraceViewer.tsx  ← step slider + NfaGraph composition (~90 loc)
└── README.md        ← vendor 가이드

왜 source-only vendor 일까?

이 repo 에는 package.json 이 없습니다. node_modules 도 없습니다. viz 는 .tsx 소스 네 개만 커밋하고, blog repo (riccilab.dev) 가 이것들을 vendor — symlink 하거나 복사해서 자신의 빌드 파이프라인에 태웁니다.

이유 두 가지:

1. 이 repo 의 관심사는 Rust + trace JSON. React/Vite/Next 설정으로 오염시키면 regex-viz 가 두 개의 빌드 시스템을 떠안습니다. "Rust 는 계산, React 는 렌더" 원칙에서 의존성은 각자 자기 쪽에.
2. Stage 안정화 전 API 가 흔들림. TraceViewer 의 props 시그니처, NfaGraph 의 style hook 지점, dagre 버전 고정. 이 중 어느 것도 아직 확정 못 했습니다. npm 패키지로 올리면 semver 감옥에 갇히고, vendor 방식은 blog 쪽이 직접 파일을 들고 있으므로 breaking change 를 한 repo 안에서 원자적으로 해결할 수 있습니다.

안정화된 후에 @regex-viz/viewer npm 패키지로 올리는 건 Stage 6 이후에 재검토 — 그때도 "올릴 이유" 가 분명하지 않으면 vendor 그대로.

역할 분담

NfaGraph 는 { nfa, active } 를 받아 한 순간의 자동자 그림을 냅니다. dagre 는 순전히 좌표 계산용 — 노드 크기 (36×36), 방향 (rankdir: 'LR'), 간격만 알려주면 각 노드의 { x, y } 와 edge 의 points 배열을 돌려줍니다. 그걸 받아서 <circle> / <path> / <text> 로 SVG 를 직접 짜기. hover effect, accept state 의 이중원, ε edge 의 점선 — 전부 JSX 안에서 inline.

TraceViewer 는 NfaGraph 를 중심에 놓고 step slider 와 description bar 를 두릅니다. useState(stepIdx), 그게 전부. Build / Run trace 둘 다 먹는데, trace.kind === "run" 일 때만 InputStrip (입력 문자열의 현재 위치 하이라이트) 이 추가로 렌더됩니다. Stage 2 가 오면 이 한 컴포넌트가 그대로 재사용.

// TODO: verify 두 곳

NfaGraph.tsx 에 // TODO: verify 주석 두 개를 남겼습니다. 둘 다 dagre 관련이고, blog repo 에서 첫 렌더가 성공하는 순간 확정.

1. dagre 를 default import (import dagre from "dagre") 로 쓸지, 아니면 @dagrejs/dagre (modern fork) 에서 namespace import 로 바꿀지.
2. 병렬 ε-edge 를 지원하기 위해 multigraph: true 로 그래프를 만들고, edge 조회를 g.edge(v, w, name) 3-인자 형태로 합니다. 이 API 가 현재 dagre 릴리즈에서 여전히 표준인지.

자신 없는 부분을 "자신 있는 척" 넘기지 말자는 게 이 프로젝트의 규칙이고, 그래서 흔적을 남겼습니다. blog vendor 에서 첫 렌더가 통과하면 TODO 를 지우고 commit 한 줄.

Lessons

세 가지 찝찝함이 남습니다.

1. Snapshot 누적의 trade-off. build trace 는 현재까지의 전체 NFA 를 매 step 에 다시 싣습니다. 작은 regex 에서는 직관적이지만, trace 가 커질수록 JSON 이 quadratic 으로 부풀 수 있습니다. Stage 3 에서 NFA→DFA mapping trace 를 만들 때 다시 판단. 필요하면 delta 모드를 Trace 포맷에 추가.

2. ε 를 유니코드 그대로 "ε". JSON 가독성은 좋지만, 나중에 label 에 backslash escape 같은 게 끼어들면 깨질 수 있습니다. 지금은 OK, 확장 시 재검토.

3. Plus 가 new_start 를 만들지 않습니다. Thompson 의 "모든 fragment 는 새 start/accept 를 가진다" 라는 관습을 깹니다. 이유는 빈 문자열 거부. inner 의 start 를 재사용해야 "반드시 한 번" 이 보장됩니다. 대신 Plus 의 fragment 가 외부에서 다시 wrap 될 때 inner 와 state 를 공유한다는 점을 기억해둬야 합니다. 테스트 every_step_snapshot_is_self_consistent 가 이 경우도 검증.

다음 — Stage 2

NFA matching trace. 고정된 NFA, 움직이는 active 집합. run trace.

• src/matcher.rs — subset-state advance (backtracking 없이). 각 step 마다 ε-closure 를 취하고 한 글자 읽고 다음 집합으로.
• examples/02_run_nfa.rs — regex + input → run-trace JSON.
• Pin: 3-5 regex × 2-3 input 조합 (match / mismatch / partial).

같은 <TraceViewer /> 가 Stage 2 뷰어가 됩니다. 이미 trace.kind === "run" 분기가 컴포넌트 안에 있습니다. 달라지는 건 NFA 가 고정되고 slider 가 "AST 노드" 가 아니라 "입력 문자 하나" 를 넘긴다는 것. active 집합이 노드에 노란 하이라이트로 보이고, input_pos 가 입력 스트립에서 움직입니다.

Stage 4 에서 동일한 regex 를 backtracker 로도 돌릴 예정. 같은 run trace 포맷 위에 두 엔진을 나란히 놓기. (a+)+b on aaaaaaaaaa! — backtracker 가 몇 천 step, NFA 가 몇 십 step. 그 비교가 Stage 4 의 pitch.

Repo 전체: github.com/Ricci-curvature/regex-viz 이번 stage 의 커밋 네 개:

• 5a07588 — readme: initial scaffold
• 9f037d8 — stage 01: Thompson's construction with build trace
• 8ca4a8f — artifacts: regenerate stage01
• 700ef10 — stage 01: viz components (TraceViewer + NfaGraph)