1. anqooqie
Changes in body
Source | HTML | Preview
@@ -1,110 +1,143 @@
# TL;DR
`.*?`は最短マッチではなく**最左**最短マッチである。
# よくある誤解
```
<<<hoge>>>
```
という文字列に対して、
```
<.*?>
```
という正規表現をパターンマッチさせると、`.*?`は**最短**マッチと呼ばれているくらいなので、
```
<hoge>
```
という、**可能な限り短い**部分文字列にマッチしてくれるのだろう。
# 実際の挙動
```ruby
# Ruby 2.4.2
"<<<hoge>>>".match(/<.*?>/)[0] #=> "<<<hoge>"
```
# なぜこうなるのか
`.*?`は、
* 最短マッチ
* 最左マッチ
の2つの原則に従い、しかも最左マッチの原則の方が優先順位としては高いからである。
# より嚙み砕いて言うと
`<.*?>`は先頭の`<`がマッチした**後に**、そこからマッチする部分をできるだけ最小化しようと試みる。
`<<<hoge>>>`に対して`<.*?>`をパターンマッチさせる際に行われる実際の処理の流れは、次のようなイメージになるだろう。
```
< # <までマッチ
<< # <>のマッチに失敗、.の数を増やしてリトライ
<< # <.までマッチ
<<< # <.>のマッチに失敗、.の数を増やしてリトライ
<<< # <..までマッチ
<<<h # <..>のマッチに失敗、.の数を増やしてリトライ
<<<h # <...までマッチ
<<<ho # <...>のマッチに失敗、.の数を増やしてリトライ
<<<ho # <....までマッチ
<<<hog # <....>のマッチに失敗、.の数を増やしてリトライ
<<<hog # <.....までマッチ
<<<hoge # <.....>のマッチに失敗、.の数を増やしてリトライ
<<<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)と呼ばれる構文を使っており、使用できる処理系が限られるという欠点があるが、より汎用的であるという利点がある。
+ではうすればよいのだろうか。
+有力な代替案の一つは、「`<`も`>`も含まない0文字以上の文字列が、`<`と`>`で囲まれた文字列」にマッチする正規表現を作ればよい、という考え方である。
+そのような正規表現には、`<[^<>]*>`がある。
-# より複雑な例での最短マッチ
-`<em>`と`</em>`で囲まれた可能な限り短い文字列にマッチする正規表現を書きたいとする。
-例えば、
-
-```
-<em>あ<em>い<strong>う</strong>え</em>お</em>
+```ruby:動作例
+# Ruby 2.4.2
+"<<<hoge>>>".match(/<[^<>]*>/)[0] #=> "<hoge>"
```
-という文字列に対して、
+# `.*?`の出番は意外に少ない
-```
-<em>い<strong>う</strong>え</em>
-```
+問題をより一般化して考えると、`.*?`を使いたくなるケースの代表例として、ある開始文字列`foo`とある終了文字列`bar`に囲まれた、できるだけ短い文字列にマッチする正規表現を書きたいというケースがあるわけである。
+だが先ほど指摘した通り、`foo.*?bar`は期待した文字列に正しくマッチしてくれない。
+ではどうすればよいかというと、こういったケースでは、「`foo`も`bar`も含まない0文字以上の文字列が、`foo`と`bar`で囲まれた文字列」にマッチする正規表現を書く、という風に考えればよいのだ。
+`.*?`を無理して使う必要はない。
-いう部分文字列にマッチするようにしたい。
-この場合は否定先読みを使って、次のような書き方ができる
+`foo`が`<em>`、`bar`が`</em>`である場合を具体例して出そう。
+以下は、「`<em>`も`</em>`も含まない0文字以上の文字列が、`<em>`と`</em>`で囲まれた文字列」にマッチする正規表現である。
+そして、このどれもが正しい
-```ruby
-# Ruby 2.4.2
-"<em>あ<em>い<strong>う</strong>え</em>お</em>".match(/<em>(?!.*<em>).*?<\/em>/)[0] #=> "<em>い<strong>う</strong>え</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>`
-# 注意点
-とはいえ、`<em>(?!.*<em>).*?</em>`ですら、結局は**最右**最短マッチでしかなく、真の意味での最短マッチではない。
+```ruby:動作例
+# 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番目の書き方は[否定先読み](http://d.hatena.ne.jp/satosystems/20100519/1274237784)と呼ばれる構文を使った書き方である。
+この書き方は1番目の書き方よりも使用できる処理系が限られるという欠点があるが、より簡単に読み書きすることができる。
+基本的にはこれを使えばよいだろう。
+
+3番目の書き方は[非包含オペレータ](https://qiita.com/k-takata/items/4e45121081c83d3d5bfd)と呼ばれる構文を使った書き方である。
+この書き方はRuby 2.4.1以上限定(より正確に言うと[鬼雲](https://github.com/k-takata/Onigmo)限定)であるが、可読性はこの中で最高である。
+Rubyistは是非この書き方を使っていきたい。
-```
-<em>あ<em>い</em>う<em>え<strong>お</strong>か</em>き</em>
-```
+# まとめ
-という文字列が入力として来たらどうなるだろうか?
-`<em>`と`</em>`で囲まれた**最短な**部分文字列は`<em>い</em>`であるべきだが、先の正規表現は`<em>え<strong>お</strong>か</em>`にマッチしてしまう
+`.*?`は最短マッチではなく**最左**最短マッチである。
+`.*?`を使いたくなるが期待通りに動作してくれないケースの多くでは、否定先読みか非包含オペレータを使うことで問題が解決可能である
-私は、真の意味での最短マッチを実現する方法を、寡聞にして知らない。(個人的な予想としては、正規表現エンジン側の実装があまりに大変になりすぎるので、最短マッチを実現することはできないのではないかと思う)
+# 余談: 真の最短マッチは実現可能か
-# まとめ
-`.*?`は最短マッチではなく**最左**最短マッチである
-**最右**最短マッチを実現する方法はある
-**最短**マッチを実現する方法はあるのかどうかわからない。(ご存知の方がいましたらご教示いただけますと幸いです)
+`.*?`は**最左**最短マッチであるが、では、**真の**最短マッチは実現可能なのだろうか。
+つまり、例えば、`<em>`と`</em>`で囲まれた部分文字列が複数ありうるとき、その中で最も短い部分文字列にマッチする正規表現を書く方法はあるのだろうか?
+具体例としては、
+
+```
+<em>あ<em>い<strong>う</strong>え</em>お<em>か</em>き</em>
+```
+
+のような文字列が入力として来た場合、`<em>か</em>`にマッチさせるようにしたい。(`<em>い<strong>う</strong>え</em>`は、`<em>か</em>`より長いのでマッチさせない)
+
+コメントを募集したが、どうやら特殊な拡張構文を利用しない限りは難しそうということのようである。
+以下は、@HMMNRST さんによる、真の最短マッチの実現例である。
+コメントをそのまま引用する。
+
+> 真の最短マッチをエンジン自体の動作でなく構文で実現しようとすると、非正規な機能が必要な気がします。
+>
+> 例えば.NETであれば「グループ定義の均等化」というものが用意されているので、「この先の部分文字列にもっと短い一致候補が無い」という条件を書けるはずです。以下のコードはPowerShellで試しました。
+>
+> ```ps1
+> $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)|(?!))`は文字列長が同じ(スタックがぴったり空)だった場合に失敗とし、最短のうえで最左マッチに仕立てています。
+>
+> タグの長さが可変になったら、その分も数えなければいけないので同様の方法が使えるかはわかりません。