正規表現(NFA / DFA と Thompson 構成)

多くの言語の正規表現はバックトラッキングで動き、a(a|aa)*b のような式に悪い入力を与えると処理時間が指数的に膨れ上がる(ReDoS)。この章はオートマトンに基づく別系統のエンジンを作る。正規表現をパースして AST にし、Thompson 構成で NFA に変換し、状態集合を並行に進めてマッチする。今いる状態を集合として持つのでバックトラッキングが要らず、入力長に比例した時間で済む。

この章で作るもの

正規表現エンジンには大きく 2 系統ある。1 つはバックトラッキング型で、多くの言語の標準実装がこれだ。分岐のたびに 1 つを試し、失敗したら戻ってやり直す。後方参照のような強力な機能を書けるが、(a*)*b のような式に長い非マッチ入力を与えると、試す組み合わせが指数的に増えて実用にならない(ReDoS)。

もう 1 つが、この章で作るオートマトン型だ。正規表現をいったん NFA(非決定性有限オートマトン)に変換し、「今いる状態の集合」を丸ごと持って入力を 1 文字ずつ進める。複数の状態に同時にいられるので、どの分岐を選ぶかを試して戻る必要がない。時間は入力長に比例する。流れは 3 段で、lang 編の「字句 → 構文 → 評価」と同じ骨格をしている。

  "(a|b)*abb"
       │  パース(再帰下降)
       ▼
   AST(構文木)         Concat(Star(Alt(a,b)), a, b, b)
       │  Thompson 構成
       ▼
   NFA(ε 遷移つき)      状態集合を並行に進める(バックトラッキング無し)
       │  部分集合構成
       ▼
   DFA(ε 無し)          状態が常に 1 つ。1 文字あたり表引き 1 回

正規表現エンジンのパイプライン。文字列を AST にパースし、Thompson 構成で ε 遷移付きの NFA にし、状態集合として並行に動かす。あるいは部分集合構成で DFA に変換して 1 文字 1 表引きにする。各段は前段の出力だけを入力に取る

順に見ていく。

1. パース: 正規表現を AST にする。優先順位は選択(|)< 連接 < 繰り返し(* + ?)
2. Thompson 構成: 各演算子に対応する小さな NFA 断片を ε 遷移で組み合わせ、木全体の NFA を作る
3. シミュレーションと DFA 化: NFA を状態集合として進める(入力長に比例)。あるいは DFA(決定性有限オートマトン。いる状態が常に 1 つ)に変換して 1 文字 1 表引きにする

① パース: 正規表現 → AST

まず文字列を構文木にする。ノードはリテラル・任意文字(.)・空・連接・選択・繰り返し(* + ?)の 7 種:

// Node は正規表現の構文木のノード。
type Node interface{ isNode() }

// Lit は 1 文字リテラル。Any は任意 1 文字(.)。Empty は空(ε)。
type Lit struct{ Ch byte }
type Any struct{}
type Empty struct{}

// Concat は連接(L の後に R)。Alt は選択(L か R)。
type Concat struct{ L, R Node }
type Alt struct{ L, R Node }

// Star は 0 回以上、Plus は 1 回以上、Quest は 0 か 1 回の繰り返し。
type Star struct{ X Node }
type Plus struct{ X Node }
type Quest struct{ X Node }

func (Lit) isNode()    {}
func (Any) isNode()    {}
func (Empty) isNode()  {}
func (Concat) isNode() {}
func (Alt) isNode()    {}
func (Star) isNode()   {}
func (Plus) isNode()   {}
func (Quest) isNode()  {}

パーサは再帰下降で、優先順位の低い順に関数を重ねる。alt(選択)が一番外で、その中に concat(連接)、さらに内側に repeat(繰り返し)、最内が atom(リテラルやグループ)。この入れ子が、そのまま「繰り返しが最も強く結びつく」優先順位を表す:

