正規表現

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

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

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

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

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

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

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

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

基本的な概念[編集]

理論的に明解であり扱いも容易であるため、形式的な説明を先に述べる。

形式的な説明[編集]

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

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

正規表現の定義に、次の項目を含めることもある:

  • ε は正規表現である。これは空記号列 ε のみからなる集合 { ε } を表す。

正規表現 ε の表す集合は正規表現 ∅* の表す集合に等しいので、ε を正規表現の定義に含めなくても ∅* で代用できる。

X|Y の代わりに X+Y と書くことや、XY の代わりに X·Y と書くこともある。また、「|」や「*」の優先順位を明確にするために括弧を使うこともある。

実用的説明[編集]

以下ではもっぱらよく使われているライブラリやツール等の実用的な観点から説明する。

例えば、「Handel」、「Hendel」、「Haendel」 という三つの文字列を含む集合は 「H(e|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の正規表現へと受け継がれていった。これ以降、トンプソンの正規表現の適用にならい、多くのUNIX系のツールがこの方法を採用した(例えば exprawkEmacsvilexPerl など)。

PerlTcl の正規表現はヘンリー・スペンサーによって書かれたものから派生している(Perlは後にスペンサーの正規表現を拡張し、多くの機能を追加した)。フィリップ・ヘーゼルは Perl の正規表現とほぼ互換のものを実装する試みとしてPerl Compatible Regular Expressions(PCRE)を開発した。これはPHPApache などといった新しいツールで使用されている。Perl 6では、正規表現の機能を改善してその適用範囲や能力を高め、Parsing Expression Grammar を定義できるようにする努力がなされた。この結果として、Perl 6 文法の定義だけでなくプログラマのツールとしても使用できる、Perl 6 rules と呼ばれる小言語が生み出された。これらの規則は正規表現の機能のすべてを保持しながら、副規則を通して再帰下降構文解析バッカス・ナウア記法の定義を行うことができる。

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

構文[編集]

標準[編集]

The nice thing about standards is that you have so many to choose from. --Andrew S. Tanenbaum

Unixの標準であるPOSIXでは、「simple regular expressions」「basic regular expression (BRE)」「extended regular expression (ERE)」の3種類の記法が示されている。このうち、「simple regular expressions」は「歴史的(historical)」また「レガシー(legacy)」と書かれており、後方互換性を提供するものとされ、標準の将来の版では廃止され得る(may be withdrawn)と注意されている。

simple regular expressions(SRE)[編集]

simple regular expressionsの仕様は「regexp.h」のマニュアルページとして示されている。[1]

basic regular expression(BRE)[編集]

基本正規表現とも。ほとんどの正規表現を利用する UNIXのユーティリティ(grepやsed)のデフォルトはこれである。[2]

この文法では、ほとんどの文字はリテラル(機能を意味せず書かれたそのまま)に扱われる。つまり、ある文字はその文字にのみマッチする。例えば、正規表現「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]」は一文字「a」、「b」 、「c」 、「-」にマッチする。一文字「[」や「]」自身にマッチさせる最も手っ取り早い方法は、囲んでいる括弧内で、括弧が最初になるようにすることである。例えば正規表現「[][ab]」は一文字「]」、「[」、「a」、「b」にマッチする。
[^…] 括弧内に含まれない一文字にマッチする。例えば正規表現「[^abc]」は「a」、「b」、「c」以外の任意の文字にマッチする。正規表現「[^a-z]」は小文字以外の任意の一文字にマッチする。上と同様にこれらは混ぜることが出来る。
^ 行の最初にマッチする。
$ 行の最後にマッチする。
(…) これに囲まれた表現は、後に呼び出すことが出来る。次の \1、…、\9 の項を参照のこと。
  • \1
  • \2
  • \3
  • \4
  • \5
  • \6
  • \7
  • \8
  • \9
それぞれ「(」と「) で囲まれた部分に先行してマッチした1~9 番目の文字列と同じ文字列パターンにマッチする。この機能は理論的には、言うならば非正規で(正規言語の記述力を超える)、POSIX拡張正規表現では採用されていない。
*
  • 一文字に続く「*」は0回以上の表現の繰り返しにマッチする。例えば「[xyz]*」は空文字列や文字列「x」、「y」、「zx」、「zyx」などにマッチする。
  • n を1から9までの数字としたとき、基本正規表現「\n*」は「(」と「)」で囲まれた部分の0回以上の繰り返しにマッチする。例えば、基本正規表現「(a.)c\1*」 は文字列「abcab」 や「abcabab」にマッチするが、文字列「abcac」にはマッチしない。
  • (」と「)」で囲まれた表現に続く「*」 は無効とされる。しかし、一部の環境ではそうならない。
{m,n} 直前のブロックの m 回以上 n 回以下の繰り返しにマッチする。例えば、正規表現「a{3,5}」 は文字列「aaa」、「aaaa」、「aaaaa」にマッチする。

特定の正規表現の実装では、一部のメタ文字の前のバックスラッシュを異なって解釈する。例えば egrep や Perl は、バックスラッシュの付いていない括弧や縦棒「|」をメタ文字と解釈し、バックスラッシュの付いているものをリテラルに解釈する。古いバージョンの 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]」ではすべて言語のすべてのアルファベット小文字のにマッチするわけではない[3]。そのため、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」~「Z」と「a」と「b」のうち一文字のみにマッチする。

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

