1. anqooqie

    Posted

    anqooqie
Changes in title
+[正規表現] .*?は最短マッチではない
Changes in tags
Changes in body
Source | HTML | Preview
@@ -0,0 +1,110 @@
+# TL;DR
+`.*?`は最短マッチではなく**最左**最短マッチである。
+
+# よくある誤解
+```
+<<<hoge>>>
+```
+
+という文字列に対して、
+
+```
+<.*?>
+```
+
+という正規表現をパターンマッチさせると、`.*?`は**最短**マッチと呼ばれているくらいなので、
+
+```
+<hoge>
+```
+
+という、**可能な限り短い**部分文字列にマッチしてくれるのだろう。
+
+# 実際の挙動
+```ruby
+# Ruby 2.4.2
+"<<<hoge>>>".match(/<.*?>/)[0] #=> "<<<hoge>"
+```
+
+# なぜこうなるのか
+
+`.*?`は、
+
+* 最短マッチ
+* 最左マッチ
+
+の2つの原則に従い、しかも最左マッチの原則の方が優先順位としては高いからである。
+
+# より嚙み砕いて言うと
+
+`<.*?>`は先頭の`<`がマッチした**後に**、そこからマッチする部分をできるだけ最小化しようと試みる。
+`<<<hoge>>>`に対して`<.*?>`をパターンマッチさせる際に行われる実際の処理の流れは、次のようなイメージになるだろう。
+
+```
+< # <までマッチ
+<< # <>のマッチに失敗、.の数を増やしてリトライ
+<< # <.までマッチ
+<<< # <.>のマッチに失敗、.の数を増やしてリトライ
+<<< # <..までマッチ
+<<<h # <..>のマッチに失敗、.の数を増やしてリトライ
+<<<h # <...までマッチ
+<<<ho # <...>のマッチに失敗、.の数を増やしてリトライ
+<<<ho # <....までマッチ
+<<<hog # <....>のマッチに失敗、.の数を増やしてリトライ
+<<<hog # <.....までマッチ
+<<<hoge # <.....>のマッチに失敗、.の数を増やしてリトライ
+<<<hoge # <......までマッチ
+<<<hoge> # <......>までマッチ
+```
+
+# 最短マッチにしたければどうするか
+この例の場合は、以下のような回避策がある。
+
+```ruby
+# Ruby 2.4.2
+"<<<hoge>>>".match(/<[^<]*?>/)[0] #=> "<hoge>"
+"<<<hoge>>>".match(/<(?!<).*?>/)[0] #=> "<hoge>"
+```
+
+どちらも、その文字よりも右に`<`が無い`<`に最初にマッチさせるようにして、言わば**最右**最短マッチを実現しようとするものである。
+1つ目の書き方は基本的な正規表現の構文のみを使っており、ほぼ全ての処理系で使用可能という利点があるが、汎用性に欠けるという欠点がある。(例えば後述のより複雑な例で最短マッチを実現するのは厳しいだろう)
+2つ目の正規表現は[否定先読み](http://d.hatena.ne.jp/satosystems/20100519/1274237784)と呼ばれる構文を使っており、使用できる処理系が限られるという欠点があるが、より汎用的であるという利点がある。
+
+# より複雑な例での最短マッチ
+`<em>`と`</em>`で囲まれた可能な限り短い文字列にマッチする正規表現を書きたいとする。
+例えば、
+
+```
+<em>あ<em>い<strong>う</strong>え</em>お</em>
+```
+
+という文字列に対して、
+
+```
+<em>い<strong>う</strong>え</em>
+```
+
+という部分文字列にマッチするようにしたい。
+この場合は否定先読みを使って、次のような書き方ができる。
+
+```ruby
+# Ruby 2.4.2
+"<em>あ<em>い<strong>う</strong>え</em>お</em>".match(/<em>(?!.*<em>).*?<\/em>/)[0] #=> "<em>い<strong>う</strong>え</em>"
+```
+
+# 注意点
+とはいえ、`<em>(?!.*<em>).*?</em>`ですら、結局は**最右**最短マッチでしかなく、真の意味での最短マッチではない。
+
+```
+<em>あ<em>い</em>う<em>え<strong>お</strong>か</em>き</em>
+```
+
+という文字列が入力として来たらどうなるだろうか?
+`<em>`と`</em>`で囲まれた**最短な**部分文字列は`<em>い</em>`であるべきだが、先の正規表現は`<em>え<strong>お</strong>か</em>`にマッチしてしまう。
+
+私は、真の意味での最短マッチを実現する方法を、寡聞にして知らない。(個人的な予想としては、正規表現エンジン側の実装があまりに大変になりすぎるので、最短マッチを実現することはできないのではないかと思う)
+
+# まとめ
+`.*?`は最短マッチではなく**最左**最短マッチである。
+**最右**最短マッチを実現する方法はある。
+**最短**マッチを実現する方法はあるのかどうかわからない。(ご存知の方がいましたらご教示いただけますと幸いです)