正規表現の `.*` が、想定の3倍マッチした日 — 貪欲マッチを止める3つの手

Posted at 2026-06-27

ログから key="..." を1個ずつ抜くだけのつもりだった。"(.*)" と書いた。返ってきたのは apple" key="banana という、2個ぶんを丸ごと食った1件だった。

原因は .* の 貪欲(greedy)マッチ。一致できる限り長く食う、という正規表現エンジンの基本動作。これを知らずにHTMLタグやJSONやCSVを .* で切ろうとすると、毎回ここで詰まる。直し方は3つあって、用途で使い分ける。

この記事は「正規表現は雰囲気で書いている」「.* を入れたら結果が変で1時間溶けたことがある」人向け。言語は問わない。下の挙動は Python 3 / Node / grep で実際に動かした出力をそのまま貼っている(出力は加工なし)。

公式の定義は Python re ドキュメントと MDN: 正規表現ガイドが一次情報。貪欲・非貪欲の網羅解説は regular-expressions.info が詳しい。この記事はそこから一歩進めて、貪欲が壊す3つの実害を実測値で並べる。

やりたいこと	書きがちなパターン	実際の挙動	直し
タグを1個ずつ	`<.*>`	全体を1個に食う	`<.?>` / `<[^>]>`
引用符の中身	`"(.*)"`	2個を1個に連結	`"(.?)"` / `"([^"])"`
高速・安全に	`(a+)+`	入力次第で固まる	ネストした量指定子をやめる

何が起きたか

アプリのログから設定値を抜く雑なスクリプトを書いていた。行はこう。

key="apple" key="banana"

ダブルクオートの中身を取りたい。素直にこう書いた。

import re
log = 'key="apple" key="banana"'
print(re.findall(r'"(.*)"', log))

期待は ['apple', 'banana']。返ってきたのはこれ。

['apple" key="banana']

apple と banana のあいだの " key=" まで巻き込んで、1個に化けている。最初の " から 最後の " までを1発で食っていた。

貪欲マッチの正体

* + .* などの量指定子は、デフォルトで マッチできる限り長く 食う。これが貪欲。

タグで見ると分かりやすい。同じ文字列に貪欲な <.*> と非貪欲な <.*?> を当てた、実際の出力がこれ。

import re
s = '<b>太字</b>と<i>斜体</i>'
print(re.findall(r'<.*>', s))    # 貪欲
print(re.findall(r'<.*?>', s))   # 非貪欲

['<b>太字</b>と<i>斜体</i>']
['<b>', '</b>', '<i>', '</i>']

貪欲版は最初の < から最後の > まで、途中の > を全部素通りして1個に食う。. は改行以外の任意文字なので、> だろうが何だろうが飲み込める。だから「いったん全部食って、> が必要だから末尾だけ吐き戻す」という動きになる。

引用符の例も同じ理屈。.* が最後の " まで食ってから、1文字だけ戻して帳尻を合わせる。だから2個ぶんが1個に連結する。

直し方その1: 非貪欲 `*?`

* のうしろに ? を付けると できる限り短く 食う非貪欲(lazy)になる。

import re
log = 'key="apple" key="banana"'
print(re.findall(r'"(.*?)"', log))

['apple', 'banana']

これで意図どおり。" を1個見つけたら、次の " が来た時点で止まる。

? の位置を間違えやすいので注意する。*? +? ?? のように 量指定子の直後 に置く。(.*)? のようにグループに付けるのは別の意味(グループ全体が省略可)になる。

直し方その2: 否定文字クラス `[^>]`

非貪欲より確実で、しかも速い手がある。「> 以外の文字」を意味する否定文字クラスを使う。

import re
s = '<b>太字</b>と<i>斜体</i>'
print(re.findall(r'<[^>]*>', s))

['<b>', '</b>', '<i>', '</i>']

[^>]* は「> 以外を0文字以上」。そもそも > を食えないので、最初の > で必ず止まる。非貪欲の <.*?> と結果は同じだが、こちらは「いったん食って吐き戻す」をやらない。

引用符版なら "([^"]*)"。区切り文字が1文字に決まっているとき(タグ・引用符・カンマ区切り)は、非貪欲より否定文字クラスのほうが事故が少ない。理由は後半のバックトラッキングの話につながる。

grep だと `*?` が効かない罠

ここでハマった。Python で直したパターンをそのまま grep に持っていったら動かない。

echo '<b>太字</b>と<i>斜体</i>' | grep -oE '<.*>'

<b>太字</b>と<i>斜体</i>

貪欲のまま、全体を1個で返してくる。grep -E(POSIX 拡張正規表現)には 非貪欲 *? が存在しない。<.*?> と書いても、? がただの「直前を0〜1回」として解釈され、意図と違う動きになる。

POSIX の世界で短くマッチさせたいなら、否定文字クラスで書く。これは grep でも効く。

echo '<b>太字</b>と<i>斜体</i>' | grep -oE '<[^>]*>'

あるいは PCRE が使える ripgrep なら非貪欲がそのまま通る。実際に動かすとこうなる。

echo '<b>太字</b>と<i>斜体</i>' | rg -o '<.*?>'

<b>
</b>
<i>
</i>