// Parse は正規表現の文字列を AST にする。再帰下降パーサで、優先順位は
// 選択(|)< 連接 < 繰り返し(* + ?)の順(繰り返しが最も強く結びつく)。
// 対応構文: リテラル・. ・グループ () ・選択 | ・繰り返し * + ?。
func Parse(pattern string) (Node, error) {
	p := &parser{src: pattern}
	n, err := p.alt()
	if err != nil {
		return nil, err
	}
	if p.pos != len(p.src) {
		return nil, fmt.Errorf("%w: 余分な文字 %q", ErrSyntax, p.src[p.pos:])
	}
	return n, nil
}

type parser struct {
	src string
	pos int
}

func (p *parser) peek() byte {
	if p.pos >= len(p.src) {
		return 0
	}
	return p.src[p.pos]
}

// alt は選択。concat を | で繋ぐ(最も弱い結合)。
func (p *parser) alt() (Node, error) {
	left, err := p.concat()
	if err != nil {
		return nil, err
	}
	for p.peek() == '|' {
		p.pos++
		right, err := p.concat()
		if err != nil {
			return nil, err
		}
		left = Alt{L: left, R: right}
	}
	return left, nil
}

// concat は連接。| ) か終端に当たるまで repeat を並べる。空なら Empty(ε)。
func (p *parser) concat() (Node, error) {
	var nodes []Node
	for {
		c := p.peek()
		if c == 0 || c == '|' || c == ')' {
			break
		}
		n, err := p.repeat()
		if err != nil {
			return nil, err
		}
		nodes = append(nodes, n)
	}
	if len(nodes) == 0 {
		return Empty{}, nil
	}
	left := nodes[0]
	for _, n := range nodes[1:] {
		left = Concat{L: left, R: n}
	}
	return left, nil
}

// repeat は後置の * + ? を atom に重ねる。
func (p *parser) repeat() (Node, error) {
	a, err := p.atom()
	if err != nil {
		return nil, err
	}
	for {
		switch p.peek() {
		case '*':
			p.pos++
			a = Star{X: a}
		case '+':
			p.pos++
			a = Plus{X: a}
		case '?':
			p.pos++
			a = Quest{X: a}
		default:
			return a, nil
		}
	}
}

// atom はグループ () ・任意文字 . ・リテラル 1 文字。
func (p *parser) atom() (Node, error) {
	switch c := p.peek(); c {
	case 0, '|', ')':
		return nil, fmt.Errorf("%w: 式が必要な位置 %d", ErrSyntax, p.pos)
	case '(':
		p.pos++
		n, err := p.alt()
		if err != nil {
			return nil, err
		}
		if p.peek() != ')' {
			return nil, fmt.Errorf("%w: 閉じ括弧が無い", ErrSyntax)
		}
		p.pos++
		return n, nil
	case '.':
		p.pos++
		return Any{}, nil
	case '*', '+', '?':
		return nil, fmt.Errorf("%w: 繰り返しの対象が無い(位置 %d)", ErrSyntax, p.pos)
	default:
		p.pos++
		return Lit{Ch: c}, nil
	}
}

concat が中身の無いときに Empty(ε)を返すのが地味に効く。a| のように選択の片側が空の式や、空パターンが自然に扱える。

② Thompson 構成: AST → NFA

ここが中心だ。1968 年に Ken Thompson が示した方法で、各演算子に対応する小さな NFA の断片を作り、ε 遷移で繋いでいく。ε 遷移は「入力を消費せずに状態を移れる」特別な辺で、断片どうしを糊付けする役割を持つ:

type builder struct {
	trans [][]edge
}

func (b *builder) newState() int {
	b.trans = append(b.trans, nil)
	return len(b.trans) - 1
}
func (b *builder) link(from int, e edge) { b.trans[from] = append(b.trans[from], e) }

// frag は構成途中の NFA 断片(開始と受理が 1 つずつ)。
type frag struct{ start, accept int }

// Build は AST を Thompson 構成で NFA にする。各ノード型に対応する断片を作り、
// ε 遷移で繋いでいく。ここが「正規表現 → オートマトン」の心臓部。
func Build(n Node) *NFA {
	b := &builder{}
	f := b.build(n)
	return &NFA{start: f.start, accept: f.accept, trans: b.trans}
}

