[正規表現] .*?は最短マッチではない

TL;DR

.*?は最短マッチではなく最左最短マッチである。

よくある誤解

<<<hoge>>>

という文字列に対して、

<.*?>

という正規表現をパターンマッチさせると、.*?は最短マッチと呼ばれているくらいなので、

<hoge>

という、可能な限り短い部分文字列にマッチしてくれるのだろう。

実際の挙動

# Ruby 2.4.2
"<<<hoge>>>".match(/<.*?>/)[0] #=> "<<<hoge>"

なぜこうなるのか

.*?は、

• 最短マッチ
• 最左マッチ

の2つの原則に従い、しかも最左マッチの原則の方が優先順位としては高いからである。

より嚙み砕いて言うと

<.*?>は先頭の<がマッチした後に、そこからマッチする部分をできるだけ最小化しようと試みる。
<<<hoge>>>に対して<.*?>をパターンマッチさせる際に行われる実際の処理の流れは、次のようなイメージになるだろう。

<         # <までマッチ
<<        # <>のマッチに失敗、.の数を増やしてリトライ
<<        # <.までマッチ
<<<       # <.>のマッチに失敗、.の数を増やしてリトライ
<<<       # <..までマッチ
<<<h      # <..>のマッチに失敗、.の数を増やしてリトライ
<<<h      # <...までマッチ
<<<ho     # <...>のマッチに失敗、.の数を増やしてリトライ
<<<ho     # <....までマッチ
<<<hog    # <....>のマッチに失敗、.の数を増やしてリトライ
<<<hog    # <.....までマッチ
<<<hoge   # <.....>のマッチに失敗、.の数を増やしてリトライ
<<<hoge   # <......までマッチ
<<<hoge>  # <......>までマッチ

<hoge>にマッチさせたければどうするか

そもそもこの目的に最左最短マッチである.*?はあまり適していないので、.*?を使うのはやめておいた方がよい。
<.*>をできるだけ短い文字列にマッチさせたいという発想からは脱する必要がある。

ではどうすればよいのだろうか。
有力な代替案の一つは、「<も>も含まない0文字以上の文字列を<と>で囲んだ文字列」にマッチする正規表現を作ればよい、という考え方である。
そのような正規表現には、<[^<>]*>がある。

動作例

# Ruby 2.4.2
"<<<hoge>>>".match(/<[^<>]*>/)[0] #=> "<hoge>"

.*?の出番は意外に少ない

問題をより一般化して考えると、.*?を使いたくなるケースの代表例として、ある開始文字列fooとある終了文字列barに囲まれた、できるだけ短い文字列にマッチする正規表現を書きたいというケースがあるわけである。
だが先ほど指摘した通り、foo.*?barは期待した文字列に正しくマッチしてくれない。
ではどうすればよいかというと、こういったケースでは、「fooもbarも含まない0文字以上の文字列をfooとbarで囲んだ文字列」にマッチする正規表現を書く、という風に考えればよいのだ。
.*?を無理して使う必要はない。

fooが<em>、barが</em>である場合を具体例として出そう。
以下は、「<em>も</em>も含まない0文字以上の文字列を<em>と</em>で囲んだ文字列」にマッチする正規表現である。
そして、このどれもが正しい。

• <em>([^<]|<(<|e<|em<|/<|/e<|/em<)*([^<e/]|e[^<m]|em[^<>]|/[^<e]|/e[^<m]|/em[^<>]))*(<(<|e<|em<|/<|/e<|/em<)*(e?|em|/|/e|/em))?</em>
• <em>(?:(?!<em>|</em>).)*</em>
• <em>(?~<em>|</em>)</em>

動作例

