From: matz@... (Yukihiro Matsumoto)
Date: 2000-08-21T00:54:17+09:00
Subject: [ruby-dev:10657] Re: a regex bug?

まつもと ゆきひろです

In message "[ruby-dev:10655] a regex bug?"
    on 00/08/20, "Akinori -Aki- MUSHA" <knu@idaemons.org> writes:

|　さっき、また別の FreeBSD 開発者から ruby の正規表現の不具合を
|見つけたという報告をもらいました。

これは不具合ではないですね。NFAを使っているものはこのパター
ンはのきなみ全滅じゃないでしょうか。

regexpマッチは欲張りなので、

  (1+){2}

に対して 11 をマッチさせると、最初の1+が両方の1を飲み込んで
しまい、次の1+にマッチさせるものが残っていないので、全体とし
て失敗します。一方

  (1*){2}

の場合は最初の1*が11にマッチしても、次の空(くう)に1*がマッチ
できるので成功できるというわけです。これはNFA型の限界です。
一方、DFA型ではそのような場合でも適切にバックトラックが行え
ますから、egrepなどでマッチするのはそういう理由だと思います。
私の記憶が正しければGNU grepは、使える場合にはDFAを使うこと
で高速化していたと思います。

たとえば、egrepでもDFA型で対応できないバックリファレンスを含
むものは、NFA型を使うことになるので同じような状況で、同じよ
うな理由で失敗します。

$ echo " 111 " | egrep -E ' (1+){2}\1 '
$ echo " 11 "  | egrep -E '( )(1+){2}\1'

これはこういうものだと考えてもらう方が良いと思います。より詳
しくは『詳説・正規表現』(オライリー・ジャパン／オーム社)を参
照してください。

|となり、 GNU regex + Perl 拡張を使っている Perl と Ruby だけが
|マッチしてくれません。

「GNU regex + Perl 拡張を使っている」のはRubyだけです。Perl
は「Henry Spencer V8 regexp + Perl拡張」です。

                            まつもと ゆきひろ /:|)