func (b *builder) build(n Node) frag {
	switch v := n.(type) {
	case Lit: // s --ch--> a
		s, a := b.newState(), b.newState()
		b.link(s, edge{to: a, ch: v.Ch})
		return frag{s, a}
	case Any: // s --.--> a
		s, a := b.newState(), b.newState()
		b.link(s, edge{to: a, any: true})
		return frag{s, a}
	case Empty: // s --ε--> a
		s, a := b.newState(), b.newState()
		b.link(s, edge{to: a, eps: true})
		return frag{s, a}
	case Concat: // L の受理 --ε--> R の開始
		l, r := b.build(v.L), b.build(v.R)
		b.link(l.accept, edge{to: r.start, eps: true})
		return frag{l.start, r.accept}
	case Alt: // 新開始から両方へ ε、両受理から新受理へ ε
		s, a := b.newState(), b.newState()
		l, r := b.build(v.L), b.build(v.R)
		b.link(s, edge{to: l.start, eps: true})
		b.link(s, edge{to: r.start, eps: true})
		b.link(l.accept, edge{to: a, eps: true})
		b.link(r.accept, edge{to: a, eps: true})
		return frag{s, a}
	case Star: // 0 回以上: 入口で本体を飛ばせ、本体後は戻れる
		s, a := b.newState(), b.newState()
		x := b.build(v.X)
		b.link(s, edge{to: x.start, eps: true})
		b.link(s, edge{to: a, eps: true})              // 0 回(本体を飛ばす)
		b.link(x.accept, edge{to: x.start, eps: true}) // 繰り返す
		b.link(x.accept, edge{to: a, eps: true})       // 抜ける
		return frag{s, a}
	case Plus: // 1 回以上: 必ず本体を通り、その後は繰り返しか脱出
		x := b.build(v.X)
		a := b.newState()
		b.link(x.accept, edge{to: x.start, eps: true})
		b.link(x.accept, edge{to: a, eps: true})
		return frag{x.start, a}
	case Quest: // 0 か 1 回: 本体を通るか飛ばすか
		s, a := b.newState(), b.newState()
		x := b.build(v.X)
		b.link(s, edge{to: x.start, eps: true})
		b.link(s, edge{to: a, eps: true})
		b.link(x.accept, edge{to: a, eps: true})
		return frag{s, a}
	default:
		panic("regex: 未知の AST ノード")
	}
}

規則は演算子ごとに決まっている。リテラルはその文字の辺 1 本。連接は左の受理から右の開始へ ε。選択は新しい開始から両方へ ε を分岐させ、両方の受理を新しい受理へ ε で集める。繰り返し(*)は「本体を飛ばす ε」と「本体後に戻る ε」を足す。どの断片も開始と受理が 1 つずつなので、上位の規則がそれをそのまま部品として使える。木を一度歩くだけで、機械的に NFA が組み上がる。

③ シミュレーション: 状態集合を並行に進める

NFA は「同じ入力に対して複数の状態にいられる」オートマトンだ。マッチはこの非決定性を、状態の集合として持つことで扱う。まず開始状態の ε 閉包(ε 遷移だけで到達できる状態を全部集めたもの)を求め、入力を 1 文字読むごとに、集合内の全状態から進める先を集め、また ε 閉包する:

// epsClosure は与えた状態集合から ε 遷移だけで到達できる状態を全て加えた集合を返す。
// 「入力を消費せずに今いられる全状態」を求める操作で、シミュレーションの各ステップで使う。
func (n *NFA) epsClosure(states map[int]bool) map[int]bool {
	stack := make([]int, 0, len(states))
	closure := make(map[int]bool, len(states))
	for s := range states {
		closure[s] = true
		stack = append(stack, s)
	}
	for len(stack) > 0 {
		s := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		for _, e := range n.trans[s] {
			if e.eps && !closure[e.to] {
				closure[e.to] = true
				stack = append(stack, e.to)
			}
		}
	}
	return closure
}

