12 分で読了 #compilers #lexical-analysis
このページの目次

正規表現とオートマトン

字句解析の第一段階: 正規表現を効率的に実行可能なオートマトンに変換する。正規表現→NFA→DFA→最小化DFAという変換チェーンは、字句解析器の速度と正確性を決定し、バックトラックエンジンとオートマトンエンジンの2つのアプローチに分かれる。

概要

字句解析（lexing）はコンパイラの第一工程であり、ソースコードの文字列をトークンの列に分割する。この工程の数学的基盤は正規言語と有限オートマトンである。「正規表現→NFA→DFA→最小化DFA」という変換チェーンを理解することは、字句解析器がなぜそのような動作をするのかを知るだけでなく、2種類の正規表現エンジン——オートマトンベースのRE2/Hyperscan（線形時間、バックトラックなし）とバックトラックベースのPCRE（最悪指数時間）——を区別する上で重要である。ここでは、変換チェーンの各ステップにおけるアルゴリズムとデータフローを明確にする。

正規表現: パターンを記述する代数

正規表現は、3つの基本的な演算を用いて文字列の集合（言語）を記述する。

  • 連結⁠: ab は "a" の後に "b" が続く文字列にマッチする
  • 選択⁠: a|b は "a" または "b" にマッチする
  • Kleene閉包⁠: a* は "a" が0回以上続く文字列にマッチする

正規表現はこれらの演算に対して閉じている——任意の組み合わせでも依然として正規表現であり、これが「必ずオートマトンに変換可能である」という代数的基盤となる。

現代の字句解析器における正規表現には、文字クラス [a-z]、繰り返し +/?、キャプチャグループなどの利便性のための構文が追加されているが、その核心はこれら3つの演算を超えない。

NFA: Thompson構成

NFA（非決定性有限オートマトン） は、有限の状態集合と遷移関係からなる。同じ入力文字に対して、1つの状態から複数の次の状態へ遷移できる（非決定性）。

Thompson構成（1968）は、正規表現からNFAへの体系的な変換手法を提供する。NFAには明確な開始状態と明確な受理状態があり、各演算は連結パターンに対応する。

Thompson構成: 正規表現演算 → NFA連結パターン 基本ユニット 文字 'a' にマッチ start accept a 連結 e1e2 e1 のNFA e2 のNFA ε accept₁ → start₂ 選択 e1|e2 start e1 のNFA e2 のNFA accept ε ε ε ε Kleene閉包 e* start e のNFA accept ε ε ε ↑ 繰り返しループ ↑ e をスキップし、0回マッチ ε遷移は入力文字を消費せず、選択や閉包における分岐と結合の鍵となるメカニズムである。 状態数は正規表現の長さに比例し、バックトラックエンジンのような指数関数的な爆発は起こらない。

状態数は正規表現の長さに比例する（各文字/演算子に対して少量の新しい状態が生成される）。バックトラックエンジンが指数関数的に爆発する可能性があるのと対照的である。ε遷移（空遷移: 入力文字を消費しない状態間の遷移）はここで重要なメカニズムとなる——選択と閉包はどちらもε分岐に依存している。

DFA: 部分集合構成

NFAの「非決定性」とは、同じ入力文字に対して、現在複数の状態の集合にいる可能性があることを意味する。DFAの核心的な洞察は、これらの「状態の集合」をDFAの新しい状態として扱うこと——これを部分集合構成（subset construction）と呼ぶ。

アルゴリズム:
  dfa_start = ε-closure({nfa_start})       ← NFAの開始状態から、入力を消費せずに到達可能なすべての状態
  worklist = [dfa_start]
  while worklist not empty:
    S = worklist.pop()
    for each input character c:
      T = ε-closure(move(S, c))            ← S内のいずれかの状態から、cによって遷移可能、その後ε-閉包
      if T is new:
        worklist.push(T)
      DFA遷移を追加: S ─c─► T
  • move(S, c): 状態集合Sから、文字cによって到達可能なすべての状態（ε遷移は見ない）。
  • ε-closure: 状態の集合から、入力を消費せずにε遷移のみをたどって到達可能なすべての状態（自身を含む）。

これら2つの操作が部分集合構成のすべてである。最悪の場合、DFAの状態数はNFAの状態数の指数倍になる——しかし、実際の字句解析における正規表現は最悪ケースをほとんどトリガーしない。多くの字句解析器において、DFAの状態数はNFAの状態数とほぼ同等である。

これが、字句解析器がDFA（状態数が少ない、決定論的、1文字あたりO(1)の遷移）を使用し、一般的な正規表現ライブラリ（PCRE）がバックトラックを使用する理由である。DFAはキャプチャグループや後方参照を処理できないが、これらは正規表現の文法が「真の正規言語」を超えた部分である。

DFA最小化: Hopcroftアルゴリズム

部分集合構成によって生成されたDFAには、冗長な状態が含まれる可能性がある（任意の入力に対して完全に同じ動作をする2つの状態）。Hopcroftアルゴリズムは等価な状態を結合する。

