読書ノート
▲ [ 国内 | 国外 | 記事 | 漫画 ][ Home ]
▼ [ 読感｜抄録(一般)｜抄録(Perl) ]

詳説　正規表現

Jeffrey E. F. Friedl/歌代和正(監訳)/春遍雀來, 鈴木武生(訳)
オライリー・ジャパン/1999/\4,300　900900-45-1

読感

『正規表現』カバーより(picture)通称フクロウ本。正規表現(regular expression : regex)を正面から扱った貴重な本である。最近は類書も出ているようだが、現在でも正規表現を本格的に掘り下げて扱う本は実質的に本書しかないといっていいだろう。正規表現は私も始めは意味不明な記号の羅列に見えて敬遠していたもののひとつだが、今では「知っててよかった」と思うもののひとつである。

むろん、正規表現だけでは単なるマッチングなので、それと併用できるツール(Perl etc..)への習熟が一方では必要になるものの、そこから得られるパワーは非常に強力である。正直なところ、個人的には本書で紹介されているような一部の高度な最適化の求められるケースはあまり多くないように思ったが(内容が完全に理解できていないということだ :-))、Perl における詳細な正規表現ルール(本書の約 1/3 がそれに当てられている)といった具体的な詳細の数々は、確かに関連書籍で薦められるだけの頼り甲斐がある。私自身はツールとして Perl しかほとんど使わないので他のツールでの話などは流し読み程度だが、逆にいうと Perl を本格的に使いこなしたい場合における避けて通れない一冊なのは確かだろう。

抄録(一般)

5/78/82

正規表現は特殊な意味を持ったメタ文字(meta character)とそれ以外の普通のテキスト文字であるリテラル(literal)から構成される。メタ文字の扱いはツールによって幅があるため、あるエスケープをそのツールがサポートしなければ、それは単なる文字列の正規表現として渡されることになる。

10/58

「^cat$」は cat だけから成る行、「^$」は空行、「^」のみは行頭のある行、即ち空行を含む全ての行にマッチする。最後はケースは「$line =~ s/^/> /;」で行頭に引用記号を付けるようなときに利用できる。

11/123/140

否定文字クラスは「指定されていない文字とマッチせよ」であって、「指定されているものとマッチしてはならない」という意味ではない。これに関連してマッチは常にマッチ不成立よりも優先される = 必須でないものは必ずマッチに成功する点がある。これを見逃すと不要なものへのマッチが起こることになる。

13/24/118/144/146/195

対象テキストを十分に理解した上で正規表現を使うということ。正規表現の場合、必要なマッチができれば戦いの半分は既に終わっている。残り半分は不要なときにマッチさせないということであり、つまりマッチしないときの結果を考えるということになる。(言い換えれば必要なものだけを書き、それが正規表現エンジンにどう解釈されるのか理解するということ。)

例えば「a 1234 num」への「[0-9*]」という正規表現は、「a」の時点でマッチしてしまうので、数字のところまで到達しない。

16/55/87

文字クラス「[...]」はあくまでも一文字に対して有効で、選択を使えば文字数の長さに制限はなくなる。但し、選択には文字クラスのような否定がない。そして、文字クラス内でのメタ文字はエスケープが不要なので、「[^()]*」で ( ) 以外に対する指定となる。(ちなみに、この否定は改行にもマッチする。)

21/30/43/307

同じ正規表現内で既に ( ) でマッチしたものへの前方参照を行うには \1 を使う。(丸括弧にはグループ化、格納、選択領域の制限という機能がある。)これが Perl の場合、格納の丸括弧がネストする場合は、左から順に $1、$2 ... となる。なお、Perl5 ではグループ化専用の括弧であることを示す (?:...) が用意されている。

$str = "the the";
print "matched\n" if($str =~ /(the) \1/);

66-72/199

正規表現は 1940 年代に Stephan Kleene という数学者が、神経生理学者の Warren McCulloh と Walter Pitts による神経系統のニューロンレベルでのモデルを図式化するために、正則表現(数学の世界では正規表現のことをこう呼ぶ)という代数を用いて記述したことに端を発する。これをコンピュータに初めて応用したのが Ken Thompson による「Regular Expression Search Algorithm」(1968)で、これが UNIX のエディタ ed の基礎となる qed の研究へとつながっていった。そして、ed には正規表現にマッチした編集対象行を表示する「g/Regular Expression/p」(Global Regular Expression Print)というコマンドがあり、それ自体がユーティリティとなることによって grep が生まれた。

