正規表現エンジンを自作する

何を作るか

作るのは、正規表現の文字列を受け取り、対象文字列がマッチするかを判定する最小のエンジンです。対応するのは連接（ab）、和（a|b）、繰り返し（a*）の3演算と、これらを括る丸括弧だけ。この3つが正規表現の理論的な核であり、a+ は aa*、a? は (a|ε) へと機械的に展開できるので、核さえ動けば拡張は差分にすぎません。

このエンジンを書くと、実務で最も価値のある事実が体で分かります。すなわち、同じ機能に見えて計算量が根本から違う2つの実装流派があるということです。PerlやPython、JavaScriptの標準エンジンの多くは「バックトラッキング方式」で、後方参照のような強力な機能を持つ代わりに、ある種の入力で計算時間が入力長に対して指数的に爆発します。これがReDoS（正規表現による自己DoS）の正体です。対して本記事で作る「Thompson NFA方式」は、後方参照を諦める代わりに、どんな入力でも処理時間が入力長に厳密に線形で収まります。なぜ線形になるのか、その理由をコードとして手元に持つのがゴールです。

最小実装の全体像

横にスクロール

エンジンは3つのパーツを直列につなぎます。

肝は3つ目の実行器の設計思想です。バックトラッキングは「1本の経路を選んで進み、行き止まったら戻ってやり直す」深さ優先探索です。対してThompson方式は「ありうる状態を全部まとめて1つの集合として保持し、集合ごと1文字進める」幅優先探索です。状態の総数は正規表現の長さで決まって有限なので、集合の要素数には上限があります。ゆえに1文字あたりの仕事量に上限があり、全体は 入力長 × 状態数 で頭打ちになる。これが線形時間の骨格です。

段階を追って作る

ステップ1: NFAをどう表すか

各状態は「文字を1つ消費する矢印」を高々1本、あるいは「文字を消費しない空遷移（εイプシロン遷移）」を高々2本持つ、という制約に統一します。この形に揃えると構成が驚くほど単純になります。状態を3種類で表現します。

class State:
    # kind: 'char'（文字消費）, 'split'（分岐）, 'match'（受理）
    def __init__(self, kind, ch=None):
        self.kind = kind
        self.ch = ch        # 'char' のとき照合する1文字
        self.out = None     # 主遷移の行き先
        self.out2 = None    # 'split' のときの第2遷移

split が空遷移による分岐で、a* や a|b の「どちらへも進める」非決定性をここが担います。match は受理状態、つまり「ここに到達できたらマッチ成立」を表す終端です。

ステップ2: Thompson構成で木からNFAを組む

Thompson構成の核心は、部分正規表現を必ず「入口1つ・出口の口が1つ」の断片（フラグメント）として作り、それを演算子ごとに接続することです。出口を後で繋ぐため、まだ行き先の決まっていない矢印（ダングリングポインタ）のリストを断片が持ち回ります。

• 1文字 a: char 状態を1つ作る。入口はその状態、未接続の口はその out。
• 連接 AB: Aの未接続の口をすべてBの入口へ繋ぐ。入口はAの入口、口はBの口。
• 和 A|B: 新しい split を作り2本の空遷移をA・Bの入口へ向ける。入口はその split、口はAとBの口を合わせたもの。
• 繰り返し A*: 新しい split を作り、一方をAの入口へ、他方を「ループを抜ける口」にする。Aの口はその split へ戻す。入口はその split。

図にすると a* はこうです。split から1本はaの char へ、もう1本は外へ。aを読み終えたら split に戻り、また分岐する。

        +---------> (out: 抜ける口)
        |
  --> [split]
        |  ^
        v  |
      [char a]  (aの出口はsplitへ戻る)

コンパイラ本体は構文木を再帰でたどるだけです。

