From: Tanaka Akira <akr@...17n.org>
Date: 2003-05-19T15:03:11+09:00
Subject: [ruby-dev:20209] /()*\1/ =~ ""

元ネタは BTS および Matzにっきなのですが、Matzにっきの調子が悪くてつっ
こめない上にどんどん長文になる気がするのでこちらで。

発端は /()*\1/ =~ "" が成功すべきかどうか、ということです。
なお、現時点の 1.8 では失敗し、ちょっと前の鬼車では失敗します。

# 最新の鬼車は試してません。

問題は繰り返しの中身が長さ 0 にマッチしたときをどう扱うかということな
のですが、まぁ、無限ループを防ぐにはちょっと特殊な扱いをしないといけな
いのは確かで、それをどんな具合に特殊にするか、というのが問題です。

要はどうバックトラックするかということなんですが。

# 求む! Prolog 使い

最初、私は 2回以上マッチしても意味がないんじゃないかなぁと思って、まず
1回を試して次に 0回を試せばいいんじゃないかと思ったんですが、考えてみ
るとこれでもうまくいかないケースがあります。

たとえば、
  /(?:()|()|()|()|()|())*\2\5/ =~ ""
というのを考えると、これは 2回(以上)マッチしてどこかで 2つめと 5つめを
(順不同で)通るようなのを見つけないといけません。

# これは鬼車でもマッチしません、が、perl 5.6.1 はマッチします。

さらに、/(?:()|()|()|(x)|()|())*\2b\5/ =~ "x" なんてのも考えられて、こ
れは 3回(以上)マッチして、2つめ、4つめ、5つめを通らないといけません。

# これは perl でもマッチしません。

まぁ、1.8 や鬼車それぞれの仕様ということで手をつけないというのが妥当な
ような気もしますが、なにか思うところのある人はいますか?
-- 
[田中 哲][たなか あきら][Tanaka Akira]