初期の grep などは機能的にも貧弱なものだったが、その後の egrep、awk、lex、sed などといったツールは独自の進化を遂げていく。しかし、その間にツール間での互換性は失われ、その混乱は 1986 に Henry Spencer が C 言語用の正規表現パッケージを開発するまで続いた。また、POSIX による BRE (Basic Regular Expressions) : 基本正規表現と ERE (Extended Regular Expressions) : 拡張正規表現も生まれたが、それでもなおツール間、更にはバージョン間の大きな違いが存在する。

なお、POSIX の場合はロケールも定めているので、正規表現もその影響を受けることになる。これは POSIX 非対応のツールが POSIX 互換の C/C++ ライブラリを使うときなどに意外な影響を与えることがある。cf.88

97-98/108-111/130-131/153

正規表現エンジンは大別すると 2 種類あり、NFA エンジン(正規表現制御型 : Tcl、Perl、Python、Emacs、ed、sed、vi、grep など)と、DFA エンジン(テキスト制御型 : egrep、awk、lex、flex など)とがある。NFA は更に従来型 NFA とPOSIX NFA とに分かれる。(POSIX NFA として ed、egrep、lex、sed など。)違いとして NFA が正規表現の要素からテキストへのチェックを行う正規表現主体であるのに対し、DFA ではテキストに対して正規表現のチェックを行うテキスト主体という点が挙げられる。そのため、単純にテキストへの部分マッチが一度しか行われない DFA の方が速度的には有利となり、逆にいうと NFA は正規表現の記述内容によって処理に違いが生じる = バックトラックを避けるためのカスタマイズの余地がある――ということになる。その代わり、DFA では事前に正規表現を調査(コンパイル)し内部地図を作るのに時間とメモリを使う。また、DFA では一部の処理を先延ばしすることで処理の効率化を図る遅延評価(lazy evaluation)が使われている。(cf.176-177 : 正規表現エンジンの種類のテストについて。)

99/100/103/107/118/124-125/127/143

正規表現エンジンにおける 2 大原則は 1) (左から見て)先に開始されたマッチが優先される 2) 繰り返し制御文字は(それ以降のマッチに失敗する場合以外は)常に欲張り――となる。後者は例えば「(.*).*」というときに後ろ側の .* には何もマッチしないことからも分かる。つまり、* はとにかくマッチが失敗するまで繰り返して、その後に譲歩しなければならないものがあれば譲歩する(先に最もマッチさせてから譲歩する)性質を持つ。これを特に最長最左(Longest-Leftmost)マッチと呼ぶ。それゆえ正規表現を考えるときには、「b の前の a」ではなく「b の続く a」という発想をするのがよい。

但し、NFA 型の場合、選択は欲張りとはならない。これを利用すると短い選択肢を前に持ってくることで、一種の非欲張り型を実現することができる。例えば、日付へのマッチを行う「Jan (0?[1-9]|[12][0-9]|3[01])」など。(この場合には後者の選択にマッチしないケースがないように注意する必要がある。)

112-114

NFA エンジンでの本質は部分やパターンで判断が固定できない場合にその地点を記憶しておくことで、マッチに失敗した場合にはそこまで戻り、別のパターンを試すという繰り返しの部分にある。この後戻りのことをバックトラックといい、記憶された場所のことをステート(状態)という。つまり、バックトラックにおいては 1) テストの必要なパターンがあれば全て必ずテストが行われ 2) バックトラックは常に最新の記憶先へ戻って行われる(つまり LIFO)、という点に特徴がある。

128-129

一方、POSIX NFA では最長最左マッチが要求されるので、仮にマッチが成功したとしても最長可能性のために残りをテストする必要が生じる。この特徴のため、POSIX NFA ではより効率上の影響を受けることになる。

132

簡単な正規表現パッケージならば自作も十分に可能であり、そこそこの実用にも耐え得るものを作ることができる。

134/135

よい正規表現を書くには 1) 必要なものにマッチさせる 2) 管理や理解のしやすいようにする 3) NFA では効率に気を配る などがポイントとなる。例えば、正規表現は短い方がよいが、処理全体において何度も行われない箇所なのであれば、分かりやすさを優先させるなど。そのためにも厳密さに配慮することが重要となる。

148

正規表現だけが常に唯一の方法となるわけではない。言語が標準で有用な関数などを提供しているのであれば、そちらを使った方が便利な場合もある。

156-157/159/178-182

