コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

正規表現

出典: フリー百科事典『ウィキペディア(Wikipedia)』
EREから転送)

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

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

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

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

ほとんどのプログラミング言語では、ライブラリによって正規表現を使うことができる他、一部の言語では正規表現のリテラルもある。「正規表現によるマッチ」を意味する(専用の)演算子がある言語なども一部ある。具体例として、grep, AWK, sed, Perl, Tcl, lex などがある。

それぞれの言語やアプリケーションで細部の仕様が異なっている、といったように思われることも多いが(古い実装では実際にそのようなことも多い)、近年は同じライブラリを使っていれば同じということも多い。またPOSIXなど標準もある。

基本的な概念

[編集]

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

形式的な説明

[編集]

記号(アルファベット) 上の正規表現は次のようなものから成る。正規表現があらわす記号列(アルファベット列)の集合によって形式言語が定義される。

  • は正規表現である。これは記号列を何も含まない空集合 を表す。
  • の任意の要素)は正規表現である。これは という記号列のみからなる集合 を表す。
  • が正規表現ならば、
    • も正規表現である。これは に含まれる記号列の集合と に含まれる記号列の集合の和集合を表す。
    • も正規表現である。これは に含まれる記号列に に含まれる記号列をつなげてできる記号列の集合 を表す。
    • も正規表現である。これは に含まれる記号列を 0 個以上つなげてできる文字列の集合 を表す(クリーネ閉包)。
  • 上記の帰納的導出によって構成される記号列のみが正規表現である。

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

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

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

の代わりに と書くことや、 の代わりに と書くこともある。また、「」や「」の優先順位を明確にするために、補助的なカッコも(上述の定義には含めていないが)必要である。

実用的説明

[編集]

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

例えば、「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 など)。

PerlTclの正規表現はヘンリー・スペンサー()によって書かれたものから派生している(Perlは後にスペンサーの正規表現を拡張し、多くの機能を追加した)。フィリップ・ヘーゼルはPerlの正規表現とほぼ互換のものを実装する試みとしてPerl Compatible Regular Expressions (PCRE) を開発した。これはPHPApacheなどといった新しいツールで使用されている。

Rakuでは、正規表現の機能を改善してその適用範囲や能力を高め、Parsing Expression Grammarを定義できるようにする努力がなされた。この結果として、Raku文法の定義だけでなくプログラマのツールとしても使用できる、Perl 6 rulesと呼ばれる小言語が生み出された。

(本来の)正規表現からの拡張は各種あり便利であるがその多くは、(本来の)正規言語から逸脱するものであり、キャプチャなどが代表例である。なお、正規言語から逸脱しないことによって理論的な扱いが可能になるという利点があるため、例えば「非包含オペレータ」の提案ではそういった観点からの理由も挙げられている。

Rakuに限らずいくつかの実装では、(Perlではsubpatternと呼んでいる)部分パターンの定義とその再帰的な呼出しにより、例えばカッコの対応などといった(本来の)正規表現では不可能なパターンも表現できる。これは、対象部分にマッチした文字列が捕獲され、後から利用できるキャプチャとは異なり、パターンそのものの定義と利用である。PHP, Perl, Python(regexライブラリ), Ruby などで利用できる。

構文

[編集]

標準

[編集]

UNIXの標準であるPOSIXでは、単純正規表現基本正規表現拡張正規表現の3種類の記法が示されている。このうち、単純正規表現は「歴史的[注 1]」また「レガシー[注 2]」と書かれており、後方互換性を提供するものとされ、標準の将来の版では廃止され得る[注 3]と注意されている。

単純正規表現

[編集]

単純正規表現はSRE[注 4]とも呼ばれる。その仕様は「regexp.h」のマニュアルページとして示されている[3]

基本正規表現

[編集]

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

この文法では、ほとんどの文字はリテラル(機能を意味せず書かれたそのまま)に扱われる。つまり、ある文字はその文字にのみマッチする。例えば、正規表現「a」は文字「a」にマッチし、正規表現「(bc」は文字列「(bc」にマッチするなど。例外はメタ文字と呼ばれる。

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

古いバージョンの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]」ではすべての言語のすべてのアルファベット小文字にマッチするわけではない[注 6]。そのため、POSIX 標準では次の表に示されているクラス、つまり文字の区分を定義している。

POSIX クラスを用いた正規表現[注 7] 対応する表現 意味
[[: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[:cntrl:]] 印字文字
[[:print:]] [^\t\n\r\f\v[:cntrl:]] 印字文字とスペース

例:正規表現「[[:upper:]ab]」は英語の大文字「A」〜「Z」と「a」と「b」のうち1文字のみにマッチする。

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

拡張正規表現

[編集]

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

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 空白文字、つまり「[ \t\n\r\f]」(ASCII文字集合の場合)
\S 空白文字以外の文字、つまり、[^\s]

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

正規表現ライブラリ

[編集]

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

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

脚注

[編集]

注釈

[編集]
  1. ^ : historical
  2. ^ : legacy
  3. ^ : may be withdrawn
  4. ^ : simple regular expressions
  5. ^ : basic regular expression
  6. ^ これは正規表現として「[a-z]」を使用していたことが原因である。
  7. ^ 所定の文字列を内側の括弧およびコロンで囲って「POSIX クラスを表現」し、外側の括弧は「その1字のみからなる正規表現を記述」している。
  8. ^ : extended regular expression

出典

[編集]
  1. ^ J. ホップクロフト、R. モトワニ、J. ウルマン『オートマトン言語理論 計算論 I 第2版』サイエンス社、2003年。ISBN 9784781910260 
  2. ^ 中村克彦『コンピュータとは何か?』東京電機大学出版局、2018年、156頁。「多くの文献では正則表現または正規表現と呼んでいるが、数学では“regular”の訳語として「正則」を当てるのが一般的であり、“expression”は算術式や論理式と同様に「式」と呼ぶべきである」 
  3. ^ POSIX > XSH > regexp(3)
  4. ^ POSIX > Base Definitions > Regular Expressions > Basic Regular Expressions
  5. ^ POSIX > Base Definitions > Regular Expressions > Extended Regular Expressions
  6. ^ PCRE - Perl Compatible Regular Expressions
  7. ^ https://github.com/kkos/oniguruma
  8. ^ https://github.com/k-takata/Onigmo
  9. ^ Perl Regular Expression Syntax - 1.81.0
  10. ^ syntax_option_type Synopsis - 1.81.0
  11. ^ <regex> - cplusplus.com
  12. ^ Regular expressions library (since C++11) - cppreference.com
  13. ^ 正規表現ライブラリ - cppreference.com
  14. ^ regex - cpprefjp C++日本語リファレンス

参考文献

[編集]

外部リンク

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