なぜ、量指定子+は貪欲ではないのか

Question

「Copyright 2003.」という文字列に「^.*([0-9]+)」という正規表現をかけたさい、
後方参照の$1(\1)には、3.が代入されます。.*は、貪欲なので全て(Copyright 2003.)マッチしようとしますが、それだと[0-9]+が困るので、3.をマッチしていない状態に戻し、[0-9]+にマッチさせます。

ここで質問ですが、なぜ、[0-9]+は、3.で満足してしまうのでしょうか。0から9のうち何れかが一回以上且つ、+?ではないので貪欲なはずです。
貪欲ならば、条件にあうまで貪欲にマッチしようとするのですから、2003.までマッチしてもいいような気がするのですが、なぜ3.で終わってしまうのでしょうか。

また、[0-9]+は、0から9の数字のうち何れかが一回以上、ですが、.までマッチして$1(\1)に代入されています。これはなぜなのでしょうか。

Comments

[ikedas]

「…ですが、.までマッチして$1(\1)に代入されています」というくだりですが、本当にそうなっていますか。

[aaaaaaaa]

ご返答有難うございます。dreamweaverCS6で、拡張子がtxtのファイルの一行目に記述した正規表現「(^.*)([0-9]+)」で「Copyright 2003.」を「$1と$2」のように置換すると「Copyright 200と3.」となりました。つまり$2(※質問文では$1)には、3.が代入されています。

[ikedas]

「^.*」は ‘Copyright 200’ に、「[0-9]+」は ‘3’ にマッチし、マッチの範囲外の ‘.’ は置換されないまま、ということではないかと思います。

「$1と$2と」に置換すると「Copyright 200と3と.」になるはずです。

[aaaaaaaa]

ご返答有難うございました。なるほど、単なる勘違いでした。

Answer 1

まず、正規表現は連接できます。表現Aと表現Bがあるとき、表現ABは「Aがマッチする文字列の後にBがマッチする文字列が続く」ということを意味します。

Aが貪欲な量指定子を含む場合も、Aがマッチした後にBがマッチします。後のBがマッチし得ない場合にのみバックトラックが発生します (バックトラックを使う正規表現エンジンの場合)。

さて、貪欲であるということはよく「できるだけ長くマッチしようとすること」などと説明されますが、これは裏を返せば「できるだけ短くマッチ__しない__ようにすること」であると言えます。つまり、マッチの長さを伸ばすのは容易ですが、バックトラックによって縮めるのは難しいのです。

ご質問の例で説明します。先にマッチする.*は最初、できるだけ長くマッチしようとします。次に[0-9]+がマッチし得なかったことによってバックトラックが起きますが、.*は貪欲なので、マッチの長さを最小限しか縮めません。再びマッチを試すと、まず.*がマッチし、次に[0-9]+がマッチしますが、後者がマッチできる長さは1文字だけです。

このように、連接で先行する*が貪欲な量指定子であるために、後続する+は貪欲な量指定子であるにも関わらず、最短の文字列にしかマッチできません。

Answer 2

パターンを「(^.)([0-9]+)」とするとよくわかります
(^.)は「Copyright 200」がマッチします。
命題の件であれば「^.*?([0-9]+)」でマッチさせればよいでしょう

Comments

[aaaaaaaa]

ご回答有難うございます。なるほど正規表現は、左から右へ読みますが、左側に貪欲な*がいて、
それが3.以外を取ってしまうので、しょうがなく([0-9]+)は、3.のみを取得するわけですね。
それを解消するには、先に読み込まれる*を非貪欲にすればよい、と。

Answer 3

前者は .* が前にあるために優先的に最長一致しようとするからです。
後者は何かの間違いだと思います。

正規表現は実装によって様々ですので、JavaScript なら JavaScript と環境を明らかにした上で、該当部分のコードをもう少し詳しく載せた方が良いかと思います。

Comments

[Zuishin]

後ろを長く一致させたい場合は .* の代わりに [^\d]* とするのが定石です。