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

In article <[e-mail]>,
  "NARUSE, Yui" <[e-mail]> writes:

> nested_parentheses = /(?<pare>\(([^\(\)]+|\g<pare>)*\))/
>
> これだとちゃんとマッチします。
> もっとも、閉じる方向で括弧が余計な場合は大丈夫ですが、
> 開き括弧が余計にある場合は固まりますが。

([^\(\)]+)* と、繰り返しが 2重になって、括弧が出てこない部分
のありとあらゆる分割に挑戦するからでしょう。

たとえば、aaaaaaa は
aaaaaaa
aaaaaa a
aaaaa aa
aaaaa a a
aaaa aaa
aaaa aa a
aaaa a aa
aaaa a a a
aaa aaaa
aaa aaa a
aaa aa aa
aaa aa a a
aaa a aaa
aaa a aa a
aaa a a aa
aaa a a a a
aa aaaaa
...
というように分割できて、これを全部試せばそりゃ時間がかかりま
す。

挑戦しないようにするには、そんなところで分割しないようにすれ
ばいいわけで、
1. [^()]+ 同士が隣接しないようにパターンの構造を変える、
2. 直後が括弧であると先読みで指定する、
3. バックトラックを抑制する、
といった方法があります。

nested_parentheses = /
 (?<text>   [^()]*                                    ){0}
 (?<pare>    \g<text> ( \(\g<pare>\) \g<text> )*      ){0}
 \A\g<pare>\z/x

nested_parentheses = /
 (?<pare>    ( [^()]+(?=[()]) | \(\g<pare>\) )*       ){0}
 \A\g<pare>\z/x

nested_parentheses = /
 (?<pare>    ( (?> [^()]+ ) | \(\g<pare>\) )*         ){0}
 \A\g<pare>\z/x
-- 
[田中 哲][たなか あきら][Tanaka Akira]