目次
トップへ
はじめに
|
にお願いします．こう書いた方がいい，
動かん，わからん，バグってる，これ書け，などなどお待ちしています．
全能な正規表現
トップへ(??{ code }) (?{ code })
マッチしない正規表現
トップへ(?!)すべてにマッチする正規表現，空文字列，の否定先読みという意味．
や [^\s\S]などでもよい．しかし， [^\w\W]では utf8 pragma を有効にした環境下において， [^\x00-\xFF]以降の文字にマッチしてしまう． \x{100}
， (?(condition)yes-pattern)と併用することで，ある条件下でマッチさせないことが可能となる． (?(condition)yes-pattern|no-pattern)(?(?{ code })(?!)) (?(?{ code })|(?!))
ある文字列とある文字列を含むものにマッチする正規表現
トップへ(?=.*foo)(?=.*bar) (?=.*foo)(?=.*bar)(?=.*hoge)
ある文字列を含まないものにマッチする正規表現
トップへ(?:(?!foo).)*fooを含まない直前までにマッチする正規表現． 「XXXXXfoo」に対して「XXXXX」がマッチ． 1文字以上にマッチさせたい場合(空文字列にマッチさせたくない場合)は， * を + に変える．
(?:(?!foo).)*(?:fo|f)?マッチする部分にfooを含まない正規表現． 「XXXXXfoo」に対して「XXXXXfo」がマッチ． 1文字以上にマッチさせたい場合(空文字列にマッチさせたくない場合)は下記の通り．
マッチする部分にfoobarを含まない正規表現は下記の通り．(?:(?:(?!foo).)+(?:fo|f)?|fo|f)1文字以上にマッチさせたい場合(空文字列にマッチさせたくない場合)は下記の通り．(?:(?!foobar).)*(?:fooba|foob|foo|fo|f)?(?:(?:(?!foobar).)+(?:fooba|foob|foo|fo|f)?|fooba|foob|foo|fo|f)
正規表現で不定方程式を解く
トップへ# solve for 12x + 15y + 16z = 281, maximizing x if (($X, $Y, $Z) = (('o' x 281) =~ /^(o*)\1{11}(o*)\2{14}(o*)\3{15}$/)) { ($x, $y, $z) = (length($X), length($Y), length($Z)); print "One solution is: x=$x; y=$y; z=$z.\n"; } else { print "No solution.\n"; } 実行結果: % perl diophantine-equations.pl One solution is: x=17; y=3; z=2.
正規表現で素因数分解する
トップへ# [regexp 23]より # Perl Cookbook のコードをわずかに修正した (途中経過を出力) while (<>) { chomp; for ($N = ('o' x $_); $N =~ /^(oo+?)\1+$/; $N =~ s/$1/o/g) { print length($1), " $N // ", length($N), "\n"; } print length($N), " $N // ", length($N), "\n"; print "\n"; } 実行例: % perl prime-pattern.pl 30 2 oooooooooooooooooooooooooooooo // 30 3 ooooooooooooooo // 15 5 ooooo // 5 54 2 oooooooooooooooooooooooooooooooooooooooooooooooooooooo // 54 3 ooooooooooooooooooooooooooo // 27 3 ooooooooo // 9 3 ooo // 3
回文にマッチする正規表現
トップへ# 再帰版 $palindrome = qr{ (\w) (?:\w|(??{$palindrome}))? \1 }x; /^$palindrome$/# 全能版 ^(\w+)\w?(??{reverse $1})$
入れ子を許した括弧内を削除する
トップへ1 while $str =~ s/\([^()]*\)//g;
入れ子を許した括弧内にマッチさせる
トップへ$openclose = qr/\([^()]*(?:(??{$openclose})[^()]*)*\)/; while ($str =~ /($openclose)/g) { print $1, "\n"; }
タグの外側だけ対象に置換する
トップへs/((?:\G|>)[^<]*?)foo/$1bar/g;タグの外側だけ置換するためにはタグの外側であることがわかる必要がある． タグの外側とはどういう場合かというのを表現した部分が
である． タグが閉じたところから次のタグが始まる前の場所はタグの外側である．つまり， ((?:\G|>)[^<]*?)である．また，前回置換した場所も タグの外側を置換したのであるから当然タグの外側である．その場所から次のタグが 始まる前の場所もタグの外側である．つまり， >[^<]*?である． \G[^<]*?一旦，タグの外側の部分を抜き出してから，その部分に対して置換する方法もある． 以下がその方法だが，置換を
修飾子 を使って行なっているのでスマートとは言い難い． 置換ではなく，タグの外側の部分だけ抜き出す目的で使う分には，マッチした部分に 余計なものが入らないという点において意味がある．es/(?:^|(?<=>))([^<]*)/(my $tmp = $1) =~ s!foo!bar!g; $tmp/egs;タグの正規表現を
とした場合， タグの外側の正規表現は <.*?>のときの (?:^|>)(.*?)(?:$|<)となる． $1>と<は後読みと先読みにして外に出すことができるので，結局 タグの外側の正規表現はとなる． (?:^|(?<=>))(.*?)(?:$|(?=<))ところが，文頭からタグが始まる場合に
修飾子 をつけて繰り返し置換させようとするとまずいことになる． 文頭からタグが始まる場合gが最初に マッチする．つまり，文頭の ^()(?=<)<の直前の隙間の空文字列が マッチし，パターンマッチの開始場所は最初の地点から動かない．これでは次に修飾子 によって再度置換しにいったとしても 同じ位置で永久に繰り返すことになってしまう．そこで，Perl では空文字列に マッチするような場合には，初回は空文字列がマッチするがそれ以降は マッチせずに必ずg1文字分 は進むようにマッチしようとする． これにより永久に繰り返すことを防いでいるわけだが，その結果，今度はが文頭の .*?<を含むようになり， 一旦文頭の<を含んでしまったら，文末か次の<が来るまで伸び続け，結局文頭から始まるタグを含んで マッチしてしまうことになる．そこで，
が .*?<を含まない ようにすることを考えると，となる． この時点で最初の正規表現はもう少し簡単になることがわかる．つまり， [^<]*?というのは ([^<]*?)(?:$|(?=<))とすることができる． ([^<]*)タグの正規表現が
とできない場合は， Perlメモ の 「自動で URI(URL) のリンクを張る」 を参照してください． <.*?>
タグの閉じ忘れをチェックする
トップへopen(PERL, '< perl.htm') or die "perl.htm: $!\n"; { local $/ = undef; $html = <PERL>; } close(PERL); while ($html =~ /<(NOBR|CODE|B|PRE|FONT)\b # ある開始タグから (?= ( (?:(?!<\/\1>).)*? # そのタグが閉じられる前に (?:<\1\b|$) # また開始タグ or 終わり ) ) /sigx) { print "<$1$2\n"; }
XMLタグを加工する
トップへ<?xml version="1.0"?> <div class="memo"> <div class="author"> <div class="name">okabe</div> </div> <div class="subject">test</div> <div class="body"> <div class="paragraph"> This is a <div class="emphasis">sample</div> script. </div> </div> </div> というxmlファイルを <?xml version="1.0"?> <memo> <author> <name>okabe</name> </author> <subject>test</subject> <body> <paragraph> This is a <emphasis>sample</emphasis> script. </paragraph> </body> </memo> という形に変換する． 1 while ($this =~ s/<div\sclass="([^"]+)"> ((?:(?!<div).)*?) <\/div>/<$1>$2<\/$1>/xsg); my @name; $this =~ s/<div\sclass="([^"]+)">(?{push(@name, $1)}) | <\/div>/$1 ? "<$1>" : "<\/@{[pop(@name)]}>"/xge;
xy を含まないものにマッチする正規表現
トップへ[regexp 60]より 遷移図が書ければ答は求まるのですが、結局 [^x] x . <----+ <----+ <----+ | | | | | | ＼／ x ＼／ y ＼／ ０ ----> １ ----> ２ | | | [^xy] | <----------+ です。 ０から始まって２で終るのが「xy を含む」ということですから、求めるも のはその否定すなわち、０か１が終了状態の DFA です。 で、素朴なアルゴリズムで解くと「xy を含まない文字列」は ([^x]|x+[^xy])*x* が答です。他には | を展開して [^x]*(x+[^xy][^x]*)*x* とか、 *y(x*[^xy]y*)*x* とかがあります。 連立方程式では p = p[^x] + q[^xy] + ε q = px + qx を解いて、答は p + q。
xyz を含まないものにマッチする正規表現
トップへ[regexp 60]より 遷移図は x <-----------+ [^x] | x | <----+ <----+ | | | | | | ＼／ x ＼／ y | z ０ ----> １ ----> ２ ----> ３(DEAD) | | | | [^xy] | | <----------+ | | [^xz] | <--------------------- 遷移図の 0, 1, 2 にマッチする正規表現を p, q, r とすると， (1) p = p[^x] + q[^xy] + r[^xz] + ε (2) q = px + qx + rx (3) r = qy (3) を (2) に代入して， (4) q = px + qx + qyx = px + q(x + yx) = px(x + yx)* # Arden の補題(x = xa + b = ba*) (3), (4) を (1) に代入して， p = p[^x] + q[^xy] + qy[^xz] + ε = p[^x] + q([^xy] + y[^xz]) + ε = p[^x] + px(x + yx)*([^xy] + y[^xz]) + ε = p([^x] + x(x + yx)*([^xy] + y[^xz])) + ε = ([^x] + x(x + yx)*([^xy] + y[^xz]))* 最終的に求める正規表現は pまたはqまたはr，すなわち，p + q + r なので， p + q + r = p + q + qy = p + qy? = p + px(x + yx)*y? = p(x(x + yx)*y?)? = ([^x] + x(x + yx)*([^xy] + y[^xz]))*(x(x + yx)*y?)? = ([^x] + x(y?x)*([^xy] + y[^xz]))*(x(y?x)*y?)? + を | に置き換えて完成 ([^x]|x(y?x)*([^xy]|y[^xz]))*(x(y?x)*y?)?
式を簡略化する
トップへ↓こんな式を ^((b)|(a)((aa)|bb)*((ab)|ba))(((bb)|aa)|((ba)|ab)((aa)|bb)*((ab)|ba))*$ ↓こんな感じに簡略化したい ^(b|a(aa|bb)*(ab|ba))(aa|bb|(ab|ba)(aa|bb)*(ab|ba))*$sub simplify { my $expr = shift; $openclose = qr/[^()]*(?:\((??{$openclose})\)[^()]*)*/; $no_or = qr/[^(|)]*(?:\((??{$openclose})\)[^(|)]*)*/; $term = qr/(?:(?:\w+|\((??{$term})(?:\|(??{$term}))*\))\*?)/; use re 'eval'; 1 while (0 or $expr =~ s/\((\w)\)/$1/g or # (a)→a $expr =~ s/\(($no_or)\)(?![*?])/$1/g or # (expr)→expr $expr =~ s/^\(($openclose)\)$/$1/g or # ^(expr)$→expr $expr =~ s/\((\($openclose\))\)/$1/g or # ((expr))→(expr) $expr =~ s/((?:^|\()(?:$term+\|)*) \( ($term+(?:\|$term+)+) \) ((?:\|$term+)*(?:\)|$))/$1$2$3/gx or # (expr1|(expr2|expr3))→(expr1|expr2|expr3) $expr =~ s/\((\w)[*?]\)\*/$1*/g or # (a[*?])*→a* $expr =~ s/\((\w)\*\)[*?]/$1*/g or # (a*)[*?]→a* $expr =~ s/(\w)[*?]\1\*/$1*/g or # a[*?]a*→a* $expr =~ s/(\w)\*\1[*?]/$1*/g or # a*a[*?]→a* $expr =~ s/\(($openclose)\)[*?]\(\1\)\*/($1)*/g or # (expr)[*?](expr)*→(expr)* $expr =~ s/\(($openclose)\)\*\(\1\)[*?]/($1)*/g or # (expr)*(expr)[*?]→(expr)* $expr =~ s/\((\($openclose\))[*?]\)\*/$1*/g or # ((expr)[*?])*→(expr)* $expr =~ s/\((\($openclose\)\*)\)[*?]/$1/g or # ((expr)*)[*?]→(abc)* $expr =~ s/(^|[(|])($no_or)((?:\|$no_or)*)\|\2($|[|)])/$1$2$3$4/ or # expr1|expr2|expr1→expr1|expr2 $expr =~ s/(^|[(|])($no_or)\|($no_or)($|[|)]) (?(?{(length $2 > length $3 or (length $2 == length $3 and ($2 cmp $3) > 0)) })|(?!))/$1$3|$2$4/x or # expr1|expr2→sort(expr1|expr2) 0); no re 'eval'; $expr; }
タグを無視して折り返す
トップへ基本的に指定バイト数で<BR>を挿入 日本語に対応(文字化けしないように多バイト文字を分割しない) タグは無視して折り返しバイト数を数える 元から<BR>が入っている場合にも対応 タグの中で間違って折り返さない$html = 'あaい<FOO>う<BAR>え<FOO>おかき<BR>くけaこ<FOO><BAR>さaしすせそたちつてとな<123456789012345>に'; $maxBytes = 10; # 指定バイト数 # EUC-JP文字 $ascii = '[\x00-\x7F]'; # 1バイト EUC-JP文字 $twoBytes = '(?:[\x8E\xA1-\xFE][\xA1-\xFE])'; # 2バイト EUC-JP文字 $threeBytes = '(?:\x8F[\xA1-\xFE][\xA1-\xFE])'; # 3バイト EUC-JP文字 $character = "(?:$ascii|$twoBytes|$threeBytes)"; # EUC-JP文字 $skip = qr/(?>(?:(?!<BR>)<[^>]*>)*)/; use re 'eval'; $html =~ s/\G((?:<[^>]*>|(?!<)$character)*?) ((?: $skip ((?!<BR>)$character) (?{local $len = $len + length($3)}) )*?) (?(?=$skip($character)) (?(?{$maxBytes >= $len and $len > $maxBytes - length($4)})|(?!))) (?!<BR>|$) /$1$2<BR>/xigo; no re 'eval'; print $html, "\n";
禁則処理しつつ折り返す
トップへPerlメモの禁則処理しつつ折り返すスクリプトと 同等の機能を正規表現で実現するrequire 'jcode.pl'; # EUC-JP文字 $ascii = '[\x00-\x7F]'; # 1バイト EUC-JP文字 $twoBytes = '(?:[\x8E\xA1-\xFE][\xA1-\xFE])'; # 2バイト EUC-JP文字 $threeBytes = '(?:\x8F[\xA1-\xFE][\xA1-\xFE])'; # 3バイト EUC-JP文字 $character = "(?:$ascii|$twoBytes|$threeBytes)"; # EUC-JP文字 $space = '(?:\s|\xA1\xA1)'; # 削除する行頭行末空白 $no_begin = "!%),.:;?]}￠°’”‰′″℃、。々〉》」』】〕" . "ぁぃぅぇぉっゃゅょゎ゛゜ゝゞァィゥェォッャュョヮヵヶ" . "・ーヽヾ！％），．：；？］｝"; # 行頭禁則文字 $no_begin_jisx0201 = "。」、・ァィゥェォャュョッー゛゜"; jcode::z2h_euc(\$no_begin_jisx0201); $no_begin .= $no_begin_jisx0201; # 行頭禁則文字(半角カタカナ) $no_end = "\$([{￡\‘“〈《「『【〔＄（［｛￥"; # 行末禁則文字 $no_end_jisx0201 = "「"; jcode::z2h_euc(\$no_end_jisx0201); $no_end .= $no_end_jisx0201; # 行末禁則文字(半角カタカナ) $allow_end = $no_begin; # ぶら下げ行頭禁則文字 $no_begin1 = '[' . join('', map {quotemeta} grep {defined} $no_begin =~ /(?:($ascii)|$twoBytes|$threeBytes)/xg) . ']'; $no_begin2 = '(?:' . join('|', grep {defined} $no_begin =~ /(?:$ascii|($twoBytes)|$threeBytes)/xg) . ')'; $no_end1 = '[' . join('', map {quotemeta} grep {defined} $no_end =~ /(?:($ascii)|$twoBytes|$threeBytes)/xg) . ']'; $no_end2 = '(?:' . join('|', grep {defined} $no_end =~ /(?:$ascii|($twoBytes)|$threeBytes)/xg) . ')'; $no_begin = '(?:' . join('|', map {quotemeta} $no_begin =~ /$character/g) . ')'; $allow_end = $no_begin; # ぶら下げ行頭禁則文字 sub fold_properly { my $str = shift; ($basesize, $maxsize) = @_; # グローバル変数にしないと途中で変更できない use re 'eval'; $str =~ tr/\t\n\r\f/ /; # 空白文字をスペースに変換 $str =~ s/^$space+//o; # 行頭空白削除 ($folded, undef, $str) = $str =~ /^ (($character*(?<!$no_end1)(?<!$no_end2)) # 行末禁則チェック # 基本長チェック (?(?{length($2) - ($2 =~ tr|\x8E||) > $basesize})(?!)) $allow_end*?) # ぶら下げ (?<!$no_end1)(?<!$no_end2) # 行末禁則チェック(ぶら下げ含) # 最大長チェック (?(?{length($1) - ($1 =~ tr|\x8E||) > $maxsize})(?!)) (?(?<=\w)(?!\w)) # 単語分割しない ((?!$space*$no_begin)$character*?)$/xo; # 行頭禁則チェック ($folded, $str) = $str =~ /^ ($character*) (?(?{length($1) - ($1 =~ tr|\x8E||) > $basesize})(?!)) (.*)$/xo if $folded eq ''; no re 'eval'; $folded =~ s/^($character*?(?=$space))$space+$/$1/ox; # 行末空白削除 ($folded, $str); } $str = 'aこはテストで すなるほどテストです．' x 2; jcode::z2h_euc(\$str); while (length($str)) { (my $folded, $str) = fold_properly($str, 10, 12); print "$folded\n"; }
a が偶数個で b が奇数個の文字列にマッチする正規表現
トップへ^(b|a(aa|bb)*(ab|ba))(aa|bb|(ab|ba)(aa|bb)*(ab|ba))*$$states = 4; @matrix = ([qw(X X X a b)], # A = Bb + Ca [qw(X X X b a)], # D = Ba + Cb [qw(X a b X X)], # C = Aa + Db [qw(E b a X X)], # B = Ab + Da + e ); sub rsrt { # r = s + rt → r = st* my $j = shift; if ($matrix[$j][$j + 1] ne 'X') { foreach my $i (0 .. $j) { if ($matrix[$j][$i] ne 'X') { $matrix[$j][$i] .= "$matrix[$j][$j + 1]*"; } } } } sub substitute { my $y = shift; foreach my $i (0 .. $y - 1) { foreach my $j (0 .. $y) { if ($matrix[$i][$j] ne 'X') { if ("$matrix[$y][$j]$matrix[$i][$y + 1]" !~ /X/) { $matrix[$i][$j] = "($matrix[$i][$j]|$matrix[$y][$j]$matrix[$i][$y + 1])"; } } else { if ("$matrix[$y][$j]$matrix[$i][$y + 1]" !~ /X/) { $matrix[$i][$j] = "($matrix[$y][$j]$matrix[$i][$y + 1])"; } } } } } sub resolv { for (my $j = $states - 1; $j > 0; $j--) { rsrt($j); substitute($j); } rsrt(0); $matrix[0][0] =~ s/E//g; $matrix[0][0] = '^' . $matrix[0][0] . '$'; } $result = resolv(); $result = simplify($result); print $result;
は 「式を簡略化する」参照． simplify()正規表現を作る過程を見られるようにした改変バージョン(宮沢さん作)は こちら．
2 の倍数にマッチする正規表現
トップへ# 全能版 ^(\d+)(?(?{$1 % 2})(?!))$ # 純粋版 8bytes [02468]$
3 の倍数にマッチする正規表現
トップへ# 全能版 ^(\d+)(?(?{$1 % 3})(?!))$ # 純粋版 109bytes ^(([0369]|[258][0369]*[147])|([147]|[258][0369]*[258])([0369]|[147 ][0369]*[258])*([258]|[147][0369]*[147]))*$[regexp 50]より まず、3 を法として、0 となる数値にマッチする正規表現を p, 1 となる数値 にマッチするものを q, 2 となる数値にマッチするものを r とします。 (まぁ、DFA の各状態に対応する正規表現を考えるわけです。) ここで、p が最終的な答えになるわけですが、まずは、DFA から次のような連 立方程式を作ります。 (1) p = p0 + q2 + r1 + ε (2) q = p1 + q0 + r2 (3) r = p2 + q1 + r0 # ある状態にたどり着くためにはその直前の状態にたどり着いた後に遷移に必 # 要が文字がくればいい、ということが書いてあるだけです。あと、開始状態 # には即座に到達できるので、εを加えます。 で、(3) を r について解きます。 r = (p2 + q1)0* # 一般に r = s + rt は r = st* というように解けます。 ## なるほど！これがポイントですね。Arden の補題というらしいですね。 これを (1) と (2) に代入して r を消去すると次のようになります。 (4) p = p0 + q2 + (p2 + q1)0*1 + ε = p(0 + 20*1) + q(2 + 10*1) + ε (5) q = p1 + q0 + (p2 + q1)0*2 = p(1 + 20*2) + q(0 + 10*2) で、(5) を q について解きます。 q = p(1 + 20*2)(0 + 10*2)* これを (4) に代入して q を消去します。 p = p(0 + 20*1) + p(1 + 20*2)(0 + 10*2)*(2 + 10*1) + ε = p(0 + 20*1 + (1 + 20*2)(0 + 10*2)*(2 + 10*1)) + ε = (0 + 20*1 + (1 + 20*2)(0 + 10*2)*(2 + 10*1))* というわけで答えは (0+20*1+(1+20*2)(0+10*2)*(2+10*1))* です。 Unix 流に書くと + を | に書き換えて (0|20*1|(1|20*2)(0|10*2)*(2|10*1))* となっておしまい、と。# 3 の倍数にマッチする正規表現(109bytes)を求める $states = 3; @matrix = ([qw(E [0369] [258] [147])], # A = A0 + B2 + C1 + e [qw(X [147] [0369] [258])], # B = A1 + B0 + C2 [qw(X [258] [147] [0369])], # C = A2 + B1 + C0 ); $result = resolv(); print $result;
, resolv(), substitute()は 「a が偶数個で b が奇数個の文字列にマッチする正規表現」参照． rsrt()
4 の倍数にマッチする正規表現
トップへ# 全能版 ^(\d+)(?(?{$1 % 4})(?!))$ # 純粋版 30bytes ((^|[02468])[048]|[13579][26])$
5 の倍数にマッチする正規表現
トップへ# 全能版 ^(\d+)(?(?{$1 % 5})(?!))$ # 純粋版 5bytes [05]$
6 の倍数にマッチする正規表現
トップへ# 全能版 ^(\d+)(?(?{$1 % 6})(?!))$ # 準純粋版 125bytes (?=^\d*[02468]$)^(([0369]|[258][0369]*[147])|([147]|[258][0369]*[2 58])([0369]|[147][0369]*[258])*([258]|[147][0369]*[147]))*$
7 の倍数にマッチする正規表現
トップへ# 全能版 ^(\d+)(?(?{$1 % 7})(?!))$# 7 の倍数にマッチする正規表現(481,878,604bytes)を求める # 6桁以内の 7 の倍数にマッチする正規表現(117,648bytes) $states = 7; @matrix = ([qw(E a g f e d c b)], # A = Aa + Bg + Cf + De + Ed + Fc + Gb # + e [qw(X b a g f e d c)], # B = Ab + Ba + Cg + Df + Ee + Fd + Gc [qw(X c b a g f e d)], # C = Ac + Bb + Ca + Dg + Ef + Fe + Gd [qw(X d c b a g f e)], # D = Ad + Bc + Cb + Da + Eg + Ff + Ge [qw(X e d c b a g f)], # E = Ae + Bd + Cc + Db + Ea + Fg + Gf [qw(X f e d c b a g)], # F = Af + Be + Cd + Dc + Eb + Fa + Gg [qw(X g f e d c b a)], # G = Ag + Bf + Ce + Dd + Ec + Fb + Ga ); # A B C D E F G @matrix2 = ([qw([07] [18] [29] 3 4 5 6) ], # 1桁目 [qw([07] 5 3 [18] 6 4 [29])], # 2桁目 [qw([07] 4 [18] 5 [29] 6 3) ], # 3桁目 [qw([07] 6 5 4 3 [29] [18])], # 4桁目 [qw([07] [29] 4 6 [18] 3 5) ], # 5桁目 [qw([07] 3 6 [29] 5 [18] 4) ], # 6桁目 ); $result = resolv(); @{$matrix3[5]}[0 .. 6] = @{$matrix2[5]}[0 .. 6]; # 6桁目の計算 for (my $p = 4; $p >= 0; $p--) { # 5桁目から1桁目までを順番に計算 for (my $group = 0; $group < 7; $group++) { $matrix3[$p][$group] = "(^$matrix2[$p][$group]"; for (my $i = 0; $i < 7; $i++) { for (my $j = 0; $j < 7; $j++) { $matrix3[$p][$group] .= '|' . $matrix3[$p + 1][$i] . $matrix2[$p][$j] if $group == ($i + $j) % 7; } } $matrix3[$p][$group] .= ')'; } } if (0) { # 1 なら 6桁以内の 7 の倍数にマッチする正規表現(117,648bytes) $result = '^' . $matrix3[0][0] . '$'; print $result; } else { # 0 なら # 7 の倍数にマッチする正規表現(481,878,604bytes) print ((defined $2) ? $matrix3[0][ord($1) - ord('a')] : $1) while ($result =~ /(([a-g])|.)/g); }
, resolv(), substitute()は 「a が偶数個で b が奇数個の文字列にマッチする正規表現」参照． rsrt()
8 の倍数にマッチする正規表現
トップへ# 全能版 ^(\d+)(?(?{$1 % 8})(?!))$ # 純粋版 86bytes ((^|[02468])((^|[048])[08]|[37]2|[26]4[159]6)|[13579]([26][08]|[1 59]2|[048]4|[37]6))$
9 の倍数にマッチする正規表現
トップへ# 全能版 ^(\d+)(?(?{$1 % 9})(?!))$# 9 の倍数にマッチする正規表現(218,457bytes)を求める $states = 9; @matrix = ([qw(E [09] 8 7 6 5 4 3 2 1)], [qw(X 1 [09] 8 7 6 5 4 3 2)], [qw(X 2 1 [09] 8 7 6 5 4 3)], [qw(X 3 2 1 [09] 8 7 6 5 4)], [qw(X 4 3 2 1 [09] 8 7 6 5)], [qw(X 5 4 3 2 1 [09] 8 7 6)], [qw(X 6 5 4 3 2 1 [09] 8 7)], [qw(X 7 6 5 4 3 2 1 [09] 8)], [qw(X 8 7 6 5 4 3 2 1 [09])], ); $result = resolv(); print $result; # $result =~ s/\(/(?:/g; # ( を (?: に変換したら実際に使用できる
, resolv(), substitute()は 「a が偶数個で b が奇数個の文字列にマッチする正規表現」参照． rsrt()
- 9 の倍数にマッチする正規表現(218,457bytes)を求めるスクリプトの 出力結果
ISBN にマッチする正規表現
トップへ# 全能版 /^(?=\d+X?$|\d+-\d+-\d+-[\dX]$) (\d)-?(\d)-?(\d)-?(\d)-?(\d)-?(\d)-?(\d)-?(\d)-?(\d)-?([\dX]) (?(?{($1 * 10 + $2 * 9 + $3 * 8 + $4 * 7 + $5 * 6 + $6 * 5 + $7 * 4 + $8 * 3 + $9 * 2 + ($10 eq 'X' ? 10 : $10)) % 11})(?!))$/x# 純粋版 # ISBN にマッチする正規表現のサイズを求める $states = 11; # A B C D E F G H I J K @matrix2 = ([qw(0 1 2 3 4 5 6 7 8 9 X) ], # 1桁目 [qw(0 6 1 7 2 8 3 9 4 * 5) ], # 2桁目 [qw(0 4 8 1 5 9 2 6 * 3 7) ], # 3桁目 [qw(0 3 6 9 1 4 7 * 2 5 8) ], # 4桁目 [qw(0 9 7 5 3 1 * 8 6 4 2) ], # 5桁目 [qw(0 2 4 6 8 * 1 3 5 7 9) ], # 6桁目 [qw(0 8 5 2 * 7 4 1 9 6 3) ], # 7桁目 [qw(0 7 3 * 6 2 9 5 1 8 4) ], # 8桁目 [qw(0 5 * 4 9 3 8 2 7 1 6) ], # 9桁目 [qw(0 * 9 8 7 6 5 4 3 2 1) ], # 10桁目 ); for (my $i = 0; $i < $states; $i++) { # 10桁目の計算 $matrix3[9][$i] = length($matrix2[9][$i]) if $matrix2[9][$i] ne '*'; } $result = length('^('); $prev_hyphen = 0; for (my $hyphen = 0; $hyphen < 2; $hyphen++) { # ハイフンなし:0, あり:1 for (my $x = 8; $x >= 2; $x--) { # グループ記号 '-' 出版社記号 for (my $y = $x - 1; $y >= 1; $y--) { # 出版社記号 '-' 書名記号 $result += length('|') if $prev_hyphen == 1; for (my $p = 8; $p >= 0; $p--) { # 9桁目から1桁目までを順番に計算 for (my $group = 0; $group < $states; $group++) { $matrix3[$p][$group] = length(''); $matrix3[$p][$group] += length('('); my $prev = 0; for (my $i = 0; $i < $states; $i++) { for (my $j = 0; $j < $states; $j++) { if ($group == ($i + $j) % $states and $matrix2[$p][$j] ne '*' and $matrix3[$p + 1][$i] != 0) { $matrix3[$p][$group] += length('|') if $prev == 1; $matrix3[$p][$group] += $matrix3[$p + 1][$i]; $matrix3[$p][$group] += length('-') if $hyphen != 0 and ($p == $x or $p == $y or $p == 0); $matrix3[$p][$group] += length($matrix2[$p][$j]); $prev = 1; } } } $matrix3[$p][$group] += length(')'); } } $result += $matrix3[0][0]; $prev_hyphen = 1; last if $hyphen == 0; } last if $hyphen == 0; } } $result += length(')$'); print $result;ISBN については こちら を参照． 上記スクリプトは正しい ISBN(International Standard Book Number) にマッチする正規表現のサイズを求める． ISBN はハイフンがあってもなくてもよいが， ハイフンの位置がおかしいものは当然正しい ISBN ではない． ハイフンの位置に関しては 28通り(8C2)である．なぜなら，検査数字の前には必ず ハイフンが入り，残り 2個のハイフンの位置は 8ヶ所のうちの 2ヶ所であるため． 上記スクリプトで求めた正しい ISBN にマッチする正規表現のサイズは 105,488,889,066bytes となった． ハイフンなしの場合を含めないときは上記スクリプトで $hyphen の for文を $hyphen = 1 からスタートすればよい．そのとき 102,122,222,401bytes となった． 逆にハイフンなしの場合だけのときは $hyphen < 1 とし， さらに前後の括弧が 1組不要になるので，3,366,666,666bytes となった． 本来は上記スクリプトで length としている場所を文字列連結に変更すれば， 正しい ISBN にマッチする正規表現を求めることができるはずだが， サイズが巨大すぎて不可能だった．しかし下記スクリプトのように， 再帰呼び出しを使うことによって出力するだけならば可能である．
# 純粋版 # ISBN にマッチする正規表現(105,488,889,066bytes)を求める $states = 11; # A B C D E F G H I J K @matrix2 = ([qw(0 1 2 3 4 5 6 7 8 9 X) ], # 1桁目 [qw(0 6 1 7 2 8 3 9 4 * 5) ], # 2桁目 [qw(0 4 8 1 5 9 2 6 * 3 7) ], # 3桁目 [qw(0 3 6 9 1 4 7 * 2 5 8) ], # 4桁目 [qw(0 9 7 5 3 1 * 8 6 4 2) ], # 5桁目 [qw(0 2 4 6 8 * 1 3 5 7 9) ], # 6桁目 [qw(0 8 5 2 * 7 4 1 9 6 3) ], # 7桁目 [qw(0 7 3 * 6 2 9 5 1 8 4) ], # 8桁目 [qw(0 5 * 4 9 3 8 2 7 1 6) ], # 9桁目 [qw(0 * 9 8 7 6 5 4 3 2 1) ], # 10桁目 ); print '^('; $prev_hyphen = 0; for (local $hyphen = 0; $hyphen < 2; $hyphen++) { # ハイフンなし:0, 有り:1 for (local $x = 8; $x >= 2; $x--) { # グループ記号 '-' 出版社記号 for (local $y = $x - 1; $y >= 1; $y--) { # 出版社記号 '-' 書名記号 print '|' if $prev_hyphen == 1; print matrix3(0, 0); $prev_hyphen = 1; last if $hyphen == 0; } last if $hyphen == 0; } } print ')$'; sub matrix3 { my($p, $group) = @_; if ($p == 9) { print $matrix2[9][$group]; return; } print '('; my $prev = 0; for (my $i = 0; $i < $states; $i++) { for (my $j = 0; $j < $states; $j++) { if ($group == ($i + $j) % $states and $matrix2[$p][$j] ne '*' and $matrix2[$p + 1][$i] ne '*') { print '|' if $prev == 1; print matrix3($p + 1, $i); print '-' if $hyphen != 0 and ($p == $x or $p == $y or $p == 0); print $matrix2[$p][$j]; $prev = 1; } } } print ')'; }
文字の正規表現
トップへ
HTMLタグ の正規表現
トップへPerlメモ の 「
HTMLタグ の正規表現」 を参照してください．
URI(URL) の正規表現
トップへPerlメモ の 「URI(URL) の正規表現」 を参照してください．
http URL の正規表現
トップへPerlメモ の 「
http URL の正規表現」 を参照してください．
ftp URL の正規表現
トップへPerlメモ の 「
ftp URL の正規表現」 を参照してください．
メールアドレスの正規表現
トップへPerlメモ の 「メールアドレスの正規表現」 を参照してください．