extended regular expression(ERE)[編集]

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

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

基本正規表現 拡張正規表現
(対応なし) +
(対応なし) ?
(対応なし) |
\{…\} {…}
\(…\) (…)
( \(
) \)
[ \[
] \]
. \.
* \*
? \?
+ \+
^ \^
$ \$

例えば、拡張正規表現「a\.(\(|\))」は文字列「a.)」や 文字列「a.(」にマッチする。

GNU Emacsの正規表現[編集]

GNU find コマンドにおけるデフォルトの正規表現文法としても用いられる。(findutils-4.2.28)

GNU Emacs Manual - Regexps

Perl の正規表現[編集]

PerlPOSIX の拡張正規表現さえも上回る豊富な文法を持っている。その例として、POSIX とは異なり、Perl の正規表現には「非欲張り量指定子」がある。標準の「*」は、例えば正規表現「a.*b」の「.*」はできるだけ長い文字列にマッチしようとする。このふるまいを「貪欲」という。たとえば文字列「a bad dab」にマッチさせると、全体にマッチする。これに対し、Perl では使うことができる正規表現「a.*?b」の「.*?」は、マッチするのであれば、できるだけ短い文字列にマッチする。たとえば文字列「a bad dab」に対して「a b」にだけマッチする。これを「非欲張り量指定子」と言う。

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

メタ文字 マッチする対象
\d アラビア数字、つまり「[0-9]
\D アラビア数字以外の文字、つまり「[^\d]
\w アルファベット、アラビア数字またはアンダーバー、つまり「[a-zA-Z_0-9]」(ロケールに依存し、例えばウムラウト付き文字などの扱いが変わる)
\W アルファベット、数字やアンダーバー以外の文字、つまり「[^\w]
\s 空白文字、つまり大抵の制御文字クラス ASCII文字集合のフォームフィード文字、ラインフィード文字、キャリッジリターン文字、水平タブ文字、垂直タブ文字[どこ?]
\S 空白文字以外の文字、つまり、[^\s]

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

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

言語処理系やアプリケーションが正規表現をサポートしていない場合にでも、正規表現に必要な処理を提供する正規表現ライブラリを導入することで正規表現を使うことができる。以下にその一例を挙げておく。

  • PCRE
    • Perl互換のライブラリ。Eximのために開発され、ApachePostfixをはじめ、さまざまなソフトウェアに組み込まれている。
  • 鬼車 (ライブラリ)英語版
    • 正規表現オブジェクトごとに異なる文字エンコーディングを指定できる特徴をもつ。Rubyの1.9系列やPHPの5系列に採用されている。Mac OS X用に検索ウィンドウを追加して移植したOgreKit(Oniguruma Regular Expression Framework for Cocoa)が存在する。
  • re2英語版
    • PCREなどのバックトラック式ではなくオートマトンを用いることで、省メモリでマッチングを行うことができる。Googleが内部で利用している。
  • GNU Regex
  • Boost.Regex
    • Boost C++ライブラリによる実装。C++11規格にて標準化された。POSIXやECMAScriptなどの文法プロファイルを任意に選択することができる[5] [6]

関連項目[編集]

参考文献[編集]

脚注[編集]

外部リンク[編集]

  • 正規表現メモ - sed, grep, perlなど様々なソフトの正規表現がまとめられている