バックトラックの回数を減らすために「[^"\\]+」で非クォート・非エスケープへの効率的なマッチを使うことができるが、これは「([^"\\]+)*」のような状況では指数的なパターンの増加を招く。これは POSIX NFA だけでなく 従来型 NFA でも「パターンにマッチしなければ全ての組み合わせを試そうとする」点では同じ。つまり(例外もあるが)、「(...*)*」のような表現は危険信号といえる。

これを避けるための筆者による「ループ展開」という技術について。これを導くには 1) マッチテストの中で実際に成功した流れを記録する 2) マッチさせる構文を高い次元から眺める、の二通りの方法を使う。(つまり、そうやって共通となりそうな部分を考察していく。)この場合だとそれは「"[^"\\]*(\\.[^"\\]*)*"」で形式的には「開始 通常要素* (特殊要素 通常要素*)* 終了」となる。上のような永久マッチを避けるためのポイントとなっているのは以下の通り。1) 特殊要素と通常要素が同一位置でマッチしない 2) 特殊要素が無とマッチしない 3) ひとつの特殊要素でマッチするものが複数の特殊要素ではマッチしない。

# ここは難しくていまいちよく分からない...

164/165/168/170/172-173/196

マッチでの効率改善を図る具体的な方法として以下のものがある。

cf.192-193 : より高度な最適化について。

171

プログラミングにおける汎用的ということは遅いという場合がほとんどなので、通常は限られた用途のために特化したものの方が高速になる。

185

正規表現が複雑な場合には共通して登場するパターン部分を X などで置き換えてみる。(数式と一緒で単純化してみる。)

抄録(Perl)

221/222/223

Perl での「=~」もふたつのオペランドを取って結果を返すという意味で演算子となる。Perl の場合にはこのような豊富な正規表現のあることが、同時に少しの変更で大きな違いをもたらす弱点にもつながっている。p.221 に Perl での正規表現表記の一覧。なお、/A、/Z で文字列の先頭、末尾を指定できる。また、Perl では「_」も \w に含まれる。

233-235

Perl で local 宣言を使うとグローバル変数の値がそのスコープの間において内部コピーとして保存されスコープを抜けた時点でそれが復元される。つまり、これは変更に対する時間を示している。例えば、グローバル変数であるデバッグ用フラグを一時的にオフにする場合には以下のようにする。

{  # このスコープの間に...
    local $^W = 0;  # デバッグ用フラグのオフ
    $func();  # 警告に引っかかる関数の呼び出し
}  # $^W の復元

241

Perl での \1 は完全に正規表現用のメタ文字なのでマッチの途中で内容の変わることがありえる。そのためマッチの結果を取り出すには $1 を使う。一方、置換オペランドに対して $1 を使うのは有効だが、正規表現オペランドとして $1 を使っても、それは正規表現コンパイル時のそれ以前のマッチしたものを指すので注意が必要。

242/244/266/267/270/272/283/329

Perl ではダブルクォート文字列の中から関数を呼び出すこともできる。また、qq{...} は "..." と同じでダブルクォートの区切りとして利用でき、\Q...\E はその間の記号文字のほとんどにバックスラッシュを挿入する。 更に /x された正規表現オペランド内では空白やコメントを自由に使うことができるようになる。

$regex = "\Q$item\E";  # $item を安全にする

m{
    正規表現  # コメント
}x;

# 置換の場合 (この場合 ?...? デリミタは意味を持たない)
$val =~ s{
    # 正規表現オペランド
}{
    # 置換オペランド
}ex;

s{regex}"replacement"  というかたちでも OK

これに関連してダブルクォート文字列中に \b があってもそれは単語境界ではなくバックスペースとして認識され、\d は単に \ が取り除かれて d となる。(ダブルクォートを展開する時点で \ が除去される。)一方、\L や \U などはオペランドへの初期の検査で使われ、正規表現コンパイルされる文字にだけ影響を与える。これらに対する混乱を避けるにはメタ文字のきちんとした把握が必要になる。なお、非 ASCII 文字のための 8 進、16 進エスケープという使い方もある。

245/246

Perl での正規表現処理は 1) 正規表現範囲の決定 2) ダブルクォート処理 3) 必要な場合の /x 処理 4) エンジンによる正規表現コンパイル――という手順を踏む。このとき変数展開(2 の段階)は動的な変数の変化に対応するため、マッチコードの開始されるまで行われない。

248-250/254/255

Perl には貪欲型だけでなく怠け者型のマッチ演算子がある。そこで否定文字クラスの代わりに怠け者型を使うこともできるが、効率は劣る。また、怠け者型は最低でも何かにマッチしようとする動きをするため、否定文字であれば越えないような位置でも通過してしまうことがあり、単純な代替の利くケースはあまり多くない。

