正規表現の貪欲・非貪欲マッチでハマらないために

約6分
正規表現regex

.* と .*? の違いは「アスタリスクの後ろにクエスチョンマークが付いたかどうか」だけですが、マッチ結果は劇的に変わります。HTMLタグやログのフィールド抽出など、現場で正規表現を書くとほぼ必ず遭遇するこの差を整理します。

量指定子の基本：* + ? {n,m}

正規表現で量指定子は「直前のパターンが何回出現するか」を指定します。

量指定子意味
*0 回以上
+1 回以上
?0 回または 1 回
{n}ちょうど n 回
{n,}n 回以上
{n,m}n 回以上 m 回以下

これらすべてに「貪欲」と「非貪欲」のバリエーションがあります。

デフォルトは「貪欲」（greedy）

何も付けない量指定子は貪欲で、マッチできる最長の範囲を取ろうとします。

例：<.*> という正規表現を <a><b> に適用すると：

入力:  <a><b>
パターン: <.*>
マッチ: <a><b>   ← 全体にマッチ（最長）

.* は「任意の文字 0 文字以上」で、貪欲に取るので末尾の > まで含む a><b を取ります。直感的には「<a> だけマッチしてほしい」と思うので、ここで初めて貪欲性に気付くケースが多いです。

? を付けると「非貪欲」（lazy）

量指定子の後ろに ? を付けると非貪欲になり、マッチできる最短の範囲を取ります。

入力:  <a><b>
パターン: <.*?>
マッチ: <a>     ← 最短にマッチ（次の > まで）
        <b>     ← 残りに対しても適用すると次もマッチ

.*? の方は「> が出てきたところで止まる」挙動になります。HTMLタグの抽出のような用途では非貪欲が必要です。

バックトラッキングとして理解する

貪欲・非貪欲の挙動は、バックトラッキング（後戻り）の方向の違いとして整理できます。

貪欲の動き

  1. まず最長のマッチを試す（入力末尾まで取る）
  2. 残りのパターンが合わなければ、1文字ずつ縮めて再試行
  3. 縮めながら成功するまで戻り続ける

非貪欲の動き

  1. まず最短のマッチを試す（0 文字または 1 文字）
  2. 残りのパターンが合わなければ、1文字ずつ広げて再試行
  3. 広げながら成功するまで進み続ける

両方ともバックトラッキングするのは同じで、進む方向が逆です。性能特性も微妙に違います（後述）。

文字クラス否定で代替する手も

.*? を多用するパターンでは、否定文字クラスで同じことを表現できる場合があります。

例：HTMLタグを抽出する：

非貪欲: <[^>]*>      ← `>` 以外の文字を貪欲に取る
       <.*?>         ← 任意文字を非貪欲に取って次の `>` で止める

両方とも結果は同じ <a> ですが、否定文字クラスのほうが：

  • 明示的：何を許容しないかが明確
  • 高速：バックトラッキングが起きないので一発でマッチが確定する
  • 誤マッチが少ない：複雑な入力でも壊れにくい

正規表現エンジン的には、[^>]* のような否定文字クラスはバックトラッキング不要なため、特に長い入力に対する性能差が出ます。

「壊滅的バックトラッキング」を起こさないために

貪欲な量指定子を入れ子にすると、バックトラッキングが指数的に膨らむパターンが作れます。

パターン: (a+)+b
入力:    aaaaaaaaaaaaaaaaaaaaaaaaaa  (b なし)

このパターンは a を (a+) の中で取り方を変えながら何度も試すので、入力長 N に対して 2^N に近い試行回数になります。実際の正規表現ライブラリで数十文字の入力でも数秒〜数分固まる、いわゆる ReDoS（Regex DoS） の典型例です。

回避策：

  • 入れ子の量指定子を避ける（(a+)+ ではなく a+）
  • 所有量指定子（(a+)+ を (a++)+ のように + を所有化）— 一部のエンジンのみサポート
  • アトミックグループ（(?>a+)+ — Java や PCRE）
  • 否定文字クラスや具体的な文字を使って曖昧さを減らす

JavaScript の正規表現エンジンは所有量指定子もアトミックグループもサポートしないので、設計で防ぐしかありません。

(.*) をキャプチャに使うときの罠

ログから JSON を抽出するような場面：

入力:  request_id="abc-123" body="{"foo":1}" status=200
パターン: body="(.*)"

貪欲なので (.*) は 末尾の " まで貪欲に取ることを試み、最後の 200 の前の " までマッチしてしまいます：

キャプチャ: {"foo":1}" status=200  (NG)

非貪欲にすると次の " まで：

パターン: body="(.*?)"
キャプチャ: {"foo":1}  (OK)

ただし (.*?) も完璧ではなく、入力に body="abc \"escaped\" def" のようなエスケープがあると壊れます。本格的にやるなら：

パターン: body="((?:[^"\]|\.)*)"

このように「" 以外の文字、またはバックスラッシュエスケープ」を許容するパターンを書くか、そもそも正規表現で JSON を切り出さず JSON パーサに通すのが安全です。

まとめ：使い分けのルール

  • デフォルトは貪欲：明示的に ? を付けない限り最長マッチ
  • HTML/タグ抽出は非貪欲か否定文字クラス：性能と正確性で否定文字クラス推奨
  • 量指定子の入れ子に注意：ReDoS の温床
  • 複雑なテキスト切り出しは正規表現の限界を意識：JSON や HTML は専用パーサに頼る

正規表現を書いて意図通りに動くか確かめたいときは、本サイトの regex テスターでマッチ結果を即座に確認できます。貪欲・非貪欲の違いを体感したいときに同じパターンを ? ありなしで試すと、挙動が一瞬で見えます。