正規表現エンジンの内部（NFA・DFA・バックトラッキング）

2つの実装系統と、この記事の射程

正規表現の照合エンジンには、計算理論上まったく異なる2系統があります。ひとつはオートマトン系（GNU grep、RE2、Go の regexp、Rust の regex）で、有限オートマトンに変換して入力を一回走査します。もうひとつはバックトラッキング系（PCRE、Perl、Python の re、JavaScript、Java、.NET）で、パターンを再帰的に試行し、失敗したら戻って別の選択肢を試します。

両者は同じ「正規表現」を受け付けるように見えますが、内部の計算モデルが違うため、最悪計算量も、扱える機能も異なります。基本的な記法そのものは「正規表現」で扱っているので、本稿はその内部実装に絞ります。

Thompson NFA 構成

Ken Thompson が示した構成法は、正規表現を**ε（イプシロン）遷移つき非決定性有限オートマトン（NFA）**へ機械的に変換します。ε遷移とは「文字を消費せずに移動できる辺」です。各部分式を、入口1つ・出口1つを持つ小さなNFA部品に対応させ、それを再帰的に組み合わせます。

• 連接 AB — A の出口を B の入口へ ε で繋ぐ。
• 選択 A|B — 新しい入口から A・B 双方へ ε で分岐し、両出口を新しい出口へ ε で合流。
• 繰り返し A* — 入口から出口へ ε（0回）、出口から入口へ ε（再ループ）。

この構成では、各演算子が定数個の状態と辺を追加するだけなので、パターン長 m に対し状態数も辺数も O(m) に収まります。重要なのは、バックトラッキングせずに照合できる点です。

パターン a(b|c)*d の照合（Thompson NFA）

「現在いる可能性のある状態の集合」を1つ持ち、入力を1文字読むたびに
集合全体をまとめて次へ進める。分岐は集合の要素として並走させる。

状態集合 = {S0}
'a' を読む → {S1, S2, S5}   ← εで到達できる状態も含める
'b' を読む → {S3, S2, S5}
...

非決定性とは「複数の選択肢を同時に保持する」ことであり、実装上は到達可能な状態の集合を1つ持ち、入力1文字ごとに集合を一括更新します。状態集合の大きさは高々 m 個なので、入力長 n に対し全体で O(n × m)。指数爆発は起きません。

部分集合構成による DFA 化

NFA の「状態集合を持ち回る」処理を事前に展開しておけば、照合時は状態を1つ持って表を引くだけで済みます。これが**決定性有限オートマトン（DFA）で、NFA から DFA への変換を部分集合構成（subset construction）**と呼びます。

考え方は単純です。NFA の「到達可能な状態集合」そのものを、DFA の1状態とみなします。集合 {S1,S2,S5} から文字 b で行ける集合が {S3,S2,S5} なら、DFA ではこの2つの集合を別々のノードとし、その間に b の辺を1本引きます。

DFA の照合は入力1文字につき遷移表を1回引くだけなので O(n) です。ただし対価があります。NFA の状態が m 個なら、その部分集合は最大で 2ᵐ 通り存在しうるため、DFA の状態数は最悪で指数的に膨れます。

なぜオートマトン系は後方参照を持たないのか。後方参照は「前に一致した実際の文字列」を記憶して再照合する機能で、これは有限個の状態では表現できません（記憶すべき文字列が無限通り）。DFA/NFA は定義上、有限状態しか持てないため、原理的に実装できないのです。

バックトラッキングと破滅的計算量（ReDoS）

PCRE 系のエンジンは、オートマトンを作らずパターンを再帰的に解釈します。A|B なら「まず A を試し、行き詰まったら入力位置を巻き戻して B を試す」。量指定子 A* なら「できるだけ多く A を取り、後続が失敗したら1回ずつ戻して再試行」。この**戻り（バックトラック）**こそが系統名の由来です。

この方式は後方参照や可変長先読みを自然に扱える反面、入力によっては試行の組み合わせが指数的に増えます。典型例が入れ子になった量指定子です。

危険なパターン:  (a+)+$
危険な入力:      "aaaa...a!"   ← 末尾に $ にマッチしない文字

内側 a+ と外側 (...)+ が、同じ a の並びを「どこで区切るか」で
膨大な分割パターンを持つ。末尾の '!' で必ず失敗するため、
エンジンは全分割を総当たりし、入力長 n に対し試行回数が O(2ⁿ) に達する。

これが**破滅的バックトラッキング（catastrophic backtracking）であり、これを悪用してサーバーを止める攻撃をReDoS（Regular expression Denial of Service）**と呼びます。計算量の指数爆発そのものなので、考え方は「計算量と Big-O 記法」の O(2ⁿ) と同じです。短い入力でも CPU を100%張り付かせ、リクエスト1本でプロセスを実質停止させられます。

なぜ系統が分かれるのか、どう選ぶか

機能と安全性はトレードオフです。後方参照や任意先読みが要るなら、表現力の高いバックトラッキング系を使うしかありません。逆に、それらが不要で入力が信頼できない（外部から来る）なら、RE2・Go・Rust のような線形時間保証のあるオートマトン系を選ぶのが安全です。RE2 が後方参照を意図的にサポートしないのは、線形時間保証を崩さないための設計判断です。実装方式の違いが言語処理系全般の設計思想に通じる点は「コンパイルとインタプリタ」とも重なります。

バックトラッキング系をやむを得ず使う場合の実務的防御は次の通りです。

• 入れ子量指定子を避け、あいまいさのないパターンに書き換える（例 (a+)+ → a+）。
• 量指定子に上限を付ける（a{1,100} のように有界化する）。
• エンジン側のタイムアウト（.NET の Regex タイムアウト、Java での実行時間監視）を設定する。
• 信頼境界を越える入力には、可能なら RE2 系エンジンへ切り替える。

なお、状態集合や遷移表といった内部表現は集合・写像で扱われます。エンジンの効率は、こうした「データ構造（配列・リスト・スタック・キュー・マップ）」の選択（遷移表を配列にするかハッシュにするか等）にも依存します。

まとめ

正規表現エンジンは、オートマトン系とバックトラッキング系に大別されます。Thompson NFA は正規表現を線形サイズの ε-NFA に変換し、状態集合を持ち回ることで O(n×m) の安定した照合を実現します。部分集合構成で DFA 化すれば照合は O(n) になりますが、状態数が最悪 O(2ᵐ) に爆発するため、実用エンジンは遅延DFAで回避します。一方、表現力に優れるバックトラッキング系は、入れ子量指定子などで O(2ⁿ) の破滅的バックトラッキング、すなわち ReDoS を招きます。「速い時と固まる時がある」のは気のせいではなく、選んだエンジンの計算モデルの帰結なのです。