正規表現はどう動いている？エンジンの仕組みを解説

文字列のパターンを指定して、検索・置換・検証ができる仕組みだよ。たとえば「メールアドレスっぽい文字列を探して」みたいな曖昧な要望を、`[a-zA-Z0-9]+@[a-zA-Z0-9]+\.[a-z]+` というパターンで正確に表現できるんだ。プログラミング言語のほとんどに標準で搭載されている、テキスト処理の基本ツールだね。

正規表現エンジンの中核は「ステートマシン（状態機械）」だよ。パターンを読み込むと、まず内部的に状態の遷移図を作るんだ。たとえば `abc` というパターンなら、「a を読んだら次の状態へ」「b を読んだら次へ」「c を読んだら一致！」という3ステップの図になる。エンジンは入力文字列を1文字ずつ読みながら、この図の上を移動していくんだよ。

大きく分けてNFA（非決定性有限オートマトン）とDFA（決定性有限オートマトン）の2種類があるよ。DFAは各状態から次の状態が1つに決まるので高速だけど、構築にメモリと時間がかかる。NFAは1つの状態から複数の遷移先がありえるので、分岐を試しながら進む必要がある。PythonやJavaScript、Rubyなど多くの言語はNFAベースのエンジンを使っていて、その理由は後方参照やキャプチャグループなどの高機能を実装しやすいからなんだ。

「バックトラッキング（後戻り）」という仕組みだよ。たとえば `a*b` というパターンで文字列 `aaac` をマッチさせようとすると、エンジンはまず `a*` で貪欲にaを全部食べてしまう。でも次の `b` がcと一致しないから、aを1つ吐き出して再挑戦する。それでもダメならもう1つ吐き出して…と後戻りしながら全パターンを試すんだ。マッチしない場合は全部試してから「不一致」と判定するよ。

そこがまさに正規表現の落とし穴で、ReDoS（Regular Expression Denial of Service）と呼ばれる問題だよ。たとえば `(a+)+$` のようなパターンに `aaaaaaaaaaaaaaaaab` を与えると、バックトラッキングの組み合わせが指数関数的に爆発して、CPUが何分も固まることがある。これは実際に攻撃手法として悪用されることもあるんだ。

いいところに気づいたね。`*` や `+` はデフォルトで「貪欲（greedy）」、つまりできるだけ多くの文字をマッチしようとする。`*?` や `+?` のように `?` を付けると「怠惰（lazy）」になって、できるだけ少なくマッチしようとするんだ。たとえばHTMLから `<b>太字</b>` を抜き出すとき、`<.*>` だと貪欲に全体をマッチするけど、`<.*?>` なら最初の `<b>` だけにマッチする。ただし怠惰にしてもバックトラッキング自体は発生するから、ReDoS対策にはならないよ。

よくある例を分解してみよう。電話番号の `^0\d{1,4}-\d{1,4}-\d{4}$` は、「0で始まり、数字が1〜4桁、ハイフン、数字が1〜4桁、ハイフン、数字4桁で終わる」という構造だね。メールアドレスはRFC準拠にすると恐ろしく複雑になるから、実務では `^[^@]+@[^@]+\.[^@]+$` くらいのゆるいチェックにして、あとは実際にメールを送って確認するのがベストプラクティスだよ。正規表現だけで完璧なバリデーションをしようとすると沼にハマるんだ。

先読み（lookahead）と後読み（lookbehind）は「マッチはするけど消費しない」特殊な条件だよ。たとえば `\d+(?=円)` は「円」の前にある数字にマッチするけど、マッチ結果に「円」は含まれない。パスワードの強度チェックで「英大文字・小文字・数字をすべて含む」みたいな複合条件を1つの正規表現で書くときに重宝するんだ。`(?=.*[A-Z])(?=.*[a-z])(?=.*\d).{8,}` のように先読みを並べると、AND条件として機能するよ。

たくさんあるよ。HTMLやXMLのパースは正規表現だけでは正確にできないし、JSONやCSVにも専用パーサーを使うべきだね。あと固定文字列の検索なら `indexOf` や `includes` のほうが圧倒的に速い。正規表現が得意なのは「パターンが可変で、かつテキストが構造化されていない」ケースだよ。ログファイルから特定のエラーパターンを抽出するとか、ユーザー入力の簡易バリデーションとか。万能に見えて、使いどころを選ぶツールなんだ。

有名なのは2019年のCloudflareの障害だね。WAF（Webアプリケーションファイアウォール）のルールに追加された正規表現にカタストロフィック・バックトラッキングが発生して、世界中のCloudflare利用サイトが約27分間ダウンしたんだ。原因は `(?:(?:\")+)+` のようなネストした量指定子で、入力によっては指数関数的にCPUを消費するパターンだった。この事件以降、Cloudflareはバックトラッキングしないエンジン（Rustのregexクレート等）への移行を進めたよ。

まず「ネストした量指定子」を避けること。`(a+)+` や `(a*)*` のようなパターンは危険信号だよ。次に、アトミックグループ `(?>...)` や所有量指定子 `*+` を使えるエンジンならバックトラッキングを制御できる。さらに根本的な対策としては、RE2やRustのregexクレートのようにバックトラッキングしないエンジンを選ぶ方法がある。これらはNFAではなくDFAベースで動くから、どんな入力でも線形時間で処理が完了するんだ。セキュリティが重要なシステムでは、エンジン選定から考えるのが現代のベストプラクティスだね。