2006年4月15日

[ruby-list:42029] Re: 正規表現のマッチングがフリーズしてしまうコード

木村です。

conundrum / さんは書きました (2006/04/15 0:52):
> conundrumです。
>
> 仕事で、C++のソースコードをスキャンするRubyスクリプトを書いています。
> なんでそんなことしているかというと、とても特殊な組み込みC++でして、
> 奇怪なコーディングルールがたくさんあって、

> それに違反していないかどうかを、チェックするため。
>
> 先日、そのC++コードをスキャンするRubyスクリプトが、ハングアップするように
> なってしまいました。
> 原因は、正規表現のマッチングで固まってしまうことでした。

まつもとさんのリプライにもあったように、バックトラックが
莫大な回数になったためにハングアップしたかのように見えている
のだと思います。面倒なので回数の計算はしませんが(^^;
簡単に言うと、「(バックトラックする)繰り返しを繰り返すと
バックトラックが幾何級数的に増える可能性がある」ということです。

試しに、正規表現を必要ないところではバックトラックを
抑止するようにすると、すぐに返ってくるようになります。

ただ、そのように書き換えても希望通りには動いていないと思いますが。
#望むようには動かないが書いたようには動く。

まつもとさんの挙げられた「詳説 正規表現」の 7.8.1 とか
6.1.4 あたりが参考になると思います。7.8.1にあるような
正規表現がRubyでも書けるといいんですけどね。

--
木村浩一
I thought what I'd do was, I'd pretend I was one of those deaf-mutes.
mail kbk at kt.rim.or.jp
web www.kt.rim.or.jp/~kbk/index.html#zakkicho
homepage3.nifty.com/farstar/


投稿者 xml-rpc : 2006年4月15日 04:21
役に立ちました?:
過去のフィードバック 平均:(0) 総合:(0) 投票回数:(0)
本記事へのTrackback: http://hoop.euqset.org/blog/mt-tb2006.cgi/41885
トラックバック
コメント
コメントする




画像の中に見える文字を入力してください。