// Match は入力全体がこの NFA にマッチするかを返す。今いる状態集合を ε 閉包で広げ、
// 入力を 1 文字読むごとに「その文字で進める遷移」を全状態について集め、また ε 閉包する。
// バックトラッキングは無い——集合を並行に進めるだけなので、時間は入力長に比例する。
func (n *NFA) Match(input string) bool {
	cur := n.epsClosure(map[int]bool{n.start: true})
	for i := 0; i < len(input); i++ {
		c := input[i]
		next := make(map[int]bool)
		for s := range cur {
			for _, e := range n.trans[s] {
				if e.eps {
					continue
				}
				if e.any || e.ch == c {
					next[e.to] = true
				}
			}
		}
		cur = n.epsClosure(next)
		if len(cur) == 0 {
			return false // どの状態にもいられない = 詰み
		}
	}
	return cur[n.accept]
}

// NumStates は NFA の状態数(表示・検査用)。
func (n *NFA) NumStates() int { return len(n.trans) }

// Regexp はコンパイル済みの正規表現。NFA を持ち、必要になったら DFA も作る。
type Regexp struct {
	nfa *NFA
	dfa *DFA
}

// Compile は正規表現をパースし、Thompson 構成で NFA にする。
func Compile(pattern string) (*Regexp, error) {
	ast, err := Parse(pattern)
	if err != nil {
		return nil, err
	}
	return &Regexp{nfa: Build(ast)}, nil
}

// Match は NFA シミュレーションでマッチ判定する。
func (r *Regexp) Match(input string) bool { return r.nfa.Match(input) }

// MatchDFA は NFA を DFA に変換してからマッチ判定する(初回のみ変換)。
func (r *Regexp) MatchDFA(input string) bool {
	if r.dfa == nil {
		r.dfa = ToDFA(r.nfa)
	}
	return r.dfa.Match(input)
}

epsClosure と Match の組み合わせが、バックトラッキングを消す仕掛けだ。「どの分岐を選ぶか」を 1 つずつ試すのではなく、あり得る状態を全部同時に持ち歩く。集合の大きさは NFA の状態数で頭打ちになるので、1 文字の処理は状態数に比例した一定の手間で済む。だから (a*)*b のような式でも指数的に膨れ上がらない。

動かす

下のデモは、この NFA シミュレーションをそのままブラウザで動かしている。パターン (a|b)*abb の NFA を組み、入力を選んで 1 文字ずつ進めると、今いる状態集合がどう動くかが見える。1 文字も読んでいない時点で複数の状態にいること、文字を読むたびに集合が並行に更新されること、そして読み切ったときに受理状態が集合に入っていればマッチすることが分かるはずだ。

デモregex(NFA シミュレーション)step 1

パターン (a|b)*abbababbaabbabab

·ababb

今いる NFA 状態集合 6 states

q0 q1 q2 q4 q6 q8

開始状態の ε 閉包。まだ 1 文字も読んでいないのに、複数の状態に同時にいる

1 / 6

正規表現を NFA に変換し、「今いる状態の集合」を丸ごと持って入力を 1 文字ずつ進める。 複数の状態に同時にいられるので、どの分岐を選ぶかを試して戻る(バックトラッキング)必要が無い。 だから (a*)*b のような式でも指数爆発せず、入力長に比例した時間で判定できる。

DFA 化: 状態集合を 1 つの状態に畳む

NFA シミュレーションは 1 文字ごとに集合の操作(ε 閉包・遷移集め)をやり直す。同じ入力に何度もマッチさせるなら、これを前もって表にしておける。部分集合構成は、NFA の「状態集合」を DFA の「1 つの状態」と見なす方法だ。ε 遷移は変換時に閉包へ畳み込まれて消える:

// DFA は決定的な遷移表。alphabet はパターンに現れるリテラル文字の集合。
// lit[state][c] はその文字での遷移、any[state] は alphabet 外の任意文字での遷移(. 用)。
type DFA struct {
	start    int
	accept   map[int]bool
	lit      []map[byte]int // state -> (文字 -> 次状態)
	any      []int          // state -> 次状態(alphabet 外の文字。無ければ -1)
	alphabet map[byte]bool
}

