[ruby-dev:20225] Re: /()*\1/ =~ ""

In article <5FD2F0CF7F5D7F44B00F36870B9E78B508DE5024@SBG-EX4>,
  [e-mail] writes:

> こういう場合があるんですね。考えていませんでした。
> 選択肢の数だけの繰り返しは、必ず試すように変更すれば良いような気がしますが、
> それだけでどのようなパターンにも対応できるのか、わかりません。
> 誰か教えてください。

考えてみました。

基本的には全部試すことになります。
ただ、本当に全部試すと無限ループになることがあるので、それを検査する必
要があって、そこが微妙です。

その検査は、繰り返しを一回進めて状態が変化しない場合はそれ以降は試さな
いというのが基本的な条件になります。たぶん。

ここで、状態というのは、

(1) マッチにおける現在位置
(2) capture した場所の開始・終了位置

というのの直積です。

なんでこれで無限ループにならないのかというと、マッチにおける現在位置と
capture の開始・終了位置は単調に変化し、決して減少しないからです。決し
て減少しない上に、さらに上の条件で同じ状態が続くことがなくなります。ま
た、対象の文字列は有限ですから、位置がだんだん増加していけばそのうち終
ります。

ただ、実装上は (2) を

(2) capture した文字列

と変えて効率を稼いだほうがいいかもしれません。

こうしても対象文字列全体がマッチするかどうかには影響を与えません。なぜ
かというと、backreference は位置を参照しないからです。

また、こうしても終了することは同じです。これは開始・終了位置が等しけれ
ばその文字列も同じなので、文字列が違うときには常に位置が変わっているこ
とから示せます。

ただ、これをやると、MatchData#{begin,end} がちょっと変わるかも知れない
という気もします。
-- 
[田中 哲][たなか あきら][Tanaka Akira]