正規表現の貪欲マッチ.*や最短マッチ.*?を使っていて、
「あれ…？なんでこんな出力になるの…？」
ってことありませんか？

突然ですが、問題

以下の２つのケース、どんな出力になるか、わかるでしょうか？
ぜひ少し考えてみてください。

import re
s = 'aaabbb'
# 連続する貪欲マッチ
re.findall(r'^(.*)(b*)$', s)
# 連続する最短マッチ
re.findall(r'^(.*?)(b*?)$', s)

答え

# re.findall(r'^(.*)(b*)$', s)
('aaabbb', '')
# re.findall(r'^(.*?)(b*?)$', s)
('aaa', 'bbb')

前者のケース、(b*)の貪欲マッチが優先されれば、('aaa', 'bbb')になりそうにも思えます。
また、後者のケースも同様に、(b*?)の最短マッチが優先されれば、('aaabbb', '')となってもおかしくないように思えます。

結論を聞くと、まぁそうだよね感はあるかと思いますが、より前方にある貪欲/最短マッチが優先されます。

なぜそうなるのか、貪欲/最短マッチのアルゴリズムとともに、説明していきたいと思います。

aaabbbに対する^(.*)(b*)$は、以下のような動作になります。

したがって、

がそれぞれ該当するという結果になる訳です。

続いて、最短マッチのアルゴリズムです。

貪欲マッチでは、2の部分で該当の条件がマッチする限り終了位置を後方に進めて、そこから前方に遡る形で、後続の条件がマッチするかを見ていきました。一方で、最短マッチでは、終了位置を1文字進める度に、後続の条件がマッチするかと見るという形になっています。

最短マッチについても、aaabbbに対する^(.*)(b*)$の動作を見ていきます。

行頭を表す^があるため、(.*)の開始位置は[ココ]aaabbbになります
終了位置を[ココ]aaabbbとして条件を確認します
1. 該当の条件(.*)は、空文字列にマッチします（→処理継続）
2. 後続の条件(b*)$は、aaabbbにはマッチしません（→処理継続）
終了位置を1文字進めて、a[ココ]aabbbとして条件を確認します
1. 該当の条件は、aにマッチします（→処理継続）
2. 後続の条件は、aabbbにはマッチしません（→処理継続）
（少し飛ばして）終了位置を更に進め、aaa[ココ]bbbとして条件を確認します
1. 該当の条件は、aaaにマッチします（→処理継続）
2. 後続の条件は、bbbにマッチします（→処理終了）

したがって、

という結果になります。

ということで、正規表現との一致の確認が前方から行われていくため、より前方の貪欲/最短マッチが、後方の貪欲/最短マッチより優先されるということになります。

実際のところ、出現頻度は低い気はしますが、私が遭遇した実例を紹介しておきます。

言語処理100本ノックという、東北大学の研究室が公開している言語処理の問題集があり、その中の第３章 25.テンプレートの抽出の中で、この記事の問題に出会しました。

少し問題を簡略化しますが、

こんにちは = Hello
おはよう=Good morning
おやすみ= Good night

といったテキストがあり、=の前後の単語で辞書型オブジェクトを生成しなさい、という問題です。意図されたものでは無いのですが、=の前後にスペースが有ったり無かったりと、統一されていないところがいやらしい感じです。

しかし、私は「貪欲マッチを使えば、楽勝楽勝っ♪」と、意気揚々と以下のコードを書きました。

matched  = re.find(r'^(.*) *= *(.*)$', text, flags=re.MULTILINE)
d = {key: value for key, value in matched}

そして、この出力を見て、目を疑いました。

{'おはよう': 'Good morning', 'おやすみ': 'Good night', 'こんにちは ': 'Hello'}

'こんにちは '

「なんでスペースまで拾ってるんじゃーっ！！Σ(ﾟдﾟ;)」

若干大袈裟ですが、 *= *の貪欲マッチで、=の前後のスペースが消えると思っていた私には、実際何が起こっているのかすぐにはわかりませんでした。

ここまで読んでくださっている方には簡単と思いますが、より前方にある(.*)が優先されてしまっているんですね。なので、その部分を最短マッチにすることで、想定通りの答えが得られます。

re.find(r'^(.*?) *= *(.*)$', text, flags=re.MULTILINE)
# [('こんにちは', 'Hello'), ('おはよう', 'Good morning'), ('おやすみ', 'Good night')]

ちなみに、=の後ろにある(.*)は、これよりも *= *の方が優先されるので、(.*?)と書く必要はありません。

「より前方の貪欲/最短マッチが優先される」

結論としては簡単ですし、アルゴリズムを理解すれば当たり前ですが、ブラックボックス的に扱っていると結構ハマってしまう部分かなと思います。
似た話では、[正規表現] .*?は最短マッチではないとかも、ハマりポイントと思います。（というか、こちらの方が頻出）

少しでも参考になれば幸いです。
お読みいただきありがとうございました。