// ToDFA は NFA を部分集合構成で DFA に変換する。
//
// 開始は NFA 開始の ε 閉包。各 DFA 状態(= NFA 状態の集合)について、alphabet の各文字と
// 「alphabet 外(any)」で遷移先の集合を求め、未知の集合なら新しい DFA 状態にする。
// NFA 状態集合に受理状態が含まれれば、その DFA 状態は受理。
func ToDFA(n *NFA) *DFA {
	alphabet := collectAlphabet(n)
	d := &DFA{accept: map[int]bool{}, alphabet: alphabet}

	ids := map[string]int{} // 状態集合のキー -> DFA 状態 id
	var sets []map[int]bool

	intern := func(set map[int]bool) int {
		key := setKey(set)
		if id, ok := ids[key]; ok {
			return id
		}
		id := len(sets)
		ids[key] = id
		sets = append(sets, set)
		d.lit = append(d.lit, map[byte]int{})
		d.any = append(d.any, -1)
		if set[n.accept] {
			d.accept[id] = true
		}
		return id
	}

	d.start = intern(n.epsClosure(map[int]bool{n.start: true}))

	for work := 0; work < len(sets); work++ {
		set := sets[work]
		// alphabet の各リテラル文字での遷移。any 辺も含めて動く。
		for c := range alphabet {
			if next := n.epsClosure(move(n, set, c, false)); len(next) > 0 {
				d.lit[work][c] = intern(next)
			}
		}
		// alphabet 外の文字での遷移(. の any 辺のみ)。
		if next := n.epsClosure(move(n, set, 0, true)); len(next) > 0 {
			d.any[work] = intern(next)
		}
	}
	return d
}

// move は状態集合から、文字 c で進める先の集合を返す。
// anyOnly が true なら any 辺(.)だけをたどる(alphabet 外の文字の遷移)。
// false なら「c に一致するリテラル辺」と「any 辺」の両方をたどる。
func move(n *NFA, set map[int]bool, c byte, anyOnly bool) map[int]bool {
	out := map[int]bool{}
	for s := range set {
		for _, e := range n.trans[s] {
			if e.eps {
				continue
			}
			if anyOnly {
				if e.any {
					out[e.to] = true
				}
			} else if e.any || e.ch == c {
				out[e.to] = true
			}
		}
	}
	return out
}

// collectAlphabet はパターンに現れるリテラル文字を集める(DFA の入力記号集合)。
func collectAlphabet(n *NFA) map[byte]bool {
	al := map[byte]bool{}
	for _, edges := range n.trans {
		for _, e := range edges {
			if !e.eps && !e.any {
				al[e.ch] = true
			}
		}
	}
	return al
}

// Match は入力全体が DFA にマッチするかを返す。1 文字ごとに表引き 1 回。
// alphabet 内の文字は lit で、外の文字は any で遷移する。行き先が無ければ即不一致。
func (d *DFA) Match(input string) bool {
	st := d.start
	for i := 0; i < len(input); i++ {
		c := input[i]
		var next int
		if d.alphabet[c] {
			n, ok := d.lit[st][c]
			if !ok {
				return false
			}
			next = n
		} else {
			if d.any[st] < 0 {
				return false
			}
			next = d.any[st]
		}
		st = next
	}
	return d.accept[st]
}

// NumStates は DFA の状態数(NFA との比較・表示用)。
func (d *DFA) NumStates() int { return len(d.lit) }

// setKey は状態集合を決定的な文字列キーにする(同じ集合を同じ DFA 状態に対応づけるため)。
func setKey(set map[int]bool) string {
	xs := make([]int, 0, len(set))
	for s := range set {
		xs = append(xs, s)
	}
	sort.Ints(xs)
	parts := make([]string, len(xs))
	for i, s := range xs {
		parts[i] = strconv.Itoa(s)
	}
	return strings.Join(parts, ",")
}