# Ruby 2.4.2
str = "<em>あ<em>い<strong>う</strong>え</em>お</em>"
str.match(%r{<em>([^<]|<(<|e<|em<|/<|/e<|/em<)*([^<e/]|e[^<m]|em[^<>]|/[^<e]|/e[^<m]|/em[^<>]))*(<(<|e<|em<|/<|/e<|/em<)*(e?|em|/|/e|/em))?</em>})[0] #=> "<em>い<strong>う</strong>え</em>"
str.match(%r{<em>(?:(?!<em>|</em>).)*</em>})[0] #=> "<em>い<strong>う</strong>え</em>"
str.match(%r{<em>(?~<em>|</em>)</em>})[0] #=> "<em>い<strong>う</strong>え</em>"

1番目の書き方は、先ほどの<[^<>]*>の例同様、基本的な正規表現の構文のみを使った書き方である。
この書き方はほぼ全ての処理系で使用可能という利点があるが、見ての通り読めたものではない。
基本的な構文のみ使う場合、特定の文字を含まない文字列にマッチする正規表現は簡単に書けるので、先ほどの<[^<>]*>は簡単に書けたのだが、特定の文字列を含まない文字列にマッチする正規表現を書くことは非常に難しいため、このようなことになってしまっている。

2番目の書き方は否定先読みと呼ばれる構文を使った書き方である。
この書き方は1番目の書き方よりも使用できる処理系が限られるという欠点があるが、より簡単に読み書きすることができる。
基本的にはこれを使えばよいだろう。

3番目の書き方は非包含オペレータと呼ばれる構文を使った書き方である。
この書き方はRuby 2.4.1以上限定（より正確に言うと鬼雲限定）であるが、可読性はこの中で最高である。
Rubyistは是非この書き方を使っていきたい。

まとめ

.*?は最短マッチではなく最左最短マッチである。
.*?を使いたくなるが期待通りに動作してくれないケースの多くでは、否定先読みか非包含オペレータを使うことで問題が解決可能である。

余談: 真の最短マッチは実現可能か

.*?は最左最短マッチであるが、では、真の最短マッチは実現可能なのだろうか。
つまり、例えば、<em>と</em>で囲まれた部分文字列が複数ありうるとき、その中で最も短い部分文字列にマッチする正規表現を書く方法はあるのだろうか？
具体例としては、

<em>あ<em>い<strong>う</strong>え</em>お<em>か</em>き</em>

のような文字列が入力として来た場合、<em>か</em>にマッチさせるようにしたい。（<em>い<strong>う</strong>え</em>は、<em>か</em>より長いのでマッチさせない）

コメントを募集したが、どうやら特殊な拡張構文を利用しない限りは難しそうということのようである。
以下は、@HMMNRST さんによる、真の最短マッチの実現例である。
コメントをそのまま引用する。

真の最短マッチをエンジン自体の動作でなく構文で実現しようとすると、非正規な機能が必要な気がします。

例えば.NETであれば「グループ定義の均等化」というものが用意されているので、「この先の部分文字列にもっと短い一致候補が無い」という条件を書けるはずです。以下のコードはPowerShellで試しました。

$regex = [regex] "<em>(?'char'(?!<em>|</em>).)*</em>(?!.*<em>(?'-char'(?!<em>|</em>).)*</em>(?(char)|(?!)))"
$regex.Match("<em>あ<em>い</em>う<em>え<strong>お</strong>か</em>き</em>").Value   #=> <em>い</em>
$regex.Match("<em>あ<em>い<strong>う</strong>え</em>お<em>か</em>き</em>").Value   #=> <em>か</em>
$regex.Match("<em>あ<em>い</em>う<em>え</em>お<em>か</em>き</em>").Value           #=> <em>い</em>

前半ではemタグの内側の文字列を1文字ずつキャプチャ（スタックcharに追加）し、後半では別のemタグの内側で1文字読み込むたびにスタックから捨てています。長い文字列だとスタックが途中で空になってもう捨てられず、部分マッチ失敗となる算段です。最後の(?(char)|(?!))は文字列長が同じ（スタックがぴったり空）だった場合に失敗とし、最短のうえで最左マッチに仕立てています。

タグの長さが可変になったら、その分も数えなければいけないので同様の方法が使えるかはわかりません。