「Python では動いたのに本番のシェルスクリプトの grep で動かない」は、エンジンが PCRE か POSIX かの違いで起きる。-P(GNU grep の Perl 互換)が使える環境なら grep -oP '<.*?>' でも通るが、macOS 標準の grep には -P が無い。環境差を踏むくらいなら否定文字クラスに寄せておくのが無難。

もっと怖い話: 正規表現で30文字に50秒

貪欲マッチの本当の地雷は、連結ミスより バックトラッキング爆発 のほう。量指定子をネストさせると、マッチに失敗する入力で計算量が指数的に膨らむ。

(a+)+$ という、ありがちに見えるパターンで測ってみた。末尾に ! を付けてわざと非マッチにする。

import re, time
pat = re.compile(r'(a+)+$')

for n in (28, 30):
    s = "a" * n + "!"
    t = time.time()
    pat.search(s)
    print(f"len={len(s):<3} (a+)+$ : {time.time()-t:.3f}s")

# 同じことを線形なパターンで
pat2 = re.compile(r'a+$')
s = "a" * 30 + "!"
t = time.time()
pat2.search(s)
print(f"len={len(s):<3} a+$    : {time.time()-t:.5f}s")

実際の出力がこれ。

len=29  (a+)+$ : 12.403s
len=31  (a+)+$ : 50.722s
len=31  a+$    : 0.00002s

入力が 2文字増えただけで 12秒 → 50秒。(a+)+ は「a の塊を、a の塊の繰り返しとして」分割する組み合わせを総当たりするので、末尾で失敗が確定するまで膨大な経路を試す。線形な a+$ なら同じ30文字が 0.00002 秒で終わる。

これが実害になるのは、ユーザー入力を正規表現に通すとき。(.+)+ (\w*)* のように 量指定子の中にさらに量指定子 がある形を書いたら、その時点で疑う。外から来る文字列に当てるなら、ネストをほどく(a+$ で足りる)か、否定文字クラスで一意に進ませる。これが ReDoS(正規表現を使ったサービス拒否)と呼ばれる攻撃の入口になる。実例として Cloudflare は 2019年7月2日、WAF に入れた .*.*=.* という1行で全世界が27分ダウンした(指数的バックトラッキング)。Stack Overflow も 2016年7月20日、空白除去の正規表現に約20,000個の空白を食わせられて34分ダウンしている(こちらは2次的に遅くなる型)。たった1本のパターンでサービスが落ちる。攻撃手法と対策は OWASP の ReDoS 解説にまとまっている。

言語ごとの差

貪欲・非貪欲の記号自体はだいたい共通だが、エンジンの素性が違う。手元で確認した範囲を並べる。

Python re / JavaScript / PCRE(grep -P, ripgrep): バックトラッキング型。*? の非貪欲が使える。ネスト量指定子で固まりうる。
POSIX grep / sed(-E): 非貪欲 *? が無い。否定文字クラスで代替する。
Go regexp / Rust regex / RE2: オートマトン型で、入力長に対して線形時間。上の (a+)+$ を投げても固まらない。ただし後方参照など一部機能が使えない(RE2 の構文一覧)。コマンドラインで PCRE の非貪欲を使いたいなら ripgrep が手軽。

Node で同じタグ分割をやっても、結果は Python と一致する。

node -e 'const s="<b>太字</b>と<i>斜体</i>"; console.log(s.match(/<.*>/g)); console.log(s.match(/<.*?>/g));'

[ '<b>太字</b>と<i>斜体</i>' ]
[ '<b>', '</b>', '<i>', '</i>' ]

「外から来る文字列に複雑な正規表現を当てる」要件なら、言語選定の段階で RE2 系を選ぶと、ネストミスでサービスが落ちる事故そのものを構造的に避けられる。

非貪欲にもデメリットがある

*? を覚えると今度は何でも非貪欲にしたくなるが、これも罠。

短くマッチしすぎる: ".*?" で "a","b" のような入れ子・連続を拾うと、想定外の最短で切れて取りこぼす。区切りが1文字なら否定文字クラスのほうが意図が明確。
速いとは限らない: 非貪欲も内部ではバックトラッキングする。否定文字クラス [^>]* のほうが「戻る」動作が無いぶん素直。
読みにくい: <.*?> は慣れないと「なんで ? が後ろ?」となる。チームのコードなら <[^>]*> のほうが意図が伝わる。

つまり優先順位は「区切りが1文字に決まる → 否定文字クラス」「それ以外で短く取りたい → 非貪欲」「ユーザー入力に当てる → そもそもネスト量指定子を書かない / RE2 を検討」。.* をデフォルトの相棒にしないのが結論。

まとめ

.* は便利に見えて、貪欲・grep非対応・バックトラッキングの3点で必ずどこかで刺さる。今日からやること:

既存コードの .* を grep して、区切り文字が決まっている箇所は [^区切り]* に書き換える
ユーザー入力を正規表現に通している箇所を探し、(.+)+ (\w*)* のネスト量指定子が無いか確認する
シェルスクリプトの grep で非貪欲を書いていたら、POSIX では効いていないので否定文字クラスに直す

.* を書きそうになったら、いったん「ここの区切りは1文字か?」と自問する。それだけで、この記事で踏んだ3つの事故(連結ミス・grep非対応・バックトラッキング)はほぼ防げる。

参考リンク

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up