正規表現

出典: フリー百科事典『ウィキペディア（Wikipedia）』

正規表現（せいきひょうげん、regular expression）とは、文字列の集合を一つの文字列で表現する方法の一つである。正則表現（せいそくひょうげん）とも呼ばれ、形式言語理論の分野では比較的こちらの訳語の方が使われる。まれに正規式と呼ばれることもある。

もともと正規表現は形式言語理論において正規言語を表すための手段として導入された。形式言語理論では、形式言語が正規言語であることと正規表現によって表せることは同値である。

その後正規表現はテキストエディタ、ワードプロセッサをはじめとするアプリケーションソフトでパターンマッチ文字列を表すために使用されるようになり、表せるパターンの種類を増やすために本来の正規表現にはないさまざまな記法が新たに付け加えられた。このような拡張された正規表現には正規言語ではない文字列も表せるものも多く、ゆえに正規表現という名前は実態に即していない面もあるが、伝統的に正規表現と呼ばれ続けている。

この記事では主にこのような正規表現を用いたパターンマッチについて説明している。以下、誤解のない限り、アプリケーションソフトやプログラミングにおいて正規表現を用いた文字列のパターンマッチを行う機能のことを、単に正規表現という。

ほとんどのプログラミング言語では、構文またはライブラリによって正規表現を使うことができるようになっている。構文やライブラリに正規表現を備えたプログラミング言語やユーティリティとして、AWK、Sed、Perl、Python、Ruby、Java、JavaScript、PHPなどがある。

また、プログラミング言語の開発などに用いるlexも正規表現を使う。

それぞれの言語やアプリケーションで細部の仕様が異なっているが、POSIXにより標準規格も定められそれに準拠するものも増えてきてはいる。

[編集] 基本的な概念

しばしばパターンと呼ばれる正規表現は、文字列群を表現する表現法である。通常、全ての要素をリストせずに文字列群を簡潔に表現するのに用いられる。例えば、Handel、Händel、Haendel という三つの文字列を含む集合は "H(ä|ae?)ndel" というパターンで表現できる（あるいは、パターンは個々の三つの文字列にマッチすると言われる）。ほとんどの形式では、もし特定の集合にマッチする何らかの正規表現が存在すれば、無限の数のそのような表現がある。ほとんどの形式では正規表現を構築するのに次の演算子を提供している。

選言

縦棒は選択肢を区切る。例えば、"gray|grey" は gray または grey にマッチし、これは普通 "gr(a|e)y" に短縮される。

グループ分け

丸括弧はスコープと演算子の優先順位を定義するのに用いられる。例えば、"gr(a|e)y" では "(a|e)" の部分で a または e を示し、全体で gray または grey にマッチする。

量化

文字やグループの後ろの量化子は、直前の表現が何回現れることが許されるかを指定する。非常によく使われる量化子は ? と * と + である。

?: 疑問符は直前の表現が0個か1個あることを示す。例えば、"colou?r" は　color と colour にマッチする。
*: アスタリスクは直前の表現が0個以上あることを示す。例えば、"go*gle" は ggle、gogle、googleなどにマッチする。
+: プラス符号は直前の表現が1個以上あることを示す。例えば、"go+gle" は gogle や google などにマッチするが、ggleにはマッチしない。

これらの構文は任意の複雑な表現を形成するために組み合わされて使用される。

[編集] 歴史

正規表現の起源は、いずれも理論計算機科学の一分野であるオートマトン理論や形式言語理論にみることができる。これらは計算のモデル化（オートマトン）や形式言語の分類方法などを扱う学術分野である。数学者のスティーヴン・クリーネは1950年代に正規集合と呼ばれる独自の数学的表記法を用い、これらの分野のモデルを記述した。ケン・トンプソンはテキストファイル中のパターンにマッチさせる手段として、この表記法をエディタQEDに導入した。彼はこの機能をUNIXのエディタedにも追加し、後に一般的な検索ツールであるgrepの正規表現へと受け継がれていった（grepはedエディタの正規表現検索コマンドg/re/pから派生した単語である。reは正規表現（regular expression）の頭文字。）。これ以降、トンプソンの正規表現の適用にならい、多くのUNIX系のツールがこの方法を採用した（例えばexpr、awk、Emacs、vi、lex、Perlなど）。