マッチ数 貪欲型(最大マッチ) 怠け者型(最小マッチ)
任意の回数 * *?
1 回以上 + +?
省略可能 ? ??
範囲指定 {min,max} {min, max}?
下限 {min,} {min,}?
回数指定 {num} {num}? 特に違いはない

他にもコメントの (?#...) や、選択のみの括弧を示す (?...) などもある。また、(?i) は文字ケースの無視を指示し、m : 複数行モード、s : 単独行モード、x : 自由書式などでも同様で組み合わせることもできる。

251-252

Perl5 では「(?=...)」による先読みと「(?!=...)」による否定先読みを使うことができる。(例えば「A (?=Cat|Dog)」。)これらは検索文字列には何ら影響を与えずに先行調査のみを行う。そのためマッチを得る丸括弧に併用するとマッチ部分から先読み部分の除いた箇所を取り込むことができる。

256/257-258/259-260

Perl における改行をめぐるマッチのふるまい。($ はテキスト末尾の改行の前にマッチする。)

モード ^ と $ (行アンカー)による対象テキスト認識 ドット
デフォルトモード 改行文字の有無に関係なく単独文字列とみなす
(内部の改行を意識しない)		 改行とマッチ
しない
単独行モード(/s) 改行文字の有無に関係なく単独文字列とみなす
(内部の改行を意識しない)		 全ての文字と
マッチ
複数行モード(/m) 改行によって区切られた複数論理行とみなす
(内部の改行を意識する)		 改行とマッチ
しない
純粋な複数行(/ms) 改行によって区切られた複数論理行とみなす
(内部の改行を意識する)		 全ての文字と
マッチ

ここから /m の使用は、^ か $ に改行の処理方法の変更だけを指示するものであることが分かる。

263/264

Perl5 での /G アンカーは前のマッチの終了した位置にマッチする。つまり、マッチ失敗時のシフトが実質的に無効化される。このマッチの終了地点は pos 関数で取得することができる。(pos による位置の代入もできるが保守性を損なうので薦められない。)

274

正規表現のデリミタにシングルクォートを使うとダブルクォート風ではなくシングルクォート風に展開される。(つまり変数展開などが行われなくなる。)更に疑問符をデリミタとして使うと最初のマッチに対してだけ成功を返すようになる。(つまり 1 回だけ成功させたい場合に使う。)

276-277/292

m/.../g で無にマッチする正規表現を使うと(例えば「m/^/g」)、(永久ループを避けるため) Perl5 では自動的に 1 文字先に進む。また、それとは別に正規表現が空だった場合には、その時点でのデフォルトの正規表現を使う。(但し、split の場合には対照文字列を文字単位に分割する指示になる。)

277/280/281

/g を伴わないリストコンテキストのマッチでのイディオム。

if(($year, $month, $day) = 
    $date =~ m{^ (\d+) / (\d+) / (\d+) $}x)
{
    # マッチに成功した場合
}
else
{
    # マッチに失敗した場合、$ year などは undef
}

そして /g を伴うリストコンテキストのマッチでのイディオム。(取得したものがキーと値のペアであればハッシュにそのまま代入できる。)

# マッチの結果を %alias に代入する
%alias = $text =~ m/^alias\s+(\S+)\s+(.+)/mg;

285/286

置換処理中で /e を使うと eval{...} のように置換オペランドが実行時評価され、その結果が使われる。この評価はマッチのたびに行われる。ちなみに /e が複数指定されると、置換オペランドがその回数だけ評価される。

# WWW での URL 特殊文字を 16 進形式にエンコード
$url =~ s/([^a-zA-Z0-9])/sprintf('%%%02x', ord($1))/ge;
# その逆(デコード)
$url =~ s/%([0-9a-f][0-9a-f])/pack("C", hex($1))/ige;

287-291/293

split 演算子(split(マッチオペランド, 対象文字列, 分割数指定))を使った場合、対象文字列は変更されない。また、分割数はマッチ回数ではなく上限値として解釈される。分割数指定がない場合は最後の空要素以外が返される。これが必要な場合はそれを含めた大きな値を指定するか、-1 で全ての要素を返すように指定する。なお、split で =~ を使うと挙動がおかしくなるので使わない方がよい。また、マッチオペランドがスカラーの場合は実行のたびにコンパイルされる。

295/305/310/311/317/335

Perl 固有の効率改善のための手法。(基本は従来型 NFA と同じ。)なお、正規表現のサイズと効率は別問題なので /o などの利用できるものは利用した方がよい。

$& (前回の正規表現でマッチしたもの)の使用を確認するプログラムとして以下を挙げる。

sub CheckNaughtiness
{
    local($_) = 'x' x 10000;  # 大きなデータ

    # 何も実行しないループでの計測
    local($start) = (times)[0];
    for($i = 0; $i < 5000; $i++) { }
    local($overhead) = (time)[0] - start;

    # 同じ回数にかかる時間の計測
    $start = (times)[0];
    for($i = 0; $i < 5000; $i++) { m/^/; }
    local($delta) = (time)[0] - start;

    # 10 倍というのは著者の経験による
    print "It seems your code is ";
    printf "%s (overhead=%.2f, delta=%.2f)\n",
        ($delta > $overhead * 10) ? "naughty" : "clean",
        $overhead, $delta;
}

298-301/303

/o を使うと正規表現オペランドが最初に評価されたときのコンパイル結果をその後も使い続ける。これにより余計な再コンパイルの行われることを避けることができるので、それを明示したい場合に使う。当然ながら、これは値が変わっても再コンパイルされなくなるので、動的に初回のみコンパイルさせるには eval を併用する。このような再コンパイルを多く伴う場合には事前に効率的なマッチを行うようにした方が結果的にはよくなることが多い。

while(...)
{
    ・・・
    $regex = &GetReply('hello');
    # foreach のブロック全体が '' で囲まれ eval の対象
    eval 'foreach $item (@items)
    {
        if($item =~ m/$regex/o)
        {
            ・・・
        }
    }';

    die $@ if $@;  # eval でエラーがあると $@ にセットされる
}

314-315

置換文字列の最適化は $& などが使われたり置換部分がマッチ部分よりも長い場合などでは内容にかかわらず無効化される。逆にいうと、マッチの始まる前から置換部分の長さが分かっている場合に最適化が有効となる。

318-320

Perl での最適化の多くはどのマッチでも現れるリテラルテキストを正規表現から導くことで行われる。-Dr を使った場合、このリテラルテキストは「start `clump'」として表示される。しかし、リテラルテキストが Perl によって認識できない場合もある。なお、-Dr による他の出力は以下の通り。

メッセージ 意味
must have "clump" back num 塊(clump)が num の位置から必要
stclass `:kind' 特定文字種を要求する場合
(SPACE や DIGIT など、ANYOF は文字クラス)
plus + によって支配されていること
anchored キャレットアンカーで始まる場合
implicit .* で始まる場合

320-322

study 関数を使うと Perl は選択された塊の中から珍しいと思われる 1 文字を選び出し、マッチ時にそれが含まれているかどうかチェックするようになる。(もし含まれていなければ、それ以降の調査を省ける。)このチェックは正規表現エンジンではなく対象の移動時点で行われるが、文字列が変更されるとその効果を失う。そして、study は対象文字列が短い場合や少ないマッチしか行わない場合、Perl が対象リテラルテキストを判別できない場合などには、そのオーバーヘッドを防ぐために使わない方がよい。逆にいうと、大きな文字列でマッチが多く行われる場合に向いている。

$/ で <> のブロックモードを変更している。例えば、$/ = ".\n"; はピリオドか改行をブロックの終了と指示するようになるので、while(<>) すると行単位ではなくパラグラフ単位で読み込むようになる。

330/339

バックスラッシュの頻出を防ぐために正規表現中でのリテラルのための表記をあらかじめ変数として定義しておくとよい。これを元に更に特定の表現を変数として用意するのも有効である。しかし、何がどう展開され、バックスラッシュのエスケープがどうなり、部分表現の中で丸括弧のない選択を使うなどでは十分な注意を払う必要がある。また、/x は文字クラス内では効力を持たない(自由形式のスペーシングやコメントを利用できない)、正規表現中のコメントは改行か正規表現の末尾まで続く(途中に入れる場合は手動で \n を追加する)、「${val}[^$NonASCII]」のように [ ] を配列要素としない記述が必要となる場合もある。

$esc        = '\\\\';  # 「\」自身
$space      = '\040';
$OpenBR     = '\[';
$OpenParen  = '\(';
$NonASCII   = '\x80-\xff';
$CRlist     = '\n\015';  # 本来的には \015 だけが正しい
$Period     = '\.';
$tab        = '\t';
$CloseBR    = '\]';
$CloseParen = '\)';
$ctrl       = '\000-\037';  # HEX での 0x1F まで

▲ [ Top ]

開明堂
Copyright (C) 2001-2006 唯野　Comment to Webmaster
Last Modified 2002.11.28 　Since 2001.6.21　Readed 2001.6.20