脳log[正規表現: 2008-01-16～]

♪ [正規表現] 遅い正規表現

/\/(?:\\.|[^\n\\\/])+\/[gim]*(?!\w)/g
/\/(?:\\.|[^\n\\\/]+)+\/[gim]*(?!\w)/g // 死ぬほど遅い

どちらも同じく /regexp/i みたいな正規表現リテラルにマッチするのだが、下の方がブラウザが固まるほど遅い*。バックトラックの影響だろうか、これまで気にしてこなかったが……。原因が推測できない(無能)のがイタイ。(この日記、SHJSによるソースコードハイライトを多用していると読み込み完了直前にブラウザの反応がいっとき消えている。正規表現を最適化する余地があるならしたい)

昨日 rubyco（るびこ）の日記 (2007-06-20 正規表現の選択) 経由でウィッシュリストに入れた『詳説 正規表現 第2版』⁑がタイムリーすぎる。

 いけないバックトラックの例

 reg = /.*x|a/
 s = "a" * 11_000_000
 m = reg.match(s)

http://d.hatena.ne.jp/kkos/20060801#1154438784

最終更新: 2016-11-12T11:41+0900

♪ [正規表現][Ruby] 鬼車すごい。正規表現で再帰ができる。

Rubyの、括弧を使った %記法だって。

irb19> re = /%[Qq]?(?<brace>\{[^\{}]*(?:\g<brace>[^\{}]*)*})/
irb19> strings = %w(%{z}a %{a{b}z}c %{a{b}c{d{e}f}z}g %{{{{}}}z}a %{a{b}c %{z}a}b)
irb19> strings.each{|str| p str[re] }
"%{z}"
"%{a{b}z}"
"%{a{b}c{d{e}f}z}"
"%{{{{}}}z}"
nil
"%{z}"
=> ["%{z}a", "%{a{b}z}c", "%{a{b}c{d{e}f}z}g", "%{{{{}}}z}a", "%{a{b}c", "%{z}a}b"]

どの例も正しい範囲( %{ から z} まで)を切り取っているのがわかる。

1. この機能が使える鬼車がのってる Rubyは 1.9.0。
2. PCRE(ver 4.x)の (?P<name>...)と(?P>name)が同じものにあたるらしい。へー、そんなものが。javascript(JScript)の正規表現も新しくならんかな
3. .NETの (?<open>...)と(?<close-open>...)も同じことができるらしいが、正直わからん*⁑⁂
4. http://www.kt.rim.or.jp/~kbk/regex/regex.html < 正規表現の各種実装の違いがよくわかる。

 追記@2008-05-09: 対応する括弧にマッチする正規表現のヴァリエイション(<くどい表記だな)

/%[Qq]?(?<brace>\{(?:[^\{}]++|\g<brace>)*})/

若干速い。同じパターン( [^\{}] )の繰り返しも存在しない。http://fleur.hio.jp/perldoc/perl/5.10.0/pod/perl5100delta.mix.html#Regular_expressions を参考にした。

/%[Qq]?(?<brace>\{(?:[^\{}]+|\g<brace>)*})/

上のものの + が一つ落ちたもの。開き括弧が余分にある文字列を食わせると待てども待てども返ってこない。 http://mlog.euqset.org/archives/ruby-list/42232.html で既に書かれている。それに対する返答が http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-list/42233 。