テスト駆動で 0 から 255 の数字にマッチする正規表現へ変形してみる

ぶくま経由で、RFC 3986 URI の日本語訳にたどり着き、読んでいました。スムーズな日本語ですんなりと読めて、良い訳だと思いました。私は誤訳を見つけられませんでした。
それはともかく、読んでいる最中に、RFC3986 だけではないのですが、IPv4 アドレスの数字にマッチする構文が、正規表現向けでないのに改めて気になりました。RFC の記述をそのまま正規表現にすると、バックトラックをおこす書き方になっています。
バックトラックがおきないようにするには、先頭から1文字ずつ見ていくだけで残りの選択肢のどれに進めばいいか決定できるようにすればよろしい。ということで、これをテスト駆動で正規表現に向いた記述に変更してみました。

http://www.studyinghttp.net/cgi-bin/rfc.cgi?3986#Sec3.2.2

 IPv4address = dec-octet "." dec-octet "." dec-octet "." dec-octet

 dec-octet   = DIGIT                 ; 0-9
             / %x31-39 DIGIT         ; 10-99
             / "1" 2DIGIT            ; 100-199
             / "2" %x30-34 DIGIT     ; 200-249
             / "25" %x30-35          ; 250-255

この手の作業はケアレスミスをおこしやすいので、最初にやることはテストを作ることです。この程度の正規表現のテストはどの言語でやっても同じですが、ここは Perl を使うことにします。
最初に、Test::More を使い、パラメータで正規表現を受け取るサブルーチンを定義することから始めます。0 から 10000 までの数字列を正規表現でマッチしてみて、0 から 255 以外にマッチした場合と、0 から 255 なのにマッチしなかったら、戻り値が偽になるように作ります。
なお、この手の正規表現のテストでは、必ず \A と \z で挟んで、テストしたい文字列全体にマッチするかどうかチェックをおこないましょう。

#!/usr/env perl
use strict;
use warnings;
use Test::More 'no_plan';

sub test_dec_octet {
    my $dec_octet = shift;
    my @invalid;
    for (0 .. 10000) {
        if (/\A$dec_octet\z/msx) {
            push @invalid, $_ unless 0 <= $_ && $_ <= 255;
        } else {
            push @invalid, $_ if 0 <= $_ && $_ <= 255;
        }
    }
    ! scalar @invalid;
}

ok test_dec_octet(qr{
  (?:[0-9]
  |  [1-9][0-9]
  |  1[0-9][0-9]
  |  2[0-4][0-9]
  |  25[0-5]
  )
}x);

\d にせず 0-9 にしているのは、変形していく上では、その方が見やすいからです。それでは、さっそく、RFC の構文を正規表現にして、動かしてみましょう。

$ perl dec_octet_re.t.pl
ok 1
1..1

ちゃんと 0 から 255 までにマッチしていることがわかります。
では、書換開始。段階的に変形させつつ、ケアレスミスをしていないかチェックするために、テストをこまめに実行していきます。
1文字目(最上位桁)の数字から扱いの区分分けをしていきます。上の場合は、1文字目がゼロのとき、1 のとき、2 のとき、3 から 9 のときの 4 通りに分けなければいけないことがわかります。また、1 文字目が 2 のとき、2文字目が 0 から 4 のときと、5 のとき、 6 から 9 のときの 3 通りに選択肢が分かれていますので、これもその通りにします。各行をそのように分けたら、次のようになりました。

ok test_dec_octet(qr{
  (?:0 | 1 | 2 | [3-9]
  |  1[0-9] | 2[0-4] | 25 | 2[6-9] | [3-9][0-9]
  |  1[0-9][0-9]
  |  2[0-4][0-9]
  |  25[0-5]
  )
}x);

上のコードに続けて、各行を分けた正規表現のテストを追加して、またテストを実行します。

$ perl dec_octet_re.t.pl
ok 1
ok 2
1..2

書換でミスをしていなければ ok になるはずです。
続いて、分解した選択肢を先頭の文字が同じになるように並べ替えた正規表現のテストを追加してテストします(実行は略)。

ok test_dec_octet(qr{
  (?:0
  |  1
  |  1[0-9]
  |  1[0-9][0-9]
  |  2
  |  2[0-4]
  |  2[0-4][0-9]
  |  25
  |  25[0-5]
  |  2[6-9]
  |  [3-9]
  |  [3-9][0-9]
  )
}x);

今度は、先頭から同じ文字でまとめていきます。そして、テストを追加して、実行します。

ok test_dec_octet(qr{
  (?:0
  |  1[0-9]{0,2}
  |  2
     (?:
     |  [0-4][0-9]?
     |  5[0-5]?
     |  [6-9]
     )?
  |  [3-9][0-9]?
  )
}x);

ここまでくれば、0-9 を \d にして、一行にまとめてしまいます。最後のテストを追加して、実行します。

ok test_dec_octet(
  qr{(?:0|1\d{0,2}|2(?:[0-4]\d?|5[0-5]?|[6-9])?|[3-9]\d?)}
);

望みの正規表現が手に入りました。

my $dec_octet = qr{(?:0|1\d{0,2}|2(?:[0-4]\d?|5[0-5]?|[6-9])?|[3-9]\d?)};
my $ipv4addr  = qr{$dec_octet(?:\.$dec_octet){3}};

手軽にテストを作って実行できる Perl のテストには、こういう使い道もありますという一例でした。