Perl正規表現雑技

更新日 2014/2/2
カウンター

戻る
Perlメモ
メールアドレスの正規表現

更新履歴

2014/02/02 「回文にマッチする正規表現」スクリプト修正
2014/01/30 「タグの閉じ忘れをチェックする」スクリプト修正
2014/01/29 「タグの閉じ忘れをチェックする」スクリプト修正
2014/01/21 「ある文字列を含まないものにマッチする正規表現」表現修正
2014/01/20 「ある文字列を含まないものにマッチする正規表現」追記

目次

トップへ

はじめに

  • このページは Perl5.6 を対象としています.
  • perl スクリプトは EUC-JP で書かれることを想定しています.
  • このページは 正規表現メーリングリスト を参考に,私が独自にメモとしてまとめたものです.
  • このページの正規表現やスクリプトについての詳しい説明, わかりやすい説明はおそらくできません.
  • このページに書かれているスクリプトは, 個人の責任において実行してください.
  • このページに書かれているスクリプトの 利用・改造は自由 です. その際はどこかにこのページの URI( http://www.din.or.jp/~ohzaki/regex.htm )を参考として記述していただければ幸いです(任意).
  • このページは Internet Explorer 5.5 以降で表示の確認を行なっています.IE 以外のブラウザをご使用の場合は, 正常に表示されないかもしれません.
  • ご意見・ご感想・ご要望などは メール にお願いします.こう書いた方がいい, 動かん,わからん,バグってる,これ書け,などなどお待ちしています.
  • このページへの リンクは自由 に張ってくださって結構です.URI は http://www.din.or.jp/~ohzaki/regex.htm です.
  • 引用または転載する場合は,出典としてこのページの URI( http://www.din.or.jp/~ohzaki/regex.htm )を明記してください. URI を明記する場合に限り許可は必要ありませんが, 事後でかまわないのでお知らせくださればうれしいです. URI を明記しない場合には事前の許可なしに引用または転載することを 禁止 します.
トップへ

全能な正規表現

(??{ code })
(?{ code })
トップへ

マッチしない正規表現

(?!)

すべてにマッチする正規表現,空文字列,の否定先読みという意味. [^\s\S][^\w\W] などでもよい.しかし, [^\x00-\xFF] では utf8 pragma を有効にした環境下において, \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文字以上にマッチさせたい場合(空文字列にマッチさせたくない場合)は下記の通り.

(?:(?:(?!foo).)+(?:fo|f)?|fo|f)
マッチする部分にfoobarを含まない正規表現は下記の通り.
(?:(?!foobar).)*(?:fooba|foob|foo|fo|f)?
1文字以上にマッチさせたい場合(空文字列にマッチさせたくない場合)は下記の通り.
(?:(?:(?!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[^<]*? である.

一旦,タグの外側の部分を抜き出してから,その部分に対して置換する方法もある. 以下がその方法だが,置換を修飾子 e を使って行なっているのでスマートとは言い難い. 置換ではなく,タグの外側の部分だけ抜き出す目的で使う分には,マッチした部分に 余計なものが入らないという点において意味がある.

s/(?:^|(?<=>))([^<]*)/(my $tmp = $1) =~ s!foo!bar!g; $tmp/egs;

タグの正規表現を <.*?> とした場合, タグの外側の正規表現は (?:^|>)(.*?)(?:$|<) のときの $1 となる.>< は後読みと先読みにして外に出すことができるので,結局 タグの外側の正規表現は (?:^|(?<=>))(.*?)(?:$|(?=<)) となる.

ところが,文頭からタグが始まる場合に修飾子 g をつけて繰り返し置換させようとするとまずいことになる. 文頭からタグが始まる場合 ^()(?=<) が最初に マッチする.つまり,文頭の < の直前の隙間の空文字列が マッチし,パターンマッチの開始場所は最初の地点から動かない.これでは次に 修飾子 g によって再度置換しにいったとしても 同じ位置で永久に繰り返すことになってしまう.そこで,Perl では空文字列に マッチするような場合には,初回は空文字列がマッチするがそれ以降は マッチせずに必ず 1文字分は進むようにマッチしようとする. これにより永久に繰り返すことを防いでいるわけだが,その結果,今度は .*? が文頭の < を含むようになり, 一旦文頭の < を含んでしまったら,文末か次の < が来るまで伸び続け,結局文頭から始まるタグを含んで マッチしてしまうことになる.

そこで,.*?< を含まない ようにすることを考えると,[^<]*? となる. この時点で最初の正規表現はもう少し簡単になることがわかる.つまり, ([^<]*?)(?:$|(?=<)) というのは ([^<]*) とすることができる.

タグの正規表現が <.*?> とできない場合は, 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  \/
    0  ---->  1  ---->  2
    |          |
    |   [^xy]  |
    <----------+

です。

0から始まって2で終るのが「xy を含む」ということですから、求めるも
のはその否定すなわち、0か1が終了状態の DFA です。

で、素朴なアルゴリズムで解くと「xy を含まない文字列」は

  ([^x]|x+[^xy])*x*

が答です。他には | を展開して

  [^x]*(x+[^xy][^x]*)*x*

とか、

  *y(x*[^xy]y*)*x*

とかがあります。

|fmcat =(retofm <<<'(x+y+a)*xy(x+y+a)*'|fmcment) =(retofm <<<'xy')|fmdeterm|fmmin|fmtore|perl -pe 'y/+/|/; s/a/[^xy]/g'  
|として
|([^xy]|y)*x(x|[^xy]([^xy]|y)*x)*y

grail

連立方程式では

  p = p[^x] + q[^xy] + ε
  q = px    + qx

を解いて、答は p + q。
トップへ

xyz を含まないものにマッチする正規表現

[regexp 60]より

|fmcat =(retofm <<<'(x+y+z+a)*xyz(x+y+z+a)*'|fmcment) =(retofm <<<'xyz')|fmdeterm|fmmin|fmtore|perl -pe 'y/+/|/; s/a/[^xyz]/g'
|として、
|([^xyz]|y|z)*x(z([^xyz]|y|z)*x|[^xyz]([^xyz]|y|z)*x|x|yx|y[^xyz]([^xyz]|y|z)*x|yy([^xyz]|y|z)*x)*yz

遷移図は

                    x
              <-----------+
   [^x]       |  x        |
  <----+      <----+      |
  |    |      |    |      |
   \/   x    \/  y    |     z
    0  ---->  1  ---->  2  ----> 3(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(), rsrt() は 「a が偶数個で b が奇数個の文字列にマッチする正規表現」参照.

トップへ

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(), rsrt() は 「a が偶数個で b が奇数個の文字列にマッチする正規表現」参照.

  • 7 の倍数にマッチする正規表現(481,878,604bytes)を求めるスクリプトの 出力結果
  • 6桁以内の 7 の倍数にマッチする正規表現(117,648bytes)を求めるスクリプトの 出力結果
トップへ

おすすめサイト

金持ち父さんのキャッシュフローゲーム
http://cashflow-master.com/
キャッシュフローゲーム体験会&金持ち父さんセミナー情報をお届け。

ブライトリング販売店
http://www.eye-eye-isuzu.co.jp/
パネライ(PANERAI)ブライトリング(BREITLING)フランクミュラー(FRANCKMULLER)など、ブランド公認正規販売店。

デイリーズをお求めなら
http://www.web-lens.com
デイリーズ、メダリストなどメジャーレンズからカラコンまで豊富に取り揃えています。

大阪の貸事務所はこちら
http://www.office-planner.jp/
便利でローコストな賃貸事務所の情報提供をいたします。

CDプレスやDVDプレスの制作
http://www.replication.jp/
CD・DVDプレス制作のご注文なら迅速かつ格安のアイテックへ。

ネクサーのスマートフォンサイト制作
http://sp-nexer-web.com
印象に残る、利便性がいいスマートフォンサイトを制作。高クオリティ、低価格のサイト制作サービスとなっております。

ポルシェ買取
http://www.crayon911.co.jp
滋賀県大津市のポルシェ買取専門店です。

幼児教室のアイ・シー・イーhttp://www.ice-world.co.jp/
アイ・シー・イーの幼児教室のメソッドが「伸びる子」を育てます。

梅干の河本食品
http://www.kawamotokk.co.jp
テレビ、雑誌で多数掲載の梅干専門店。健康を気遣った贈り物に最適。

沖縄青の洞窟ダイビングショップ
http://www.marine-trip.net
青の洞窟など、沖縄ダイビングなら恩納村の初心者向けダイビングショップ!


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(), rsrt() は 「a が偶数個で b が奇数個の文字列にマッチする正規表現」参照.

  • 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 ')';
}
  • ISBN にマッチする正規表現(105,488,889,066bytes)を求めるスクリプトの 出力結果
  • ISBN(ハイフンありのみ) にマッチする正規表現(102,122,222,401bytes)を求めるスクリプトの 出力結果
  • ISBN(ハイフンなしのみ) にマッチする正規表現(3,366,666,666bytes)を求めるスクリプトの 出力結果
トップへ

文字の正規表現

Perlメモ の 「文字の正規表現」 を参照してください.

トップへ

HTMLタグの正規表現

Perlメモ の 「HTMLタグの正規表現」 を参照してください.

トップへ

URI(URL) の正規表現

Perlメモ の 「URI(URL) の正規表現」 を参照してください.

トップへ

http URL の正規表現

Perlメモ の 「http URL の正規表現」 を参照してください.

トップへ

ftp URL の正規表現

Perlメモ の 「ftp URL の正規表現」 を参照してください.

トップへ

メールアドレスの正規表現

Perlメモ の 「メールアドレスの正規表現」 を参照してください.

トップへ

戻る
うずら メール

Copyright (C) 2001-2014 OHZAKI Hiroki. All rights reserved.