Loading article…
/r[aeiou]+/g正規表現（regexまたはregexpと略される）[ 1 ]は、有理式[ 2 ] [ 3 ]とも呼ばれ、テキスト内のマッチパターンを指定する文字のシーケンスです。通常、このようなパターンは、文字列検索アルゴリズムによって、文字列に対する「検索」または「検索と置換」操作、あるいは入力検証に使用されます。正規表現の技術は、理論計算機科学と形式言語理論で開発されています。
正規表現の概念は、1950年代にアメリカの数学者スティーブン・コール・クリーネが正規言語の概念を体系化したことから始まった。正規表現はUnixのテキスト処理ユーティリティで広く使われるようになった。1980年代以降、正規表現を記述するための様々な構文が存在し、その一つがPOSIX標準であり、もう一つは広く使われているPerl構文である。
正規表現は、検索エンジン、ワープロソフトやテキストエディタの検索と置換ダイアログ、sedやAWKなどのテキスト処理ユーティリティ、および字句解析で使用されます。正規表現は多くのプログラミング言語でサポートされています。ライブラリ実装はしばしば「エンジン」と呼ばれ、[ 4 ] [ 5 ]これらの多くを再利用できます。
正規表現は、1951 年に数学者のスティーブン・コール・クリーネが正規イベントと呼ばれる数学的記法を用いて正規言語を記述したことに端を発する。[ 6 ] [ 7 ]これらは、クリーネが初期の人工ニューラルネットワークを記述しようとしたことに触発され、理論計算機科学のオートマタ理論（計算モデル）や形式言語の記述と分類の分野で生まれた。（クリーネはこれをマカロックとピッツの「理解可能」の代替として導入したが、「より記述的な用語についての提案があれば歓迎する」と認めた。[ 8 ]）パターンマッチングのその他の初期の実装には、正規表現ではなく独自のパターンマッチング構造を使用したSNOBOL言語がある。
正規表現は、1968 年以降、テキスト エディタでのパターン マッチング[ 9 ]とコンパイラでの字句解析[ 10 ]という 2 つの用途で広く使われるようになりました。プログラム形式で正規表現が初めて登場したのは、ケン トンプソンがテキスト ファイル内のパターンをマッチングする手段として、クリーネ記法をエディタQEDに組み込んだときでした。[ 9 ] [ 11 ] [ 12 ] [ 13 ]速度を上げるため、トンプソンは、JIT コンパイルの重要な初期例であるCompatible Time-Sharing System上のIBM 7094コードに対して、ジャストインタイム コンパイル(JIT)による正規表現マッチングを実装しました。 [ 14 ]彼は後にこの機能を Unix エディタedに追加し、最終的に人気の検索ツールgrepが正規表現を使用するようになりました (「grep」は ed エディタでの正規表現検索コマンドから派生した単語で、「正規表現のグローバル検索と一致する行の出力」を意味します)。[ 15 ]トンプソンが QED を開発したのとほぼ同時期に、ダグラス T. ロスを含む研究者グループが、コンパイラ設計における字句解析に使用される正規表現に基づくツールを実装した。[ 10 ]g/re/p
正規表現のこれらの初期形式の多くのバリエーションは、1970年代にベル研究所のUnix [ 13 ]プログラム（ lex、sed、AWK、exprなど）や、 viやEmacs （独自の互換性のない構文と動作を持つ）などの他のプログラムで使用されました。正規表現はその後、幅広いプログラムに採用され、これらの初期の形式は1992年にPOSIX.2標準で標準化されました。
1980年代には、より複雑な正規表現がPerlで登場しました。これは元々、Henry Spencer (1986) が書いた正規表現ライブラリから派生したもので、後にAdvanced Regular Expressionsと呼ばれるTcl用の実装を作成しました。[ 16 ] Tclライブラリは、パフォーマンス特性が向上したハイブリッドNFA / DFA実装です。SpencerのTcl正規表現実装を採用したソフトウェアプロジェクトにはPostgreSQLがあります。[ 17 ] Perlは後にSpencerの元のライブラリを拡張し、多くの新機能を追加しました。[ 18 ] Raku (以前はPerl 6と呼ばれていました)の設計における取り組みの一部は、Perlの正規表現統合を改善し、解析式文法を定義できるようにその範囲と機能を拡大することです。[ 19 ]その結果、Rakuルールと呼ばれるミニ言語が生まれ、Raku文法を定義するとともに、この言語のプログラマにツールを提供します。これらのルールは、Perl 5.x の正規表現の既存の機能を維持しつつ、サブルールを介してBNFスタイルの再帰下降パーサーを定義することも可能にします。
文書およびデータベースモデリングのための構造化情報標準における正規表現の使用は、1960年代に始まり、ISO SGML （ANSI「GCA 101-1983」を前身とする）などの業界標準が確立された1980年代に拡大しました。構造仕様言語標準の中核は正規表現で構成されています。その使用は、DTD要素グループ構文に明らかです。正規表現が使用される以前は、多くの検索言語で単純なワイルドカードが使用されていました。たとえば、「*」は任意の文字シーケンスに一致し、「?」は単一の文字に一致します。この名残は、ファイル名のglob構文やSQLLIKE演算子に今日でも見られます。
1997年からフィリップ・ヘイゼルはPCRE （Perl互換正規表現）を開発しました。これはPerlの正規表現機能を忠実に模倣しようとするもので、PHPやApache HTTP Serverなど多くの最新ツールで使用されています。[ 20 ]
今日では、正規表現はプログラミング言語、テキスト処理プログラム（特に字句解析器）、高度なテキストエディタ、およびその他のいくつかのプログラムで広くサポートされています。正規表現のサポートは、 JavaやPythonを含む多くのプログラミング言語の標準ライブラリの一部であり、Perl やECMAScriptを含む他の言語の構文に組み込まれています。2010 年代後半には、いくつかの企業が、CPU実装よりも高速なPCRE互換正規表現エンジンのハードウェア、FPGA [ 21 ] GPU [ 22 ]実装の提供を開始しました。
正規表現、またはregexという用語は、後述する数学的表記法とは異なり、テキストのマッチングパターンを表すための特定の標準的なテキスト構文を指す場合によく使用されます。正規表現の各文字（つまり、パターンを記述する文字列の各文字）は、特別な意味を持つメタ文字か、リテラルな意味を持つ通常の文字のいずれかです。たとえば、正規表現ではb.、「b」は「b」のみに一致するリテラル文字であり、「.」は改行文字を除くすべての文字に一致するメタ文字です。したがって、この正規表現は、たとえば「b%」、「bx」、「b5」に一致します。メタ文字とリテラル文字を組み合わせることで、特定のパターンのテキストを識別したり、そのパターンの複数のインスタンスを処理したりすることができます。パターンの一致は、メタ文字によって制御されるため、厳密な一致から非常に一般的な類似まで様々です。例えば、.は非常に一般的なパターンで、[a-z](「a」から「z」までのすべての小文字に一致) はそれほど一般的ではなく、はより正確なパターンです (「b」のみに一致)。メタ文字構文は、さまざまな入力データのテキスト処理の自動化を指示するために、標準的なASCIIキーボードbを使用して簡単に入力できる形式で、規定されたターゲットを簡潔かつ柔軟な方法で表現するように特別に設計されています。
この構文における正規表現の非常に単純な例として、テキストエディタで2つの異なる綴りの単語を検索することが挙げられます。たとえば、正規表現はseriali[sz]e「serialise」と「serialize」の両方に一致します。ワイルドカード文字でも同様のことができますが、メタ文字が少なく、言語ベースも単純なため、パターン化できる範囲はより限定されます。
ワイルドカード文字の一般的な使用例は、ファイルリスト内の類似した名前を網羅的に検索することですが、正規表現は通常、テキスト文字列をパターンマッチングするアプリケーションで使用されます。たとえば、正規表現は行の先頭または末尾にある余分な空白に一致します。任意の数字に一致する高度な正規表現は です。^[ \t]+|[ \t]+$[+-]?(\d+(\.\d*)?|\.\d+)([eE][+-]?\d+)?
正規表現プロセッサは、上記の構文の正規表現を、検索対象のテキストを表す文字列に対して実行および照合できる内部表現に変換します。考えられるアプローチの1つは、トンプソンの構成アルゴリズムを使用して非決定性有限オートマトン（NFA）を構築し、それを決定性にして、結果として得られる決定性有限オートマトン（DFA）を対象のテキスト文字列で実行して、正規表現に一致する部分文字列を認識することです。図は、正規表現から得られたNFAスキームを示しています。ここで、 sは、すでに再帰的にNFA N（s）に変換されている、より単純な正規表現を表します。N(s*)s*
正規表現（パターンとも呼ばれる）は、特定の目的に必要な文字列のセットを指定します。有限個の文字列のセットを指定する簡単な方法は、その要素またはメンバーを列挙することです。ただし、より簡潔な方法もよくあります。たとえば、「Handel」、「Händel」、「Haendel」という 3 つの文字列を含むセットは、パターンで指定できます。このパターンは、3 つの文字列のそれぞれに一致するH(ä|ae?)ndelと言います。ただし、同じ文字列のセットに対して正規表現を記述する方法は複数あります。たとえば、この例では、も同じ 3 つの文字列のセットを指定します。(Hän|Han|Haen)del
ほとんどの形式体系では、正規表現を構築するために以下の操作が提供されています。
gray|greygray|greyと はどちらも「gray」または「grey」の集合を表す同等のパターンです。gr(a|e)y?*+.任意の文字に一致します。たとえば、 a.b「a」、任意の文字、そして「b」を含む文字列に一致します。a.*b「a」という文字を含み、その後に「b」という文字が続く文字列に一致します。これらの構成要素を組み合わせることで、任意に複雑な式を形成することができる。これは、数と演算（+、−、×、÷）から算術式を構成できるのとよく似ている。
正規表現は、形式言語理論における正規言語を記述するものです。正規表現は正規文法と同じ表現力を持っています。しかし、正規表現自体の言語は文脈自由言語です。
正規表現は、文字列の集合を表す定数と、これらの集合に対する演算を表す演算子記号から構成されます。以下の定義は標準的なものであり、形式言語理論に関するほとんどの教科書に記載されています。[ 24 ] [ 25 ]有限アルファベットΣが与えられた場合、以下の定数は正規表現として定義されます。
正規表現RとSが与えられたとき、正規表現を生成するために、それらに対して以下の演算が定義されます。
(RS)は、R が受け入れる文字列と S が受け入れる文字列を（この順序で）連結することによって得られる文字列の集合を表します。たとえば、R を {"ab", "c"}、S を {"d", "ef"} とします。すると、 は(RS){"abd", "abef", "cd", "cef"} を表します。(R|S)を表します。たとえば、Rが{"ab", "c"}を記述し、Sが{"ab", "d", "ef"}を記述する場合、式は{"ab", "c", "d", "ef"}を記述します。(R|S)(R*)最小のスーパーセットで、ε を含み、文字列連結に関して閉じているものを表します。これは、R で記述される集合から任意の有限個 (0 個を含む) の文字列を連結して作成できるすべての文字列の集合です。たとえば、R が {"0", "1"} を表す場合、はすべての有限バイナリ文字列(空文字列を含む) の集合を表します。R が {"ab", "c"} を表す場合、は {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "abcab", ...} を表します。(R*)(R*)括弧を避けるため、クリーネスターが最も優先順位が高く、次に連結、最後に交替の順であると仮定します。曖昧さがない場合は、括弧を省略できます。たとえば、(ab)cは と書くことができabc、a|(b(c*))は と書くことができますa|bc*。多くの教科書では、交替を表す記号として縦棒の代わりに ∪、+、または ∨ を使用しています。
例：
a|b*は {ε, "a", "b", "bb", "bbb", ...} を表す。(a|b)*は、空文字列を含め、「a」と「b」以外の記号を含まないすべての文字列の集合を表します: {ε, "a", "b", "aa", "ab", "ba", "bb", "aaa", ...}ab*(c|ε)は、「a」で始まり、0 個以上の「b」が続き、最後にオプションで「c」が続く文字列の集合を表します。{"a", "ac", "ab", "abc", "abb", "abbc", ...}(0|(1(01*0)*1))*は、3の倍数である2進数の集合を表します: { ε, "0", "00", "11", "000", "011", "110", "0000", "0011", "0110", "1001", "1100", "1111", "00000", ...}正規表現の導関数は、ブジョゾフスキー導関数を用いて定義できます。
正規表現の正式な定義は意図的に最小限に抑えられており、?およびの定義は避けられています+。これらは次のように表現できます。a+= aa*、およびa?= (a|ε)。 時には、補演算子が追加され、一般化された正規表現が得られます。ここで、R c は、 Rに一致しない Σ* 上のすべての文字列に一致します。 原則として、補演算子は冗長です。なぜなら、それ以上の表現力は得られないからです。 しかし、正規表現をはるかに簡潔にすることができます。1 つの補演算子を削除すると、長さが2 倍の指数関数的な増加を引き起こす可能性があります。[ 26 ] [ 27 ] [ 28 ]
この意味での正規表現は、決定性有限オートマトンが受け入れる言語のクラスである正規言語を表現できます。ただし、コンパクトさには大きな違いがあります。正規言語のクラスの中には、最短の同等の正規表現のサイズに対してサイズが指数関数的に増加する決定性有限オートマトンによってのみ記述できるものがあります。ここでの標準的な例は、アルファベット { a , b }上のすべての文字列のうち、最後から k 番目の文字がaであるものからなる言語 L kです。一方、L 4を記述する正規表現は次のように与えられます。 。
このパターンをL kに一般化すると、次の式が得られます。
一方、言語L kを受理するすべての決定性有限オートマトンには、少なくとも 2 k個の状態が必要であることが知られています。幸いなことに、正規表現からより一般的な非決定性有限オートマトン(NFA) への単純なマッピングがあり、そのようなサイズの爆発的な増加にはつながりません。このため、NFA は正規言語の代替表現としてよく使用されます。NFA は、チョムスキー階層のタイプ 3文法の単純な変形です。[ 24 ]
反対に、DFAで簡単に記述できる言語でも、正規表現では簡単に記述できない言語が多数存在する。例えば、与えられたISBNの有効性を判定するには、整数を11で割った余りを計算する必要があり、11状態のDFAで簡単に実装できる。しかし、これを正規表現に変換すると、2.14メガバイトのファイルになってしまう。[ 29 ]
正規表現が与えられると、トンプソンの構成アルゴリズムは同等の非決定性有限オートマトンを計算する。逆方向の変換はクリーネのアルゴリズムによって実現される。
最後に、実際の多くの「正規表現」エンジンは、形式言語理論の意味での正規表現では記述できない機能を実装しています。むしろ、正規表現を実装しているのです。これについては後述します。
上記の多くの例に見られるように、同じ結果を得るための正規表現の構築方法は複数存在する。
与えられた2つの正規表現に対して、記述された言語が等しいかどうかを判定するアルゴリズムを作成することが可能です。このアルゴリズムは、各正規表現を最小限の決定論的有限状態機械に還元し、それらが同型（同等）であるかどうかを判定します。
Algebraic laws for regular expressions can be obtained using a method by Gischer which is best explained along an example: In order to check whether (X+Y)∗ and (X∗Y∗)∗ denote the same regular language, for all regular expressions X, Y, it is necessary and sufficient to check whether the particular regular expressions (a+b)∗ and (a∗b∗)∗ denote the same language over the alphabet Σ={a,b}. More generally, an equation E=F between regular-expression terms with variables holds if, and only if, its instantiation with different variables replaced by different symbol constants holds.[30][31]
Every regular expression can be written solely in terms of the Kleene star and set unions over finite words. This is a surprisingly difficult problem. As simple as the regular expressions are, there is no method to systematically rewrite them to some normal form. The lack of axiom in the past led to the star height problem. In 1991, Dexter Kozen axiomatized regular expressions as a Kleene algebra, using equational and Horn clause axioms.[32] Already in 1964, Redko had proved that no finite set of purely equational axioms can characterize the algebra of regular languages.[33]
正規表現パターンは、ターゲット文字列に一致します。パターンは、アトムのシーケンスで構成されます。アトムは、正規表現パターン内の単一のポイントであり、ターゲット文字列に一致させようとします。最も単純なアトムはリテラルですが、パターンの一部をグループ化してアトムに一致させるには、メタ文字を使用する必要があります。メタ文字は、アトム、アトムの数（および貪欲な量指定子かどうか）を示す量指定子、選択肢のセットを提供する論理OR文字、アトムの存在を否定する論理NOT文字、およびアトムのパターンを完成させる前のアトムを参照する後方参照の形成に役立ちます。一致は、文字列のすべてのアトムが一致したときではなく、正規表現内のすべてのパターンアトムが一致したときに行われます。このアイデアは、すべてのリテラルの可能性の大きなリストを作成するのではなく、小さな文字パターンで多数の可能な文字列を表すようにすることです。( )
正規表現プロセッサによって、メタ文字は約 14 種類あります。メタ文字は、文脈や「エスケープ」されているかどうか、つまりエスケープシーケンス(この場合はバックスラッシュ) が前に付いているかどうかによって、文字の文字通りの意味を持つ場合と持たない場合があります。 最新の正規表現や POSIX 拡張正規表現では、文字の文字通りの意味よりもメタ文字を頻繁に使用するため、「バックスラッシュ症候群」や「傾いたつまようじ症候群」を避けるために、メタ文字を文字の文字通りのモードにエスケープする機能があります。 ただし、最初は、4 つの角括弧メタ文字とが主に文字として使用され、この通常の意味を「エスケープ」してメタ文字になります。 一般的な標準では、両方が実装されています。 通常のメタ文字はとです。 エスケープされるとメタ文字になる通常の文字はとです。\( ){ } {}[]()^$.|*+?\dswDSWN
プログラミング言語で正規表現を入力する場合、通常の文字列リテラルとして表現されることが多く、そのため通常は引用符で囲まれます。これは、たとえば C、Java、Python でよく見られる方法で、正規表現はreのように入力します"re"。ただし、正規表現 のように、区切り文字としてスラッシュを使用して記述されることもよくあります。これはedに由来し、は検索用のエディタ コマンドで、式を使用して行の範囲 (パターンに一致する) を指定できます。この式は、両側の他のコマンドと組み合わせることができ、最も有名なのはgrep ("global regex print")で、 LinuxディストリビューションなどのほとんどのUnixベースのオペレーティングシステムに含まれています。同様の慣習はsedでも使用されており、検索と置換は で指定され、パターンはカンマで結合して行の範囲を指定できます。この表記法は、通常の文字列リテラルとは異なる構文の一部を形成するPerlでの使用により特に有名です。 sedやPerlなどの一部のツールでは、コンテンツとの衝突を回避したり、コンテンツ内の区切り文字をエスケープする必要をなくすために、代替の区切り文字を使用できます。たとえば、sedでは、コマンドはカンマを区切り文字として使用して、aをanに置き換えます。/re/re//re/g/re/ps/re/replacement//re1/,/re2/s,/,X,/X
IEEE POSIX標準には、BRE (基本正規表現)、[ 34 ] ERE (拡張正規表現)、およびSRE (単純正規表現)の 3 つの準拠セットがあります。SREは、後方互換性を提供する BRE に置き換えられ、非推奨となっています[ 35 ] 。文字クラスを扱う以下のサブセクションは、 BRE と ERE の両方に適用されます。
BRE と ERE は連携して動作します。ERE は?、、、+およびを追加し、BRE で必要なメタ文字とを|エスケープする必要をなくします。さらに、正規表現の POSIX 標準構文が遵守されている限り、特定の (ただし POSIX 準拠の) アプリケーションに対応するための追加の構文が存在する可能性があり、実際によく存在します。POSIX.2 では実装の詳細が定義されていない部分がありますが、BRE と ERE は、その後多くのツールのデフォルト構文として採用された「標準」を提供しており、BRE モードまたは ERE モードの選択は通常サポートされているオプションです。たとえば、GNU には次のオプションがあります。「」は ERE 用、「」は BRE (デフォルト) 用、「」はPerl正規表現用です。( ){ }grepgrep -Egrep -Ggrep -P
Perl の正規表現は、豊富で強力な基本式セットを備え、事実上の標準となっています。Perl には「基本」レベルや「拡張」レベルはありません。POSIX ERE と同様に、エスケープされない限りメタ文字として扱われます。その他のメタ文字は、文脈のみに基づいてリテラルかシンボルかがわかります。追加機能には、遅延マッチング、後方参照、名前付きキャプチャグループ、再帰パターンなどがあります。( ){ }
POSIX標準では、基本正規構文 ( BRE )ではメタ文字 とを と指定する必要がありますが、拡張正規構文 ( ERE ) ではそうではありません。( ){ }\(\)\{\}
例：
.at「at」で終わる任意の3文字の文字列に一致します。これには、「hat」、「cat」、「bat」、「4at」、「#at」、および「at」（スペースで始まる）が含まれます。[hc]at「帽子」と「猫」に一致する。[^b]at.at「bat」を除く、に一致するすべての文字列に一致します。[^hc]at.at「hat」と「cat」以外の文字列すべてに一致します。^[hc]at「hat」と「cat」に一致しますが、文字列または行の先頭でのみ一致します。[hc]at$「hat」と「cat」に一致しますが、文字列または行の末尾でのみ一致します。\[.\]角括弧がエスケープされるため、 "[" と "]" で囲まれた任意の単一文字に一致します。たとえば、 "[a]", "[b]", "[7]", "[@]", "[]]", および "[ ]" (角括弧スペース角括弧) などです。s.*s の後に 0 文字以上続く文字列に一致します。例: "s", "saw", "seed", "s3w96.7", "s6#h%(>>>mn mQ)。Russ Cox によると、POSIX 仕様では曖昧な部分式を Perl とは異なる方法で処理する必要があるとのことです。委員会は Perl のルールを、説明しやすいルールに置き換えましたが、新しい「シンプルな」ルールは実際には実装がより複雑です。既存のツールと互換性がなく、「遅延マッチ」（後述）拡張機能を定義することが事実上不可能になりました。その結果、POSIX の部分式ルールを実際に実装しているプログラムはごくわずかです（POSIX 構文の他の部分を実装している場合でも）。[ 37 ]
POSIX拡張正規表現（ERE ）構文では、バックスラッシュでエスケープされたメタ文字の意味が一部の文字で反転します。この構文では、バックスラッシュによってメタ文字がリテラル文字として扱われます。したがって、たとえば、は となり、は となります。さらに、後方参照のサポートが削除され、次のメタ文字が追加されます。\( \)( )\{ \}{ }\n
例：
[hc]?at「at」、「hat」、「cat」に一致します。[hc]*at「at」、「hat」、「cat」、「hhat」、「chat」、「hcat」、「cchchat」などに一致します。[hc]+at「hat」、「cat」、「hhat」、「chat」、「hcat」、「cchchat」などには一致しますが、「at」には一致しません。cat|dog「猫」または「犬」に一致する。POSIX 拡張正規表現は、コマンドラインフラグ-Eを含めることで、最新の Unix ユーティリティで使用できることがよくあります。
文字クラスは、リテラルマッチに次いで最も基本的な正規表現の概念です。文字クラスを使うと、短い文字シーケンスがより大きな文字セットにマッチします。たとえば、 は[A-Z]英語のアルファベットの大文字を表し、 は任意の数字を表すことができます。文字クラスは、POSIX のどちらのレベルにも適用されます。\d
文字範囲[a-Z]（小文字aから大文字などZ）を指定する場合、コンピュータのロケール設定は文字エンコーディングの数値順序によって内容を決定します。ロケール設定では、その順序で数字が格納される場合もあれば、abc...zABC...Z、またはaAbBcC...zZ の順序になる場合もあります。そのため、POSIX 標準では文字クラスが定義されており、これはインストールされている正規表現プロセッサによって認識されます。これらの定義は次の表に示されています。
POSIX文字クラスは、角括弧式の中でのみ使用できます。たとえば、大文字のアルファベットと小文字の「a」と「b」に一致します。[[:upper:]ab]
一部のツールが理解する追加の非 POSIX クラスは で[:word:]、通常は[:alnum:]プラス アンダースコアとして定義されます。これは、多くのプログラミング言語で、これらが識別子に使用できる文字であるという事実を反映しています。エディタVim は、多くのプログラミング言語で識別子の開始に使用できる文字が他の位置に出現できる文字と同じではないため、単語クラスと単語ヘッドクラスをさらに区別します(表記法とを使用)。数字は一般的に除外されるため、識別子はPOSIX 表記法ではまたはのようになります。\w\h\h\w*[[:alpha:]_][[:alnum:]_]*
POSIX正規表現規格で文字クラスと呼ばれるものは、それをサポートする他の正規表現でも一般的にPOSIX文字クラスと呼ばれていることに注意してください。他のほとんどの正規表現では、文字クラスという用語は、POSIXで括弧式と呼ばれるものを説明するために使用されます。
Perlの表現力と（比較的）読みやすさから、Java、JavaScript、Julia、Python、Ruby、Qt、Microsoft の.NET Framework、XML Schemaなど、他の多くのユーティリティやプログラミング言語がPerlと同様の構文を採用しています。BoostやPHPなどの言語やツールは、複数の正規表現をサポートしています。Perl派生の正規表現の実装は同一ではなく、通常は 1994 年にリリースされた Perl 5.0 の機能のサブセットを実装しています。Perl は、他の言語で最初に見つかった機能を取り入れることもあります。たとえば、Perl 5.10 は、PCRE と Python で最初に開発された構文拡張を実装しています。[ 38 ]
Python やその他の実装 (Java など) では、3 つの一般的な量指定子 ( *、+、 および?)は、可能な限り多くの文字に一致するため、デフォルトで貪欲になります。 [ 39 ]文字列に適用される正規表現".+"(二重引用符を含む)
「ガニメデは、太陽系で最大の衛星です」と彼は続けた。
は、行全体が二重引用符で始まり、二重引用符で終わるため、最初の部分のみに一致するのではなく、行全体に一致します"Ganymede,"。ただし、前述の量指定子は、疑問符を追加することで、可能な限り少ない文字に一致するように、怠惰または最小限または消極的に".+?"することができます。は のみに一致します"Ganymede,"。[ 39 ]
JavaおよびPython 3.11以降では、[ 40 ]量指定子にプラス記号を付加することで所有格にすることができ、バックトラッキングエンジンではバックオフが無効になります。たとえそうすることで全体のマッチが成功する場合でもです。[ 41 ]".*"文字列に適用された正規表現では
「ガニメデは、太陽系で最大の衛星です」と彼は続けた。
は行全体に一致しますが、正規表現は には全く一致しません".*+"。なぜなら は最後の を含めた入力全体を消費するからです。したがって、所有格量指定子は、否定文字クラス、たとえば で最も役立ちます。これは、同じ文字列に適用すると一致します。.*+""[^"]*+""Ganymede,"
同じ機能を果たすもう 1 つの一般的な拡張機能はアトミック グルーピングで、括弧で囲まれたグループのバックトラッキングを無効にします。典型的な構文は(? > group)です。たとえば、^(wi|w)i$ はwiとwiiの両方に一致しますが、^(? > wi|w)i$ はwiiにのみ一致します。これは、エンジンがバックトラッキングを禁止されているため、「wi」に一致した後にグループを「w」に設定しようとできないためです。[ 42 ]
所有格量化子は、貪欲量化子や怠惰量化子よりも実装が容易で、通常は実行時に効率的です。[ 41 ]
IETF RFC 9485 は「I-Regexp: 相互運用可能な正規表現フォーマット」について説明しています。これは、多数の正規表現ライブラリで相互運用可能、つまり同じ効果を生み出すように設計された正規表現イディオムの限定されたサブセットを規定しています。I-Regexp はまた、マッチング、つまり正規表現と特定のテキストとの間で真または偽のマッチングを提供する機能に限定されています。したがって、キャプチャグループ、先読み、後方参照などの高度な機能は備えていません。[ 43 ]
現代の正規表現ライブラリのほぼすべてに見られる多くの機能は、正規言語を超える表現力を提供します。たとえば、多くの実装では、括弧を使用して部分式をグループ化し、同じ式内で一致する値を呼び出すことができます（後方参照）。これは、とりわけ、パターンが「papa」や「WikiWiki」のような繰り返し単語の文字列にマッチできることを意味します。形式言語理論では、これらの文字列。これらの文字列のパターンは です(.+)\1。
正方形の言語は、ポンピング補題により、正規でもなく、文脈自由でもありません。しかし、多くの最新ツールでサポートされている無制限の数のバックリファレンスを使用したパターンマッチングは、依然として文脈依存です。[ 44 ]任意の数のバックリファレンスをマッチングする一般的な問題はNP完全であり、既知のアルゴリズムの実行時間は、使用されるバックリファレンスグループの数によって指数関数的に増加します。[ 45 ]
しかし、このような構造を提供する多くのツール、ライブラリ、エンジンは、依然としてパターンに対して「正規表現」という用語を使用しています。このため、形式言語理論とパターンマッチングにおいて、「正規表現」という用語が異なる意味を持つという命名法が生じています。このため、後者を説明する際に、 regex、regexp、あるいは単にpatternという用語を使用する人もいます。Perlプログラミング言語の作者であるラリー・ウォールは、Rakuの設計に関するエッセイの中で次のように述べています。
「正規表現」は、実際の正規表現とはほとんど関係がありません。とはいえ、この用語はパターンマッチングエンジンの機能の発達とともに広まったので、ここでは言語的な必然性に逆らおうとは思いません。しかし、一般的には「regexs」（または、アングロサクソン風に言うと「regexen」）と呼ぶことにします。[ 19 ]
正規言語の記述には見られないその他の機能としてアサーションがあります。これには、少なくとも 1970 年以来使用されている遍在の および が含まれます^[ $46 ]。また、1994 年に登場したルックアラウンドなどのより高度な拡張機能もあります[ 47 ]。ルックアラウンドはマッチの周囲を定義し、マッチ自体には影響しません。この機能は、文字列検索のユースケースにのみ関連します。これらのいくつかは、周囲も言語の一部として扱うことで、正規言語でシミュレートできます[ 48 ] 。
の先読みアサーション(?=...)と は、(?!...)Perl 5 から始まる少なくとも 1994 年以降に証明されています。 [ 47 ]後読みアサーション(?<=...)と は、(?<!...)Ilya Zakharevich による Perl 5.005 へのコミットで 1997 年以降に証明されています。 [ 49 ]
与えられた正規表現が文字列に一致するかどうか、またどのように一致するかを決定するアルゴリズムは、少なくとも3種類存在する。
最も古く、最も高速な方法は、形式言語理論における、すべての非決定性有限オートマトン（NFA）を決定性有限オートマトン（DFA）に変換できるという結果に基づいています。DFAは明示的に構築でき、その後、結果として得られる入力文字列に対して1文字ずつ実行できます。サイズmの正規表現に対するDFAの構築には、時間とメモリのコストがO (2m )かかりますが、サイズnの文字列に対してはO ( n )の時間で実行できます。式のサイズは、数値量指定子などの省略形が展開された後のサイズであることに注意してください。
別のアプローチとしては、NFA を直接シミュレートし、基本的に各 DFA 状態をオンデマンドで構築し、次のステップで破棄する方法があります。この方法では DFA は暗黙的に保持され、指数関数的な構築コストは回避されますが、実行コストはO ( mn ) に上昇します。明示的なアプローチは DFA アルゴリズムと呼ばれ、暗黙的なアプローチは NFA アルゴリズムと呼ばれます。NFA アルゴリズムにキャッシュを追加すると、「遅延 DFA」アルゴリズム、または区別せずに単に DFA アルゴリズムと呼ばれることがよくあります。これらのアルゴリズムは高速ですが、グループ化された部分式の呼び出し、遅延量化、および同様の機能に使用するのは困難です。[ 50 ] [ 51 ]最新の実装には、 Cox のコードに基づくre1- re2 -sregex ファミリーが含まれます。
3つ目のアルゴリズムは、バックトラッキングによってパターンを入力文字列と照合するものです。このアルゴリズムは一般的にNFAと呼ばれますが、この用語は紛らわしい場合があります。実行時間は指数関数的に増加する可能性があり、単純な実装では、選択と無制限の量化の両方を含む式と照合する場合に、アルゴリズムが指数関数的に増加するサブケースを考慮する必要が生じます。この動作は、正規表現サービス拒否攻撃（ReDoS）と呼ばれるセキュリティ上の問題を引き起こす可能性があります。(a|aa)*b
バックトラッキングの実装は最悪の場合指数関数的な保証しか提供しませんが、はるかに高い柔軟性と表現力を提供します。たとえば、バックリファレンスの使用を許可する実装、または Perl によって導入されたさまざまな拡張機能を実装する実装には、何らかのバックトラッキングが含まれている必要があります。一部の実装では、まず高速な DFA アルゴリズムを実行し、マッチ中にバックリファレンスが見つかった場合にのみ、潜在的に遅いバックトラッキング アルゴリズムに戻ることで、両方のアルゴリズムの最良の部分を提供しようとします。GNU grep (および基盤となる gnulib DFA) は、このような戦略を使用しています。[ 52 ]
サブリニア実行時間アルゴリズムは、Boyer-Moore (BM) ベースのアルゴリズムと、逆スキャンなどの関連する DFA 最適化技術を使用して実現されています。[ 53 ]多種多様な POSIX 構文と拡張機能をサポートする GNU grep は、最初のパスの事前フィルタリングに BM を使用し、その後暗黙の DFA を使用します。近似マッチングを実装する Wu agrepは、BDM (後方 DAWG マッチング) で事前フィルタリングを DFA に組み合わせます。NR-grep の BNDM は、BDM 技術を Shift-Or ビットレベル並列性で拡張します。[ 54 ]
バック参照に対するバックトラッキングの理論的な代替手段はいくつか存在し、それらの「指数」はバック参照の数のみに関係するため、より穏やかです。バック参照数は、POSIXなどの一部の正規表現言語の固定プロパティです。バック参照ノートごとに非バックトラッキングNFAを複製する単純な方法の複雑さは時間と長さ n の干し草の山と正規表現内の k 個のバックリファレンスのためのスペース。 [ 55 ]メモリオートマタに基づく理論的研究では、「アクティブ」変数ノードの使用に基づくより厳密な境界と、一部のバックリファレンス正規表現に対する多項式の可能性が示されています。 [ 56 ]
理論的には、トークンセットが事前に定義されていれば、どんなトークンセットでも正規表現でマッチさせることができます。歴史的な実装に関して言えば、正規表現は当初、トークンセットとしてASCII文字を使用するように記述されていましたが、正規表現ライブラリは他の多くの文字セットもサポートしてきました。多くの最新の正規表現エンジンは、少なくともUnicodeをある程度サポートしています。ほとんどの場合、文字セットが何であるかは関係ありませんが、正規表現を拡張してUnicodeをサポートする際には、いくつかの問題が発生します。
[x-y]限り、次の形式の文字範囲が有効です。このような文字範囲を Unicode に自然に拡張すると、端点が [0x00,0x7F] 内にあるという要件を、[0x0000,0x10FFFF] 内にあるという要件に変更するだけです。ただし、実際にはそうでない場合がよくあります。gawk などの一部の実装では、文字範囲が Unicode ブロックをまたぐことを許可していません。 [0x61,0x7F] のような範囲は、両端が Basic Latin ブロック内に含まれるため有効です。同様に、[0x0530,0x0560] のような範囲も、両端が Armenian ブロック内に含まれるため有効ですが、[0x0061,0x0532] のような範囲は、複数の Unicode ブロックを含むため無効です。Vim エディタなどの他のエンジンではブロックをまたぐことができますが、文字値の差は 256 以上であってはなりません。[ 57 ]java.util.regexの形式のプロパティはブロックX内の文字に一致し、またははそのブロックに含まれないコード ポイントに一致します。同様に、、、またはは、アルメニア語スクリプトの任意の文字に一致します。一般に、は、バイナリ プロパティXまたは一般カテゴリXのいずれかを持つ任意の文字に一致します。たとえば、、、またはは、任意の大文字に一致します。一般カテゴリではないバイナリ プロパティには、、、、およびが含まれます。バイナリではないプロパティの例は、、、およびです。\p{InX}\p{Block=X}\P{InX}\P{Block=X}\p{Armenian}\p{IsArmenian}\p{Script=Armenian}\p{X}\p{Lu}\p{Uppercase_Letter}\p{GC=Lu}\p{White_Space}\p{Alphabetic}\p{Math}\p{Dash}\p{Bidi_Class=Right_to_Left}\p{Word_Break=A_Letter}\p{Numeric_Value=10}ほとんどの汎用プログラミング言語は、ネイティブに、またはライブラリを介して、正規表現機能をサポートしています。
正規表現は、さまざまなテキスト処理タスク、そしてより一般的には、データがテキスト形式である必要のない文字列処理において役立ちます。一般的な用途としては、データ検証、データスクレイピング（特にWebスクレイピング）、データラングリング、単純な構文解析、構文強調表示システムの作成など、その他多くのタスクが挙げられます。
一部のハイエンドデスクトップパブリッシングソフトウェアには、正規表現を使用してテキストのスタイルを自動的に適用する機能があり、レイアウト担当者が正規表現に一致するものに対して手作業でスタイルを適用する手間を省くことができます。たとえば、テキストをスモールキャップスに変換する文字スタイルを定義し、そのスタイルを正規表現で適用することで、4文字以上の連続する大文字の単語はすべて自動的にスモールキャップスとして表示されます。[A-Z]{4,}
正規表現はインターネット検索エンジンでは有用ですが、正規表現の複雑さや設計によっては、データベース全体で正規表現を処理すると過剰なコンピュータリソースを消費する可能性があります。多くの場合、システム管理者は内部で正規表現ベースのクエリを実行できますが、ほとんどの検索エンジンは一般向けに正規表現のサポートを提供していません。注目すべき例外としては、Google Code SearchとExaleadがあります。ただし、Google Code Search は 2012 年 1 月にサービスを終了しました。[ 59 ]
具体的な構文規則は、使用する実装、プログラミング言語、ライブラリによって異なります。さらに、正規表現の実装機能はバージョンによって異なる場合があります。
正規表現は例がないと説明も理解も難しいため、正規表現をテストできるインタラクティブなウェブサイトは、実験を通して正規表現を学ぶ上で便利なリソースとなります。このセクションでは、例を用いて正規表現のいくつかの特性について基本的な説明を行います。
以下の表記法が例で使用されています。[ 60 ]
メタ文字 ;; メタ文字列は、デモンストレーションされている正規表現構文を指定します =~ m// ;; はPerl における正規表現のマッチ操作を示します =~ s/// ;; はPerl における正規表現置換操作を示します
これらの正規表現はすべてPerlライクな構文です。標準的なPOSIX正規表現は異なります。
特に明記されていない限り、以下の例はPerlプログラミング言語、リリース 5.8.8、2006 年 1 月 31 日に準拠しています。つまり、他の実装では、ここに示されている構文の一部がサポートされていない可能性があります (たとえば、基本正規表現と拡張正規表現、\( \)またはの代わりに()がないPOSIX\dなど)。[:digit:]
これらの例で使用されている構文と規則は、他のプログラミング環境のものと一致する。[ 61 ]
正規表現は、一連の例文字列に基づいて作成（「誘導」または「学習」）できる場合が多い。これは正規言語の誘導として知られており、計算学習理論における文法誘導という一般的な問題の一部である。形式的には、正規言語の文字列の例、場合によってはその正規言語に含まれない文字列の例も与えられれば、その言語の文法、つまりその言語を生成する正規表現を誘導することができる。すべての正規言語がこのように誘導できるわけではないが（極限における言語識別を参照）、多くは誘導できる。例えば、例の集合 {1, 10, 100} と否定集合（反例） {11, 1001, 101, 0} を使用して、正規表現 1⋅0* (1 の後に 0 が 0 個以上続く) を誘導することができる。
正規イベントの概念は、Kleeneが正規表現の定義を通して導入した。
この性質は、正規表現が正規言語よりも大きなクラスを記述しない場合でも、拡張正規表現には必ずしも当てはまらない。121ページ参照。
余談：POSIXサブマッチング
スキャナがバックリファレンスで遷移を検出すると、バックトラッキングマッチャーで一致を検証する必要があることを示す一種の「準成功」を返します。
m/[^abc]//[^abc]/
ウィキメディア・コモンズにある正規表現関連のメディア