def compile(node):
    if node.type == 'char':
        s = State('char', node.ch)
        return Frag(start=s, dangling=[s])   # 口は s.out
    if node.type == 'concat':
        a = compile(node.left)
        b = compile(node.right)
        patch(a.dangling, b.start)           # Aの口をBの入口へ
        return Frag(start=a.start, dangling=b.dangling)
    if node.type == 'alt':
        a = compile(node.left); b = compile(node.right)
        s = State('split'); s.out = a.start; s.out2 = b.start
        return Frag(start=s, dangling=a.dangling + b.dangling)
    if node.type == 'star':
        a = compile(node.child)
        s = State('split'); s.out = a.start
        patch(a.dangling, s)                 # Aの口をsplitへ戻す
        return Frag(start=s, dangling=[('out2', s)])  # 抜ける口はs.out2

ここで重要なのは、どの部分正規表現も状態を定数個しか増やさないことです。したがって正規表現の長さを m とすると、NFAの状態数は m に比例して収まります。この上限が後で効いてきます。

ステップ3: 状態集合を並行に進めて実行する

実行器は現在ありうる状態の集合を持ち、入力を1文字ずつ食わせます。手順は「今の集合から空遷移で到達できる全状態を集める（εクロージャ）→ その集合の各 char 状態のうち、今の1文字と一致するものだけ次の集合へ入れる」の反復です。

def add(state, current):
    if state in current:      # 既にあるなら二度と辿らない（ここが線形性の要）
        return
    current.add(state)
    if state.kind == 'split':
        add(state.out, current)   # 空遷移は集合へ展開
        add(state.out2, current)

def run(start, text):
    current = set(); add(start, current)
    for c in text:
        nxt = set()
        for s in current:
            if s.kind == 'char' and s.ch == c:
                add(s.out, nxt)   # 一致した矢印の先を次集合へ
        current = nxt
    return any(s.kind == 'match' for s in current)

線形時間の理由がこの add に凝縮されています。集合に既にある状態は即 return するため、1回の文字処理で触る状態は高々「状態数 m 個」。文字数を n とすると全体は n × m。m は正規表現の長さで固定なので、入力長 n に対して線形です。バックトラッキングが同じ状態を無数の経路から何度も再訪して指数爆発するのと、ここが決定的に違います。

ステップ4: 部分マッチとキャプチャ

ここまでは文字列全体がマッチするか（完全一致）でした。実務で多い「文字列のどこかにマッチするか」（部分マッチ）は、正規表現の先頭に .* を暗黙で連接するのと等価です。.* はどの位置からでも照合を開始できることを意味し、開始位置をずらして全走査する素朴な方法（位置数 × マッチ計算）より効率的に、集合方式のまま1回の走査で解けます。

キャプチャ（(...) で括った部分の位置取得）は、遷移に「タグ」を載せて実現します。グループの開始・終了に対応する空遷移を通過した瞬間の入力位置を記録するのです。ただし集合方式では複数経路が同じ状態に融合するため、「どの経路のタグを採用するか」を最左最長などの規則で決める必要があり、実装は一段複雑になります。ここが、後方参照を捨てても純粋なThompson方式が実装として簡単すぎるとは言えない理由です。

発展と本物との違い

作ったエンジンは核となる3演算だけで、実運用のエンジンが足している要素を意図的に省いています。

最大の発展はDFA化です。NFA実行は毎文字ごとに split を展開して状態集合を計算し直しますが、この「状態集合そのもの」を1つのDFA状態とみなし、集合から集合への遷移を事前計算（部分集合構成）すれば、実行時は1文字につき表を1回引くだけになります。理論上の状態数は最悪で状態集合の総数、すなわち2の m 乗まで増えうるため、実務では必要になった集合だけを実行中に作って表に足す「遅延DFA化（オンザフライ）」が使われます。RE2やRustのregexクレートはこの系統で、DFAの速さとNFAの省メモリを両取りしつつ、最悪でも線形という保証を守ります。

オートマトンと計算量の土台はプログラミングの他記事に、状態機械が支える通信プロトコルの実装はネットワークのトピックに関連論点があります。まずは本記事の30行の実行器を写経し、(a|b)*abb のようなパターンで状態集合が1文字ごとにどう膨らみ・畳まれるかを紙に書き出すと、線形時間の直感が確実に手に入ります。