正規表現
正規表現(せいきひょうげん、regular expression)は、文字列の集合を一つの文字列で表現する方法の一つである。正則表現とも呼ばれ、形式言語理論の分野では比較的こちらの訳語の方が使われる。まれに正則式あるいは正規式と呼ばれることもある。
もともと正規表現は形式言語理論において正規言語を表すための手段として導入された。形式言語理論では、形式言語が正規言語であることと正規表現によって表せることは同値である。
その後正規表現は単機能の文字列探索ツールやテキストエディタ、ワードプロセッサなどのアプリケーションで、マッチさせるべき対象を表すために使用されるようになり、表せるパターンの種類を増やすために本来の正規表現にはないさまざまな記法が新たに付け加えられた。このような拡張された正規表現には正規言語ではない文字列も表せるものも多く、ゆえに正規表現という名前は実態に即していない面もあるが、伝統的に正規表現と呼ばれ続けている。
この記事では主にこのような正規表現を用いたパターンマッチングについて説明している。以下、誤解のない限り、アプリケーションやプログラミングにおいて正規表現を用いた文字列のパターンマッチングを行う機能のことを、単に正規表現という。
ほとんどのプログラミング言語では、ライブラリによって正規表現を使うことができる他、一部の言語では正規表現のリテラルもある。「正規表現によるマッチ」を意味する(専用の)演算子がある言語なども一部ある。具体例として、grep, AWK, sed, Perl, Tcl, lex などがある。
それぞれの言語やアプリケーションで細部の仕様が異なっている、といったように思われることも多いが(古い実装では実際にそのようなことも多い)、近年は同じライブラリを使っていれば同じということも多い。またPOSIXなど標準もある。
理論的に明解であり扱いも容易であるため、形式的な説明を先に述べる。
記号(アルファベット)A = \{a_1, \dots, a_n\} 上の正規表現は次のようなものから成る。正規表現があらわす記号列(アルファベット列)の集合によって形式言語が定義される。
\varnothing は正規表現である。これは記号列を何も含まない空集合 \varnothing を表す。
a_i(A の任意の要素)は正規表現である。これは a_i という記号列のみからなる集合 \{a_i\} を表す。
X と Y が正規表現ならば、
X\mid Y も正規表現である。これは X に含まれる記号列の集合と Y に含まれる記号列の集合の和集合を表す。
XY も正規表現である。これは X に含まれる記号列に Y に含まれる記号列をつなげてできる記号列の集合 \{ab\mid a \in X, b \in Y\} を表す。
X* も正規表現である。これは X に含まれる記号列を 0 個以上つなげてできる文字列の集合 \bigcup_n \{X^n\mid n \ge 0\} を表す(クリーネ閉包)。
上記の帰納的導出によって構成される記号列のみが正規表現である。
正規表現の定義に、次の項目を含めることもある:
\varepsilon は正規表現である。これは空記号列 \varepsilon のみからなる集合 \{\varepsilon\} を表す。
正規表現 \varepsilon の表す集合は正規表現 \varnothing* の表す集合に等しいので、\varepsilon を正規表現の定義に含めなくても \varnothing* で代用できる。
X\mid Y の代わりに X+Y と書くことや、XY の代わりに X\cdot Y と書くこともある。また、「\mid」や「*」の優先順位を明確にするために、補助的なカッコも(上述の定義には含めていないが)必要である。
以下ではもっぱらよく使われているライブラリやツールなどの実用的な観点から説明する。
例えば、「Handel」「Hendel」「Haendel」という3つの文字列を含む集合は「H(e|ae?)ndel」というパターンで表現できる(あるいは、パターンは個々の3つの文字列にマッチすると言われる)。ほとんどの形式では、もし特定の集合にマッチする何らかの正規表現が存在すれば、無限の数のそのような表現がある。ほとんどの形式では正規表現を構築するために次の演算子を提供している。
縦棒は選択肢を区切る。例えば「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」は「google」「gogle」「ggle」などにマッチする。
+
プラス符号は直前の表現が1個以上あることを示す。例えば、「go+gle」は「google」「gogle」などにマッチするが、「ggle」にはマッチしない。
これらの構文は任意の複雑な表現を形成するために組み合わされて使用される。
正規表現の起源は、言語学と、理論計算機科学の一分野であるオートマトン理論や形式言語理論にみることができる。20世紀の言語学では数理的に言語を扱う数理言語学が発展しその過程の一部として、また後者は計算のモデル化(オートマトン)や形式言語の分類方法などを扱う学術分野である。数学者のスティーヴン・クリーネは1950年代に正規集合と呼ばれる独自の数学的表記法を用い、これらの分野のモデルを記述した。
Unix系のツールに広まったのは、ケン・トンプソンがテキストファイル中のパターンにマッチさせる手段として、この表記法をエディタQEDに導入したことなどに始まる。彼はこの機能をUNIXのエディタedにも追加し、後に一般的な検索ツールであるgrepの正規表現へと受け継がれていった。これ以降、トンプソンの正規表現の適用にならい、多くのUnix系のツールがこの方法を採用した(例えば expr, awk, Emacs, vi, lex, Perl など)。
PerlとTclの正規表現はヘンリー・スペンサー(英)によって書かれたものから派生している(Perlは後にスペンサーの正規表現を拡張し、多くの機能を追加した)。フィリップ・ヘーゼルはPerlの正規表現とほぼ互換のものを実装する試みとしてPerl Compatible Regular Expressions (PCRE) を開発した。これはPHPやApacheなどといった新しいツールで使用されている。
Rakuでは、正規表現の機能を改善してその適用範囲や能力を高め、Parsing Expression Grammarを定義できるようにする努力がなされた。この結果として、Raku文法の定義だけでなくプログラマのツールとしても使用できる、Perl 6 rulesと呼ばれる小言語が生み出された。
(本来の)正規表現からの拡張は各種あり便利であるがその多くは、(本来の)正規言語から逸脱するものであり、キャプチャなどが代表例である。なお、正規言語から逸脱しないことによって理論的な扱いが可能になるという利点があるため、例えば「非包含オペレータ」の提案ではそういった観点からの理由も挙げられている。
Rakuに限らずいくつかの実装では、(Perlではsubpatternと呼んでいる)部分パターンの定義とその再帰的な呼出しにより、例えばカッコの対応などといった(本来の)正規表現では不可能なパターンも表現できる。これは、対象部分にマッチした文字列が捕獲され、後から利用できるキャプチャとは異なり、パターンそのものの定義と利用である。PHP, Perl, Python(regexライブラリ), Ruby などで利用できる。
UNIXの標準であるPOSIXでは、単純正規表現、基本正規表現、拡張正規表現の3種類の記法が示されている。このうち、単純正規表現は「歴史的」また「レガシー」と書かれており、後方互換性を提供するものとされ、標準の将来の版では廃止され得ると注意されている。
単純正規表現はSREとも呼ばれる。その仕様は「regexp.h」のマニュアルページとして示されている。
基本正規表現はBREとも呼ばれる。ほとんどの正規表現を利用する UNIXのユーティリティ(grepやsed)のデフォルトはこれである。
この文法では、ほとんどの文字はリテラル(機能を意味せず書かれたそのまま)に扱われる。つまり、ある文字はその文字にのみマッチする。例えば、正規表現「a」は文字「a」にマッチし、正規表現「(bc」は文字列「(bc」にマッチするなど。例外はメタ文字と呼ばれる。
古いバージョンのgrepは選言演算子「\|」をサポートしていない。
正規表現「.at」は文字列「hat」「cat」「5at」のような3文字の文字列にマッチする
正規表現「[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]」ではすべての言語のすべてのアルファベット小文字にマッチするわけではない。そのため、POSIX 標準では次の表に示されているクラス、つまり文字の区分を定義している。
例:正規表現「[:upper:]ab]」は英語の大文字「A」〜「Z」と「a」と「b」のうち1文字のみにマッチする。
いくつかのツールで使用できる、POSIX にないクラスとして「[:word:]」がある。「[:word:]」は通常「[:alnum:]」とアンダースコアからなる。これらが多くのプログラミング言語で識別子として使用できる文字であることを反映している。
拡張正規表現はEREとも呼ばれる。より現代的な拡張正規表現は多くの場合、現在の UNIXのユーティリティでコマンドラインオプションに「-E」を含めることで使用できる。
POSIXの拡張正規表現は伝統的な UNIX の正規表現に似ているが、いくつかの点で異なっている。
例えば、拡張正規表現「a\.(\(|\))」は文字列「a.)」や文字列「a.(」にマッチする。
GNU findコマンドにおけるデフォルトの正規表現文法としても用いられる。(findutils-4.2.28)
PerlはPOSIXの拡張正規表現さえも上回る豊富な文法を持っている。その例として、POSIXとは異なり、Perlの正規表現には「非欲張り量指定子」がある。標準の「*」は、例えば、正規表現「a.*b」の「.*」はできるだけ長い文字列にマッチしようとする。このふるまいを「貪欲」という。たとえば文字列「a bad dab」にマッチさせると、全体にマッチする。これに対し、Perlでは使うことができる正規表現「a.*?b」の「.*?」は、マッチするのであれば、できるだけ短い文字列にマッチする。たとえば文字列「a bad dab」に対して「a b」にだけマッチする。これを「非欲張り量指定子」と言う。
また、Perlには以下の定義済み文字クラスがある。
すぐれた機能をもつPerlの拡張正規表現は、多くのプログラミング言語やソフトウェアで採りいれられている。例えば、JavaのPatternクラス、Python、Rubyなどがそうである。しかし、これらがPerlの正規表現と完全に互換である訳ではない。また、Perl Compatible Regular Expressions (PCRE) と呼ばれる汎用の正規表現ライブラリはアプリケーションに組み込まれ、Perlの正規表現とほぼ互換の機能を提供する。
言語処理系やアプリケーションが正規表現をサポートしていない場合であっても、正規表現に必要な処理を提供する外部ライブラリを導入することで正規表現を使うことができる。以下にその一例を挙げておく。
Perl互換のライブラリ。Eximのために開発され、ApacheやPostfixをはじめ、さまざまなソフトウェアに組み込まれている。
正規表現オブジェクトごとに異なる文字エンコーディングを指定できる特徴をもつ。Rubyの1.9系列やPHPの5系列に採用されている。macOS用に検索ウィンドウを追加して移植したOgreKit(Oniguruma Regular Expression Framework for Cocoa)が存在する。
鬼車から派生した正規表現ライブラリで、Perl 5.10以降で導入された機能をサポートする。Ruby 2.0以降の標準ライブラリとして利用されている。
PCREなどのバックトラック式ではなくオートマトンを用いることで、省メモリでマッチングを行うことができる。Googleが内部で利用している。
GNU Regex
GNU Cライブラリに含まれているため、Unix系では標準で利用できる。
Boost.Regex
Boost C++ライブラリによる実装。デフォルトでPerl互換の文法が使われるが、POSIXやECMAScriptなどの文法プロファイルを任意に選択することもできる。C++11規格にてBoost.Regexのサブセットが標準化された。