PerlとTclの正規表現はHenry Spencerによって書かれたものから派生している（Perlは後にSpencerの正規表現を拡張し、多くの機能を追加した）。Philip HazelはPerlの正規表現に限りなく近いものを実装する試みとしてPerl Compatible Regular Expressions（PCRE）を開発した。これはPHPやApacheなどといった新しいツールで使用されている。Perl 6では、正規表現の機能を改善してその適用範囲や能力を高め、解析表現文法を定義できるようにする努力がなされた。この結果として、Perl 6文法の定義だけでなくプログラマのツールとしても使用できる、Perl 6 rulesと呼ばれる小言語が生み出された。これらの規則は正規表現の機能のすべてを保持しながら、副規則を通して再帰下降構文解析のBNFスタイルの定義を行うことができる。

構造化情報標準における、文書やデータベースのモデル化に対する正規表現の使用は重要である。これは1960年代に始まり、ISO SGMLのような産業標準が確立された1980年代に拡大した。構造規定言語の標準の中核は正規表現である。より単純かつ明白な例としては、DTD要素グループの構文において正規表現が使われている。

[編集] 文法

[編集] 伝統的な UNIX の正規表現

UNIX における基本正規表現の文法は POSIX によって旧式(obsolete)であるとされている。しかし、後方互換性のためにいまだに広く用いられている。ほとんどの正規表現を利用する UNIXのユーティリティ（grepやsed）ではデフォルトでこれを用いている。

この文法では、ほとんどの文字はリテラルに扱われる。つまり、ある文字はその文字にのみマッチする。例えば、"a" は a にマッチし、"(bc" は (bc にマッチするなど。例外はメタ文字と呼ばれる。

.	任意の文字にマッチする。
[ ]	括弧内に含まれる一文字にマッチする。例えば、[abc] は a、b、c にマッチする。英語のアルファベットでは、[a-z] は全ての小文字にマッチする。これらは混ぜることが出来る。[abcq-z] は a、b、c、q、r、s、t、u、v、w、x、y、z にマッチし、[a-cq-z]でも同様である。文字 '-' は括弧内の最初か最後にあるときのみ、リテラルに扱われる。例えば、[abc-] や [-abc]。[ や ] にマッチさせる最も手っ取り早い方法は、囲んでいる括弧内で、括弧が最初になるようにすることである。例えば、[][ab] は ]、[、a、b にマッチする。
[^ ]	括弧内に含まれない一文字にマッチする。例えば、[^abc] は a、b、c 以外の任意の文字にマッチする。[^a-z] は小文字以外の任意の一文字にマッチする。上と同様にこれらは混ぜることが出来る。
^	行の最初にマッチする。
$	行の最後にマッチする。
	これに囲まれた表現は、後に呼び出すことが出来る。次の \n の項を参照のこと。
\n	ここで n は1から9までの数である。n 番目ので囲まれた部分にマッチする。この構文は理論的には不正で（正則文法の記述力を超える）、拡張正規表現では採用されていない。
*	一文字に続く "" は0回以上の表現の繰り返しにマッチする。例えば、"[xyz]" は ""、"x"、"y"、"zx"、"zyx" などにマッチする。 n を1から9までの数字としたとき、\n* はで囲まれた部分の0回以上の繰り返しにマッチする。例えば、"$a.$c\1" は abcab* や abcabab にマッチするが、abcac にマッチしない。 "$" や "$" で囲まれた表現に続く "*" は無効とされる。しかし、一部の環境ではそうならない。
\{x,y\}	直前の"ブロック"の x 回以上 y 回以下の繰り返しにマッチする。例えば、"a\{3,5\}" は aaa、aaaa、aaaaa にマッチする。

特定の正規表現の実装では、一部のメタ文字の前のバックスラッシュを異なって解釈する。例えば egrep や perl は、バックスラッシュの付いていない 括弧や縦棒 "|" をメタ文字と解釈し、バックスラッシュの付いているものをリテラルに解釈する。古いバージョンの grepは選言演算子 "|" をサポートしていない。

例

".at" は hat、cat、bat のような三文字の文字列にマッチする

"[hc]at" は hat と cat にマッチする

"[^b]at" は bat 以外の ".at" でマッチする全ての文字列にマッチする

"^[hc]at" は行の最初にあるときだけ、hat と cat にマッチする

"[hc]at$" は行の最後にあるときだけ、hat と cat にマッチする

文字列の範囲はロケールに依存する。例えば、エストニア語のアルファベットでは、s の後に z があり、その後は t、u、v、w、x、y と続くので、[a-z] ではすべての小文字のアルファベットにマッチしない^[1]。そのため、POSIX 標準では次の表に示されているクラス、つまり文字の区分を定義している。

POSIX クラス	対応する表現	意味
[:upper:]	[A-Z]	大文字
[:lower:]	[a-z]	小文字
[:alpha:]	[A-Za-z]	アルファベット
[:alnum:]	[A-Za-z0-9]	数字とアルファベット
[:digit:]	[0-9]	数字
[:xdigit:]	[0-9A-Fa-f]	16進数
[:punct:]	[.,!?:...]	句読点
[:blank:]	[ \t]	スペースとタブ
[:space:]	[ \t\n\r\f\v]	空白文字
[:cntrl:]		制御文字
[:graph:]	[^ \t\n\r\f\v]	印字文字
[:print:]	[^\t\n\r\f\v]	印字文字とスペース

例: [[:upper:]ab] は大文字と a と b のみにマッチする。

いくつかのツールで使用できる、POSIX にないクラスとして [:word:] がある。[:word:] は通常 [:alnum:] とアンダースコアからなる。これらが多くのプログラミング言語で識別子として使用できる文字であることを反映している。

[編集] POSIX の拡張正規表現

より現代的な拡張正規表現は多くの場合、現在のUNIX のユーティリティでコマンドラインオプションに "-E" を含めることで使用できる。

POSIX の拡張正規表現は伝統的な UNIX の正規表現に似ているが、いくつかの点で異なっている。

メタ文字 "+"、"?"、"|" が追加されている。また、バックスラッシュが削除されて、\{...\} は {...} になり、$...$ は (...) になる。

"("、")"、"["、"]"、"."、"*"、"?"、"+"、"^"、"$" といった文字は特別な記号として使用されるので、リテラルに使いたいときはエスケープしなければならない。エスケープするには、それらの前に '\' を付ける。例えば、"a\.($|$)" は a.) や a.( にマッチする。

[編集] Perl の正規表現

Perl は POSIX の拡張正規表現さえも上回る豊富な文法を持っている。その例として、POSIX とは異なり、Perl では最長マッチを行うか指定できることが挙げられる。例えば、パターン "a.*b" では .* はできるだけ長い文字列にマッチさせようとするが、パターン "a.*?b" ではできるだけ短い文字列にマッチさせようとする。だから "a bad dab" に対しては、前者のパターンでは文字列全体にマッチし、後者のパターンでは "a b" にだけマッチする。

また、Perl には以下の定義済み文字クラスがある。

\d	数字 [0-9]
\D	数字以外の文字、つまり [^\d]
\w	アルファベット、数字またはアンダーバー、つまり [a-zA-Z_0-9] （ロケールに依存し、例えばウムラウト付き文字などの扱いが変わる）
\W	アルファベット、数字やアンダーバー以外の文字、つまり [^\w]
\s	空白文字、つまり大抵の制御文字クラス \f、\n、\r、\t や \v
\S	空白文字以外の文字 [^\s]

すぐれた機能をもつ Perl の拡張正規表現と、多くのプログラミング言語やソフトウェアで採りいれられている。例えば、Java の Pattern クラス、Python、Ruby]] などがそうである。しかし、これらが Perl の正規表現と完全に互換である訳ではない。また、Perl Compatible Regular Expressions (PCRE) と呼ばれる汎用の正規表現ライブラリは、アプリケーションに組み込まれ、Perl の正規表現とほぼ互換の機能を提供する。

