Perlの正規表現の限界を突破する - Islands in the byte stream (legacy)

Perlerなら誰しも一度はお世話になったことのあるであろう、大崎氏のPerlメモというサイトがあります。

Perlメモ

ここで紹介されているHTMLタグの正規表現は正規表現の叡智が詰め込まれたすばらしいものですが、Perlではこれである特定の文字列系に対してマッチを行うと、うまく動きません。具体的には、Perl 5.8系ではSEGVし、5.10以上だと警告が出た上で、本来成功するはずのマッチに失敗します。もっとも、これはこの正規表現に問題があるのではなく、Perlの正規表現エンジンの限界です。これは、バックトラックをCレベルの関数の再帰で実装しているためです。
例：

#!perl -w
# complex_re.pl
use strict;
my $tag_regex_ = q{[^"'<>]*(?:"[^"]*"[^"'<>]*|'[^']*'[^"'<>]*)*(?:>|(?=<)|$(?!\n))}; #'}}}}
my $comment_tag_regex =
    '<!(?:--[^-]*-(?:[^-]+-)*?-(?:[^>-]*(?:-[^>-]+)*?)??)*(?:>|$(?!\n)|--.*$)';
my $tag_regex = qq{$comment_tag_regex|<$tag_regex_};

for my $n(1 .. 64) {
    my $m = 2 ** $n;
    print $m, "\n";
    my $html = sprintf '<meta %s/>', "foo='bar' " x $m;
    $html =~ /$tag_regex/ or die "not ok\n";
}

結果：

$ perl complex_re.pl
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
Complex regular subexpression recursion limit (32766) exceeded at complex_re.pl line 13.
not ok

Ruby 1.9 (正規表現エンジンは鬼車 / oniguruma)ではこの問題は起こらないようです。

#!ruby -w
# Ruby 1.9.2 is OK.
# 注意！！！実行するとメモリを食いつぶすので適当に^Cで殺すこと！！！

tag_regex_ = %q{[^"'<>]*(?:"[^"]*"[^"'<>]*|'[^']*'[^"'<>]*)*(?:>|(?=<)|$(?!\n))}; #'}}}}
comment_tag_regex =
    '<!(?:--[^-]*-(?:[^-]+-)*?-(?:[^>-]*(?:-[^>-]+)*?)??)*(?:>|$(?!\n)|--.*$)';
tag_regex = /#{comment_tag_regex}|<#{tag_regex_}/;

(1 .. 64).each { |n|
    m = 2 ** n;
    puts m;
    html = sprintf '<meta %s/>', "foo='bar' " * m;
    html =~ tag_regex or raise "not ok\n";
}

HTMLタグのケースでは偶然この限界に当たることはまずないでしょうが、Xslateではこれまでで二度もこの限界に当たってしまったのでした。