正規表現パターンの再帰呼び出しについて、再帰が停止しないパターンのチェックは、どうなっているのかを調べた。相互呼び出しで再帰している場合も、以下のような単純なものであればチェックされる。 "aaa" =~ /(?<n1>(?&n2))(?<n2>(?&n1))/ #=> Pattern subroutine</n2></n1>…

同じ名前を重複して定義した場合の仕様を確認した。 後方参照では、一番左のグループだけを参照する。 "abcb" =~ /(a)(?'name'b)(?'name'c)\k'name'/鬼車の場合は、グループ番号の大きいものから順番に、マッチングが成功するまで全部参照する。理由があって…

Perlのnamed groupの動作を確認してみた。 named groupにはグループ番号も付加されている。これは鬼車と同じなので助かった。.NETの場合は違っていたような気がする。 "abb" =~ /(a)(?<name>b)\g{-1}/ #=> $1 = "a", $2 = "b"それにしても、\g{N},\g{name}で後方参</name>…

Regular Expression Matching Can Be Simple And Fastを読んで、Perlでの指数関数的発散の対処方法は、鬼車の実装方法と大体同じだろうということが分かった。 "Backtracking with memoization"と説明してあった。ところで、この論文に書いてある例をPerlで…

Perlでは、\sと\p{Space}が厳密には同じではないということを教えてもらった。 [[:space:]] == \p{Space} != \s == \p{SpacePerl}\p{Space}と\p{SpacePerl}では、U+000Bが含まれるかどうかが違っている。どうして二種類必要なのかはわからない。

昨日、4.4.0をRuby 1.9にマージした。 組合せ爆発の対応について、Perlでは対応できているのに、鬼車では対応できていないパターンがあれば教えて欲しい。 多分、見つかっても対応はしないと思うが、把握しておきたい。

Perlが(A*){0,10}に対処していないのなら、もう既に鬼車のほうが対処できているパターンが多いのではないか？ (?:A*){0,10}には以前から対処してあるのだから。 しかし、Perlが対処できるパターンの仕様を理解できていないので、断言はできない。

あれ、変だな？ $s = "a" x 100 . "z"; $s =~ /\A(a*){0,10}\z/;これをPerlは対処していると思っていたのだが、今確認してみるとできていない。それどころか、以下のようにキャプチャなしにしてもできない。 $s =~ /\A(?:a*){0,10}\z/;

(?:...){1,1}で囲んだだけで、チェックが働かない。 $s = " foo " x 50 . "z"; $s =~ /(?:(?:\s*foo\s*)*){1,1}\z/;

チェックする位置が増えても、この程度なら問題ない。 $s = " foo " x 100 . "z"; $s =~ /(?:\s*foo\s*)*(?:\s*foo\s*)*(?:\s*foo\s*)* (?:\s*foo\s*)*(?:\s*foo\s*)*(?:\s*foo\s*)*(?:\s*foo\s*)* (?:\s*foo\s*)*(?:\s*foo\s*)*(?:\s*foo\s*)*\z/;しかし、…

$s = " foo " x 100 . "z"; $s =~ /(?:(\s*)foo\s*)*\1\z/;これが停止しないのは仕方ないが、 $s = " foo " x 100 . "z"; $s =~ /(?:\s*foo\s*)*()\1\z/;これも停止しないのは意外。 後方参照が使用されていれば無条件でチェックが働かなくなるようだ。

Perlも失敗状態を記録しているというのを、何かで読んだ気がするので、同じ方法だろうと思っていました。が、具体的な実装方法は違うかもしれないですね。

CygwinとFedora Core 4です。 Fedora Core 4は手元にないですが、Cygwinは、 $ perl -v This is perl, v5.8.7 built for cygwin-thread-multi-64int (with 1 registered patch, see perl -V for more detail) ...

念のため、文字列が長いときに、Perlで極端に処理が遅くなってしまう場合がないか調べてみよう。(Perl 5.8.7) と思って実行すると、コアを吐いてしまった。 $s = " foo " x 8000 . "z"; $s =~ /(?:\s*foo\s*)*\z/;8000ではなく、もっと小さい値なら動いた。 …