アルゴリズム (Hopcroft, O(n log n)):
  初期分割: 受理状態を1グループ、非受理状態を1グループ
  while 分割がさらに細分化される:
    分割ブロックAを1つ取る
    各入力文字cについて:
      もしA内の状態がcへの遷移で異なる分割ブロックに遷移するなら
        → 「どのブロックに遷移するか」によってAをさらに分割する

分割が安定状態に達する——同じブロック内の状態は任意の入力に対して完全に同じ動作をするため、1つに結合できる。Hopcroftの n log n は現在理論的に最適である（DFA最小化の理論的下界は Ω(n log n) であり、Hopcroftアルゴリズムはこの最適値に達している。DFAの等価性判定は別の独立した問題であり、O(n)時間で解決可能である）。

実際には、多くの字句生成器（lex/flex/re2c）はDFAの最小化を行う——字句解析器のDFAは通常数百状態程度であり、線形またはほぼ線形のアルゴリズムで十分であり、定数最適化に過度に投資する必要はない。

オートマトンから字句解析器へ: 最長一致と優先度

字句解析器は単に「DFAを走らせて最初の受理状態に達するまで実行する」のではなく、⁠最長一致 + 優先度を行う。

アルゴリズム (maximal munch):
  現在のソースコード位置からDFAを走らせ、通過中に遭遇した受理状態とその位置を記録する
  DFAがこれ以上進めなくなるまで（デッド状態 / 遷移なし）
  最近の受理状態に戻り → そのトークンを切り出す
  次の文字から再開する
  • 最長一致⁠: if は i を読み込んだ時点で停止しない（i が有効な識別子トークンであっても）、if を読み込み、さらに1文字読んでそれ以上進めなくなった時点で初めてトークンとして確定する。
  • 優先度⁠: if はキーワードであり、かつ有効な識別子でもある——キーワードの方が高い優先度を持つ。DFA構築時に、キーワードの受理状態に高い優先度をマークする。最長一致後、複数の受理状態が同じ長さでマッチする場合、最も優先度の高いものを選ぶ。

2種類の正規表現エンジン: なぜこれが教科書の知識だけではないのか

NFA→DFAというチェーンを理解することは、現実世界の正規表現エンジンの選択に直接対応する。

バックトラックエンジン (PCRE, Python re, JS)オートマトンエンジン (RE2, Hyperscan, Rust regex)
実装再帰的バックトラックNFA→DFA（またはNFAシミュレーション）
時間計算量最悪指数時間（特定の正規表現でトリガー可能）O(n)（入力長に線形）
キャプチャグループサポートあり限定的/サポートなし
後方参照サポートありサポートなし（正規言語を超えている）
用途一度限りの小規模テキストマッチング高スループット/信頼できない入力/ストリーミング

バックトラックエンジンの本質はNFA上でDFS（深さ優先探索）を行うことであり、オートマトンエンジンは「まずDFAを構築し、入力に対してO(n)のスキャンを実行する」である。正規表現注入攻撃（ReDoS）の根本原因は、バックトラックエンジンが意図的に構築された正規表現に対して指数関数的に爆発することにある——DFAを構築すればこの問題は存在しない。

この境界は、字句解析器の正規表現と一般的な正規表現の違いも説明している。字句解析器の正規表現は「真の正規表現」（キャプチャや後方参照を必要としない）であるため、DFAを使用できる。一般的な正規表現は正規表現能力を超えた機能を多く追加しているため、バックトラックしか使用できない。

トレードオフと失敗パターン

  • DFA状態の爆発⁠: 特定の正規表現（ネストされた量指定子 (a*)* や、Kleene星の後に複雑な選択が続く場合など）では、部分集合構成が指数関数的な状態を生成する可能性がある→実際にはほとんど見られないが、トリガーされた場合は、完全なDFAの代わりにNFAシミュレーション（状態集合を必要に応じて計算）を使用する。
  • 最長一致が不要な文字まで消費する⁠: >> がネストされたジェネリクス >> vs 右シフトとして誤認される可能性がある→字句解析器自体では処理できない（構文解析器が文脈を提供する必要がある）、字句解析器は単に分割するだけである。
  • Unicodeにおける文字クラス⁠: \w はASCIIとUnicodeで意味が異なり、DFAのアルファベットが128から数百万に急増する→現代のエンジンでは文字区間エンコーディング⁠（各Unicodeコードポイントを列挙せず、遷移区間を保存する）を使用し、アルファベットサイズを制御可能に保つ。

参考文献

  • Dragon Book(Aho, Lam, Sethi, Ullman): Chapter 3, Lexical Analysis — 正規表現→NFA→DFA→最小化の完全なチェーン
  • Ken Thompson(1968): "Regular Expression Search Algorithm" (CACM 11(6)) — NFAシミュレーションの起源
  • Russ Cox(2007): "Regular Expression Matching Can Be Simple And Fast" — 2種類のエンジンの徹底的な比較

Keywords: regular expression, finite automaton, NFA, DFA, Thompson construction, subset construction, ε-closure, ε-transition, Hopcroft minimization, maximal munch, longest match, backtracking, RE2, ReDoS, character class, Unicode character intervals

関連ページ

© 2026 liz's doc