ToDFA は開始集合から始め、各状態集合について入力文字ごとの遷移先集合を求め、未知の集合を新しい DFA 状態として登録していく。できた DFA の Match は、1 文字あたり表引き 1 回だけで進む。集合操作も ε 閉包も要らない。代償は状態数で、最悪では NFA の状態集合の組み合わせだけ、つまり指数的に増えうる。実行の速さとメモリのトレードオフになる。

設計の観点: なぜバックトラッキングを避けるか

• ReDoS: バックトラッキング型は (a+)+$ のような式に非マッチ入力を与えると、分岐の組み合わせを指数的に試して固まる。公開サービスでユーザ入力を正規表現にかけると、これが DoS になる。オートマトン型は状態集合で進むので、この急激な増加が原理的に起きない
• NFA vs DFA: NFA シミュレーションは状態数に比例するメモリで、変換コストが無い。DFA は 1 文字 1 表引きで速いが、構築に時間がかかり状態数が最悪指数的。使い捨ての式は NFA、繰り返し使う式は DFA、という使い分けになる
• なぜ ε 遷移か: Thompson 構成は ε 遷移のおかげで、各演算子を「開始 1 つ・受理 1 つ」の部品として合成できる。合成が単純になる代わりに ε が増えるが、閉包計算や DFA 変換で吸収できる
• バックトラッキングの居場所: 後方参照(\1)や先読みは、オートマトンでは表せずバックトラッキングが要る。だから PCRE 系は表現力を取ってバックトラッキングを選ぶ。RE2(Go の regexp)はオートマトン型で、後方参照を捨てて線形時間を保証する。表現力と最悪計算量のトレードオフ
• 部分マッチと最長一致: 本章は入力全体のマッチに絞ったが、実務は「どこにマッチするか」「最長一致」を扱う。開始位置をずらして試す、あるいは NFA に「任意の前置き」を足すなどで実現する

メリット・デメリットと実例

方式	最悪計算量	表現力	メモリ	実例
バックトラッキング	指数(ReDoS)	高(後方参照・先読み)	小	PCRE、Perl、Python re、JS
NFA シミュレーション	線形 × 状態数	中(標準正規言語)	状態数	RE2 の一系統、本章
DFA	線形(1 文字 1 表引き)	中	状態数が最悪指数	grep(一部)、字句解析器

裏どり:

• RE2 / Go の regexp: オートマトン型で、後方参照を意図的に捨てて線形時間を保証する。ユーザ入力を安全に正規表現へかけられるのが売り。本章と同じ Thompson 系の設計
• PCRE / Perl / Python: バックトラッキング型。後方参照や先読みなど表現力が高い代わりに、(a+)+ 系の式で ReDoS を起こしうる。実際に大規模障害の原因になった例が複数ある
• 字句解析器(lexer): 正規表現から DFA を生成し、トークンを高速に切る。lex/flex はこの DFA 化を使う。lang 編や bytecode 編の字句解析の裏側
• Thompson の原典: 1968 年の論文で、正規表現を機械語に変換して実行する形で NFA シミュレーションを示した。現代のオートマトン型エンジンの源流

簡略化したこと

• 入力全体のマッチのみ: 部分マッチ・最長一致・マッチ位置の取得は扱わない
• 後方参照・先読みなし: これらはオートマトンで表せない。バックトラッキングが要る領域
• 文字クラス・エスケープなし: [a-z]・\d・\. のようなエスケープは未実装。リテラル・.・() | * + ? に絞る
• ASCII バイト単位: マルチバイト文字(UTF-8 のコードポイント単位)は扱わない
• DFA 最小化なし: 部分集合構成までで、等価な状態を併合する最小化(Hopcroft 法)はしない

参考資料

• Ken Thompson, "Regular Expression Search Algorithm"(1968) — NFA シミュレーションの原典
• Russ Cox, "Regular Expression Matching Can Be Simple And Fast" — オートマトン型と ReDoS の定番解説。RE2 の設計思想
• lang 編(字句→構文→評価の同じ骨格)・bytecode 編(字句解析の裏で DFA)と合わせて読むと繋がる
• 実装: foundations/regex