[編集] 正規表現ライブラリ

言語処理系やアプレケーションが正規表現をサポートしていない場合にでも、正規表現に必要な処理を提供する正規表現ライブラリを導入することで正規表現を使うことができる。Eximのために開発されたPCREは、C言語で記述されたPerl互換のライブラリで、ApacheやPostfixをはじめ、さまざまなソフトウェアに組み込まれている。また、正規表現オブジェクトごとに異なる文字エンコーディングを指定できる特徴をもつ「鬼車（おにぐるま）」は、鬼車は、Rubyの1.9系列やPHPの5系列に採用されている。

[編集] 形式言語理論における正規表現

アルファベット A = {a₁,...,a_n} 上の正規表現は次のように定義される。正規表現の表す集合が、その正規表現の表す言語である。

∅ は正規表現である。これは空集合 ∅ を表す。
a_i（A の任意の要素）は正規表現である。これは a_i のみからなる集合 { a_i } を表す。
X と Y が正規表現ならば、
- X|Y も正規表現である。これは X の表す集合と Y の表す集合の和集合を表す。
- XY も正規表現である。これは X に含まれる記号列に Y に含まれる記号列をつなげてできる記号列の集合 { ab | a ∊ X, b ∊ Y } を表す。
- X* も正規表現である。これは X に含まれる記号列を 0 個以上つなげて出来る文字列の集合 { aⁿ | a ∊ X, n ≥ 0 } を表す。
上記の帰納的導出によって構成される記号列のみが正規表現である。