正規表現

正規表現（regexまたはregexpと略される） [ 1 ]は、^有理式^{[2] [3]}とも呼ばれ、テキスト内の一致パターンを指定する文字列です。通常、このようなパターンは、文字列に対する「検索」または「検索と置換」操作、または入力検証のための文字列検索アルゴリズムによって使用されます。正規表現の技術は、理論計算機科学と形式言語理論 で開発されました。

正規表現の概念は、アメリカの数学者スティーブン・コール・クリーネが正規言語の概念を形式化した1950 年代に始まりました。正規表現は、 Unixテキスト処理ユーティリティで一般的に使用されるようになりました。正規表現を記述するためのさまざまな構文は1980 年代から存在しており、1 つはPOSIX標準で、もう 1 つは広く使用されているPerl構文です。

正規表現は、検索エンジン、ワードプロセッサやテキストエディタの検索および置換ダイアログ、sedやAWKなどのテキスト処理ユーティリティ、および字句解析で使用されます。正規表現は多くのプログラミング言語でサポートされています。ライブラリの実装は「エンジン」と呼ばれることが多く、^{[4] [5]}、その多くは再利用できます。

正規表現は1951年に数学者スティーブン・コール・クリーネが正規イベントと呼ばれる数学的記法を使って正規言語を記述したときに始まりました。^{[6] [7]}これらは理論計算機科学のオートマトン理論（計算モデル）のサブフィールドと形式言語の記述と分類で生まれ、クリーネが初期の人工ニューラルネットワークを記述しようとした試みに触発されました。（クリーネはマカロックとピッツの「把握可能」に代わるものとしてこれを導入しましたが、「より説明的な用語についての提案を歓迎します」と認めました。^{[8] ）}パターンマッチングの他の初期の実装には、正規表現を使用せず、代わりに独自のパターンマッチング構造を使用する SNOBOL言語が含まれます。

正規表現は、1968年から、テキストエディタでのパターンマッチング^[9]とコンパイラでの字句解析^[10]の2つの用途で広く使われるようになりました。プログラム形式での正規表現の最初の登場は、ケン・トンプソンがテキストファイル内のパターンをマッチングする手段としてクリーネ記法をエディタQEDに組み込んだときでした。^{[9] [11] [12] [13]速度を上げるため、トンプソンは}互換タイムシェアリングシステム上のIBM 7094コードにジャストインタイムコンパイル(JIT)による正規表現マッチングを実装しました。これは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)が書いた正規表現ライブラリから派生したもので、Spencerは後に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要素グループ構文に明らかです。正規表現が使用される前は、多くの検索言語で単純なワイルドカードが許可されていました。たとえば、"*" は任意の文字シーケンスに一致し、"?" は 1 つの文字に一致します。この名残は、今日、ファイル名のglob構文やSQL LIKE演算子に見られます。

1997年から、フィリップ・ヘイゼルはPCRE （Perl互換正規表現）を開発しました。これはPerlの正規表現の機能を厳密に模倣したもので、PHPやApache HTTP Serverを含む多くの最新ツールで使用されています。^[20]

今日、正規表現はプログラミング言語、テキスト処理プログラム（特に字句解析プログラム）、高度なテキストエディタ、その他のプログラムで広くサポートされています。正規表現のサポートは、 JavaやPythonを含む多くのプログラミング言語の標準ライブラリの一部であり、PerlやECMAScriptを含む他の言語の構文に組み込まれています。2010年代後半には、 CPU実装に比べて高速なPCRE互換正規表現エンジンのハードウェア、 FPGA ^[21]、^[22] GPU実装をいくつかの企業が提供し始めました。

正規表現（regex ）という用語は、以下で説明する数学的表記法とは異なり、テキストを一致させるためのパターンを表す特定の標準テキスト構文を意味する場合によく使用されます。正規表現内の各文字（つまり、パターンを記述する文字列内の各文字）は、特別な意味を持つメタ文字か、リテラルな意味を持つ通常の文字のいずれかです。たとえば、 regex ではb.、「b」は「b」だけに一致するリテラル文字ですが、「.」は改行を除くすべての文字に一致するメタ文字です。したがって、この regex は、「b%」、「bx」、「b5」などに一致します。メタ文字とリテラル文字を一緒に使用すると、特定のパターンのテキストを識別したり、そのパターンのインスタンスの数を処理したりすることができます。パターンの一致は、メタ文字によって制御され、正確な等価性から非常に一般的な類似性までさまざまです。たとえば、.は非常に一般的なパターンです[a-z]('a' から 'z' までのすべての小文字に一致)。 はそれほど一般的ではなく、は正確なパターンです ('b' だけに一致)。 メタ文字構文は、標準のASCIIキーボードbを使用して簡単に入力できる形式で、さまざまな入力データのテキスト処理の自動化を指示するために、規定されたターゲットを簡潔かつ柔軟な方法で表すように特別に設計されています。

この構文の正規表現の非常に単純な例は、テキスト エディターで 2 つの異なる綴りの単語を検索することです。この場合、正規表現は"serialise" と "serialize" の両方に一致します。ワイルドカード文字でもこれを実現できますが、メタ文字が少なく言語ベースが単純なため、パターン化できる内容がより制限されます。 seriali[sz]e

ワイルドカード文字の通常のコンテキストは、ファイルのリスト内の類似した名前をグロブすることですが、正規表現は通常、テキスト文字列全般をパターン マッチするアプリケーションで使用されます。たとえば、正規表現は行の先頭または末尾の余分な空白と一致します。任意の数字と一致する高度な正規表現は です。 ^[ \t]+|[ \t]+$[+-]?(\d+(\.\d*)?|\.\d+)([eE][+-]?\d+)?

正規表現プロセッサは、上記の構文の正規表現を、実行して検索対象のテキストを表す文字列と照合できる内部表現に変換します。 考えられる 1 つの方法は、トンプソンの構築アルゴリズムを使用して非決定性有限オートマトン(NFA)を構築することです。その後、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」または「grey」に一致できます。gray|grey

グループ化

括弧は、演算子のスコープと優先順位を定義するために使用されます(他の用途もあります)。たとえば、gray|greyと は、どちらも「gray」または「grey」のセットを表す同等のパターンです。gr(a|e)y

定量化

要素 (トークン、文字、グループなど) の後の数量詞は、先行する要素を何回繰り返すことができるかを指定します。最も一般的な数量詞は、疑問符、アスタリスク(クリーネの星から派生)、およびプラス記号(クリーネのプラス) です。 ? * +

ワイルドカード

ワイルドカードは.任意の文字と一致します。たとえば、

a.b「a」、任意の文字、そして「b」を含む文字列と一致します。

a.*b「a」を含み、その後に文字「b」が含まれる文字列と一致します。

これらの構造は、数字と演算 +、-、×、÷ から算術式を構築するのと同じように、組み合わせて任意の複雑な式を形成できます。

正規表現の正確な構文はツールやコンテキストによって異なります。詳細については、§ 構文を参照してください。

正規表現は形式言語理論における正規言語を記述するものであり、正規文法と同じ表現力を持っています。

正規表現は、文字列の集合を表す定数と、これらの集合に対する演算を表す演算子記号から構成されます。次の定義は標準的なもので、形式言語理論のほとんどの教科書に載っています。^{[24] [25]}有限のアルファベットΣが与えられた場合、次の定数が正規表現として定義されます。

• (空集合) ∅ は集合 ∅ を表します。
• (空の文字列) ε は、文字がまったく含まれていない「空の」文字列のみを含むセットを表します。
• Σ 内の(リテラル文字)は、文字aaのみを含む集合を表します。

正規表現 R と S が与えられた場合、正規表現を生成するためにそれらに対する次の演算が定義されます。

• (連結)(RS)は、R が受け入れる文字列と S が受け入れる文字列を (この順序で) 連結することによって得られる文字列のセットを表します。たとえば、R が {"ab", "c"} を表し、S が {"d", "ef"} を表すとします。この場合、は(RS){"abd", "abef", "cd", "cef"} を表します。
• (交替)は、RとSによって記述される集合の和集合(R|S)を表します。たとえば、Rが{"ab", "c"}を記述し、Sが{"ab", "d", "ef"}を記述する場合、式は{"ab", "c", "d", "ef"}を記述します。(R|S)
• (クリーネスター) は、 Rによって記述される集合のうち、ε を含み、文字列連結に関して閉じている(R*)最小のスーパーセットを表します。これは、R によって記述される集合から任意の有限数 (ゼロを含む) の文字列を連結することによって作成できるすべての文字列の集合です。たとえば、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」、... }

正規表現の正式な定義は意図的に最小限に抑えられており、?との定義は避けられています。これらは、 = 、=と+表現できます。補数演算子が追加され、一般化された正規表現になることもあります。ここで、R ^{c は、} Rに一致しない Σ* 以上のすべての文字列に一致します。原理的には、補数演算子は冗長です。なぜなら、それ以上の表現力を与えないからです。しかし、補数演算子を使用すると、正規表現をはるかに簡潔にすることができます。補数演算子を 1 つ削除すると、長さが2 倍の指数関数的に増大する可能性があります。^{[26] [27] [28]}a+aa*a?(a|ε)

この意味での正規表現は、正規言語、つまり決定性有限オートマトンが受け入れる言語のクラスを表現することができます。しかし、コンパクトさには大きな違いがあります。正規言語のいくつかのクラスは、最短の同等の正規表現のサイズに対して 指数関数的にサイズが大きくなる決定性有限オートマトンでのみ表現できます。ここでの標準的な例は、アルファベット { a , b }上のすべての文字列から成り、最後から k番目の文字がaに等しい言語L _kです。一方、L _{4 を}表現する正規表現はによって与えられます 。 ${\displaystyle (a\mid b)^{*}a(a\mid b)(a\mid b)(a\mid b)}$

このパターンをL _kに一般化すると、次の式が得られます。

${\displaystyle (a\mid b)^{*}a\underbrace {(a\mid b)(a\mid b)\cdots (a\mid b)} _{k-1{\text{ 回}}}.\,}$

一方、言語L _kを受け入れるすべての決定性有限オートマトンには、少なくとも2 ^{k の}状態が必要であることが知られています。幸いなことに、正規表現からより一般的な非決定性有限オートマトン（NFA）への単純なマッピングがあり、これはサイズの爆発にはつながりません。このため、NFAは正規言語の代替表現としてよく使用されます。NFAは、チョムスキー階層のタイプ3文法の単純なバリエーションです。^[24]

逆に、DFAで簡単に記述できる言語でも、正規表現では簡単に記述できない言語は数多くあります。例えば、特定のISBNの有効性を判断するには、11を底とする整数の係数を計算する必要があり、11状態のDFAで簡単に実装できます。しかし、これを正規表現に変換すると、2.14メガバイトのファイルになります。^[29]

正規表現が与えられると、トンプソンの構築アルゴリズムは同等の非決定性有限オートマトンを計算します。逆方向の変換はクリーネのアルゴリズムによって実現されます。

最後に、現実世界の多くの「正規表現」エンジンは、形式言語理論の意味での正規表現では記述できない機能を実装していることに注意してください。むしろ、それらはregex を実装しています。これについては以下を参照してください。

上記の多くの例に見られるように、同じ結果を達成するための正規表現を構築する方法は複数あります。

与えられた 2 つの正規表現に対して、記述された言語が等しいかどうかを判断するアルゴリズムを記述することができます。このアルゴリズムは、各表現を最小限の決定論的有限状態マシンに縮小し、それらが同型(同等) であるかどうかを判断します。

正規表現の代数法則は、Gischer の方法を使って得ることができ、これは例を挙げて説明するのが最もよい。すべての正規表現X、Yについて、 ( X + Y ) ^*と ( X ^* Y ^* ) ^*が同じ正規言語を表すかどうかを確認するには、特定の正規表現 ( a + b ) ^*と ( a ^* b ^* ) ^*がアルファベット Σ={ a、b } 上で同じ言語を表すかどうかを確認することが必要かつ十分である。より一般的には、変数を含む正規表現項間の方程式E = Fが成立するのは、異なる変数を異なる記号定数に置き換えたインスタンス化が成立する場合のみである。^{[30] [31]}

すべての正規表現は、有限語上のクリーネの星と集合の和集合だけで記述できる。これは驚くほど難しい問題である。正規表現は単純であるが、体系的に何らかの正規形に書き直す方法はない。過去に公理がなかったことが、星の高さ問題につながった。1991年、デクスター・コーゼンは、方程式とホーン節の公理を用いて、正規表現をクリーネ代数として公理化した。^[32] すでに1964年に、レドコは、純粋に方程式の公理の有限集合では正規言語の代数を特徴づけることができないことを証明していた。^[33]

正規表現パターンは、ターゲット文字列と一致します。パターンは、アトムのシーケンスで構成されます。アトムは、ターゲット文字列と一致しようとする正規表現パターン内の単一のポイントです。最も単純なアトムはリテラルですが、パターンの一部をグループ化してアトムと一致させるには、( )メタ文字を使用する必要があります。メタ文字は、アトム、アトムの数を示す量指定子(および貪欲な量指定子であるかどうか)、一連の選択肢を提供する論理 OR 文字、アトムの存在を否定する論理 NOT 文字、およびアトムの完全なパターンの前のアトムを参照するバック参照の形成に役立ちます。文字列のすべてのアトムが一致したときではなく、正規表現のすべてのパターンアトムが一致したときに一致します。この考え方は、すべてのリテラルの可能性の大きなリストをコンパイルするのではなく、小さな文字パターンで多数の可能な文字列を表すようにすることです。

正規表現プロセッサに応じて、約 14 個のメタ文字があります。メタ文字は、コンテキスト、またはエスケープされているかどうか、つまりエスケープシーケンス(この場合はバックスラッシュ) が先行しているかどうかによって、リテラル文字の意味を持つ場合と持たない場合があります。最新の POSIX 拡張正規表現では、リテラルの意味よりもメタ文字を使用することが多いため、「バックスラッシュ症候群」または傾斜つまようじ症候群を回避するために、リテラル モードへのメタ文字エスケープが用意されています。ただし、最初は、代わりに 4 つの括弧付きメタ文字とがあり、主にリテラルであり、この通常の意味を「エスケープ」してメタ文字になります。共通標準では、両方が実装されています。通常のメタ文字はと です。エスケープされるとメタ文字になる通常の文字はと です。 \( ){ } {}[]()^$.|*+?\dswDSWN

プログラミング言語で正規表現を入力する場合、それらは通常の文字列リテラルとして表される場合があり、したがって通常は引用符でre囲まれます。これは、たとえば C、Java、Python で一般的であり、正規表現は と入力されます。ただし、正規表現 の場合のように、それらは多くの場合、区切り"re"文字としてスラッシュを使用して記述されます。これはedに由来します。ここで、 は検索用のエディター コマンドであり、式を使用して行の範囲 (パターンに一致する) を指定できます。これは、両側で他のコマンドと組み合わせることができます。最も有名なのは、Linuxディストリビューションなど、ほとんどのUnixベースのオペレーティング システムに含まれているgrep (「グローバル正規表現プリント」)です。同様の規則がsedでも使用されます。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は非推奨となり、^{[35] BREが推奨されます。}文字クラスをカバーしている以下のサブセクションは、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「hat」、「cat」、「bat」、「4at」、「#at」、「at」（スペースで始まる）など、「at」で終わる任意の 3 文字の文字列に一致します。
• [hc]at「帽子」と「猫」に一致します。
• [^b]at.at「bat」を除く、一致するすべての文字列と一致します。
• [^hc]at.at「hat」と「cat」以外のすべての文字列と一致します。
• ^[hc]at「hat」や「cat」に一致しますが、文字列または行の先頭にのみ一致します。
• [hc]at$「hat」や「cat」に一致しますが、文字列または行の末尾にのみ一致します。
• \[.\]括弧がエスケープされているため、"[" と "]" で囲まれた任意の 1 文字に一致します。例: "[a]"、"[b]"、"[7]"、"[@]"、"[]]"、"[ ]" (括弧 スペース 括弧)。
• s.*s の後に 0 個以上の文字が続くものに一致します。例: "s"、"saw"、"seed"、"s3w96.7"、"s6#h%(>>>mn mQ")。

ロス・コックスによれば、POSIX 仕様では、あいまいな部分式を Perl とは異なる方法で処理する必要がある。委員会は Perl のルールを説明が簡単なものに置き換えたが、新しい「単純な」ルールは実際には実装がより複雑である。既存のツールと互換性がなく、「遅延一致」(以下を参照) 拡張を定義することが実質的に不可能であった。その結果、POSIX 部分式ルールを実際に実装しているプログラムはほとんどない (POSIX 構文の他の部分を実装している場合でも)。^[37]

POSIX 拡張正規表現 ( ERE ) 構文の一部の文字では、バックスラッシュでエスケープされたメタ文字の意味が逆になります。この構文では、バックスラッシュによりメタ文字がリテラル文字として扱われます。たとえば、は now であり、は now です。また、バック参照のサポートが削除され、次のメタ文字が追加されました。 \( \)( )\{ \}{ }\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「cat」または「dog」に一致します。

POSIX 拡張正規表現は、コマンドラインフラグ-Eを含めることで、最新の Unix ユーティリティで使用できる場合がよくあります。

文字クラスは、リテラル マッチに次ぐ最も基本的な正規表現の概念です。これにより、1 つの小さな文字シーケンスが、より大きな文字セットに一致します。たとえば、[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,"にすることができます。つまり、 のみに一致します。^[39]".+?""Ganymede,"

JavaとPython 3.11以降では、^{[40]量指定子にプラス記号を追加することで}所有格にすることができ、これによりバックトラックエンジンでのバックオフが無効になりますが、そうすることで全体の一致が成功する場合もあります。^[41]".*"文字列に適用された 正規表現は

「ガニメデは太陽系最大の衛星です」と彼は続けた。

は行全体に一致しますが、正規表現はにはまったく一致しません".*+"。これは、が最後の を含む入力全体を消費するためです。したがって、絶対量指定子は、否定文字クラスで最も役立ちます。たとえば、 は、同じ文字列に適用された場合に一致します。 .*+""[^"]*+""Ganymede,"

同じ機能を果たすもう一つの一般的な拡張はアトミックグループ化で、括弧で囲まれたグループのバックトラックを無効にします。一般的な構文は(?>group)です。たとえば、^(wi|w)i$ はwiとwiiの両方に一致しますが、^(?>wi|w)i$ はwiiにのみ一致します。これはエンジンがバックトラックを禁止されているため、"wi" に一致した後にグループを "w" に設定できないためです。^[42]

強欲な量指定子は貪欲な量指定子や遅延量指定子よりも実装が簡単で、通常は実行時に効率的です。^[41]

IETF RFC 9485 は、「I-Regexp: 相互運用可能な正規表現フォーマット」について説明しています。これは、多数の正規表現ライブラリで相互運用可能、つまり同じ効果を生み出すように設計された、限定された正規表現イディオムのサブセットを指定します。I-Regexp は、マッチング、つまり正規表現と特定のテキスト間の真偽の一致を提供することに限定されています。したがって、キャプチャ グループ、先読み、バックリファレンスなどの高度な機能が欠けています。^[43]

ほぼすべての最新の正規表現ライブラリに備わっている多くの機能は、正規言語を超える表現力を提供します。たとえば、多くの実装では、括弧で部分式をグループ化し、同じ式内で一致する値を呼び出すことができます（後方参照)。つまり、パターンは、スクエア。これらの文字列のパターンは です(.+)\1。

平方数の言語は正規言語ではなく、ポンピング補題により文脈自由言語でもありません。しかし、多数の最新ツールでサポートされている無制限の数のバックリファレンスを使用したパターンマッチングは、依然として文脈依存です。^[44]任意の数のバックリファレンスをマッチングする一般的な問題はNP完全であり、既知のアルゴリズムの実行時間は、使用されるバックリファレンスグループの数によって指数関数的に増加します。^[45]

しかし、このような構造を提供する多くのツール、ライブラリ、エンジンでは、依然としてパターンに正規表現という用語を使用しています。このため、正規表現という用語が形式言語理論とパターン マッチングで異なる意味を持つという命名法が生まれました。このため、後者を説明するためにregex、regexp、または単にpattern という用語を使用する人もいます。Perl プログラミング言語の作者であるLarry Wall は、Raku の設計に関するエッセイで 次のように書いています。

「正規表現」は、実際の正規表現とはほとんど関係がありません。しかし、この用語はパターン マッチング エンジンの機能とともに拡大してきたため、ここでは言語上の必要性に反論するつもりはありません。ただし、一般的には「regexes」(または、アングロサクソン風に「regexen」) と呼ぶことにします。^[19]

正規言語の記述には見られない他の機能としては、アサーションがあります。これには、少なくとも1970年以来使用されているユビキタスな^や$[ ^46]や、1994年に登場したlookaroundなどのより洗練された拡張機能が含まれます。 ^[47] lookaroundは一致の周囲を定義し、一致自体には影響しません。これは、文字列検索のユースケースにのみ関連する機能です^[要出典]。それらのいくつかは、周囲も言語の一部として扱うことで、正規言語でシミュレートできます。^[48]

の先読みアサーション (?=...)とは、(?!...)少なくとも1994年からPerl 5で証明されています。 ^[47]後読みアサーション(?<=...)、(?<!...)1997年にIlya ZakharevichによるPerl 5.005へのコミットで証明されています。 ^[49]

特定の正規表現が文字列と一致するかどうか、またどのように一致するかを決定する アルゴリズムは少なくとも 3 つあります。

最も古くて高速な方法は、形式言語理論の結果に依存しており、あらゆる非決定性有限オートマトン(NFA) を決定性有限オートマトン(DFA)に変換できます。DFA は明示的に構築し、結果の入力文字列に対して 1 シンボルずつ実行できます。サイズmの正規表現の DFA の構築にはO (2 ^m )の時間とメモリのコストがかかりますが、サイズ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]

サブリニアランタイムアルゴリズムは、ボイヤー・ムーア（BM）ベースのアルゴリズムと、逆スキャンなどの関連するDFA最適化技術を使用して実現されています。^[53]さまざまなPOSIX構文と拡張機能をサポートするGNU grepは、最初のパスのプレフィルタリングにBMを使用し、次に暗黙のDFAを使用します。近似マッチングを実装するWu agrepは、プレフィルタリングをBDM（後方DAWGマッチング）のDFAに組み合わせます。NR-grepのBNDMは、Shift-Orビットレベルの並列処理でBDMテクニックを拡張します。^[54]

バックリファレンスのバックトラッキングに代わる理論的な方法はいくつか存在し、それらの「指数」はバックリファレンスの数にのみ関係する点で穏やかです。これはPOSIXなどの一部の正規表現言語の固定された特性です。バックリファレンスノートごとにバックトラッキングなしのNFAを複製する単純な方法の1つは、長さnの干し草の山とRegExpのk個のバックリファレンスに対して、時間とスペースの複雑さを伴います。[ 55${\displaystyle {\mathrm {O} }(n^{2k+2})}$ ]メモリ${\displaystyle {\mathrm {O} }(n^{2k+1})}$オートマトン^に基づくごく最近の理論的研究では、使用される「アクティブな」変数ノードに基づくより厳しい境界と、一部のバックリファレンスされた正規表現に対する多項式の可能性が示されています。^[56]

理論的には、事前に定義されている限り、どのトークン セットでも正規表現と一致させることができます。歴史的な実装では、正規表現は元々ASCII文字をトークン セットとして使用するように作成されていましたが、正規表現ライブラリは他の多数の文字セットをサポートしています。多くの最新の正規表現エンジンは、少なくともUnicodeをサポートしています。ほとんどの点で、文字セットが何であっても違いはありませんが、正規表現を拡張して Unicode をサポートすると、いくつかの問題が発生します。

• サポートされているエンコーディング。一部の正規表現ライブラリは、抽象的な Unicode 文字ではなく、特定のエンコーディングで動作することを想定しています。これらの多くはUTF-8エンコーディングを必要としますが、他のものはUTF-16またはUTF-32 を想定する場合があります。対照的に、Perl と Java はエンコーディングに依存せず、代わりに内部でデコードされた文字を操作します。
• サポートされている Unicode の範囲。多くの正規表現エンジンは、基本多言語面、つまり 16 ビットでのみエンコードできる文字のみをサポートしています。現在 (2016 年現在^{[アップデート]})、完全な 21 ビットの Unicode 範囲を処理できるのは、Perl や Java などの少数の正規表現エンジンのみです。
• ASCII 指向の構造を Unicode に拡張します。たとえば、ASCII ベースの実装では、xとyのコード ポイントが[0x00,0x7F] の範囲内にあり、 codepoint( x ) ≤ codepoint( y )である[x-y]場合は、形式の文字範囲が有効です。このような文字範囲を Unicode に自然に拡張すると、エンドポイントが [0x00,0x7F] 内にあるという要件が、エンドポイントが [0x0000,0x10FFFF] 内にあるという要件に変更されるだけです。ただし、実際にはそうならないことがよくあります。 gawkなどの一部の実装では、文字範囲が Unicode ブロックをまたぐことはできません。 [0x61,0x7F] のような範囲は、両端が基本ラテンブロック内にあるため有効であり、[0x0530,0x0560] も両端がアルメニアブロック内にあるため有効であるが、[0x0061,0x0532] のような範囲は複数の Unicode ブロックを含むため無効である。Vim エディタなどの他のエンジンではブロックをまたぐことはできるが、文字値は 256 を超えて離れてはならない。^[57]
• 大文字と小文字を区別しない。大文字と小文字を区別しないフラグの中には、ASCII 文字にのみ影響するものがあります。その他のフラグはすべての文字に影響します。エンジンによっては、ASCII 用と Unicode 用の 2 つの異なるフラグがあります。POSIX クラスに属する文字も異なります。
• 大文字と小文字を区別しないの類似機能。ASCII では大文字と小文字が区別されるため、大文字と小文字を区別しないことはテキスト検索における論理的な機能になりました。Unicodeでは、デーヴァナーガリー文字のような大文字と小文字のないアルファベット文字が導入されました。これらには、大文字と小文字の区別は適用されません。中国語などの文字では、繁体字と簡体字という別の区別が論理的であると思われます。アラビア語の文字では、語頭、語中、語末、および孤立位置を区別しないことが望ましい場合があります。日本語では、ひらがなとカタカナを区別しないことが便利な場合があります。
• 正規化。Unicode には結合文字があります。古いタイプライターのように、プレーンな基本文字 (空白、句読点、記号、数字、または文字) の後に 1 つ以上の非スペーシング記号 (通常は、文字を変更するアクセント記号のような発音区別符号) を続けると、1 つの印刷可能な文字を形成できます。ただし、Unicode では、限定された一連の合成文字、つまり 1 つ以上の結合文字がすでに含まれている文字も提供されています。基本文字 + 結合文字のシーケンスは、同一の 1 つの合成文字と一致する必要があります (これらの結合シーケンスの一部だけが 1 つの Unicode 文字に合成できますが、Unicode では他の無限の数の結合シーケンスが可能であり、最初の基本文字の後に 1 つ以上の結合文字を使用して、さまざまな言語に必要です。これらの結合シーケンスには、部分的に合成された基本文字または結合文字を含めることができますが、必ずしも正規の順序ではなく、必ずしも正規の合成を使用しているわけではありません)。基本文字 + 結合文字のシーケンスを、正規的に同等なシーケンスに分解して標準化し、その後、正規の順序に並べ替える (オプションで、一部の結合文字を先頭の基本文字に再構成する) プロセスを、正規化と呼びます。
• 新しい制御コード。Unicode では、バイト オーダー マークやテキスト方向マーカーなどが導入されました。これらのコードは、特別な方法で処理する必要がある可能性があります。
• Unicode ブロック、スクリプト、およびその他の多数の文字プロパティ用の文字クラスの導入。ブロック プロパティはスクリプト プロパティほど有用性は高くありません。これは、ブロックが複数の異なるスクリプトのコード ポイントを持つことができ、スクリプトが複数の異なるブロックのコード ポイントを持つことができるためです。^[58] Perlとライブラリでは、または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月に閉鎖されました。^[69]

具体的な構文規則は、特定の実装、プログラミング言語、または使用中のライブラリによって異なります。また、正規表現の実装の機能はバージョンによって異なる場合があります。

正規表現は例がないと説明も理解も難しいため、正規表現をテストするためのインタラクティブな Web サイトは、実験によって正規表現を学習するための便利なリソースです。このセクションでは、例を挙げて、正規表現のいくつかの特性について基本的な説明を行います。

例では以下の規則が使用されている。^[70]

メタ文字 ;; メタ文字列は、説明されている正規表現の構文を指定します
=~ m// ;; Perlの正規表現マッチ操作を示します
=~ s/// ;;はPerlの
正規表現の置換操作を示します

また、これらの正規表現はすべて Perl のような構文であることも注目に値します。標準の POSIX 正規表現は異なります。

特に明記しない限り、以下の例はPerlプログラミング言語、リリース 5.8.8、2006 年 1 月 31 日に準拠しています。つまり、他の実装では、ここで示す構文の一部がサポートされない可能性があります (例: 基本正規表現と拡張正規表現、\( \)と、またはPOSIXではなく()がない)。 \d [:digit:]

これらの例で使用されている構文と規則は、他のプログラミング環境のものと一致しています。^[71]

正規表現は、多くの場合、一連の例文字列に基づいて作成（「誘導」または「学習」）できます。これは正規言語の誘導として知られ、計算学習理論における文法誘導の一般的な問題の一部です。正式には、正規言語の文字列の例が与えられ、おそらくその正規言語にない文字列の例も与えられると、言語の文法、つまりその言語を生成する正規表現を誘導することができます。すべての正規言語がこのように誘導できるわけではありませんが（制限の言語識別を参照）、多くの正規言語が誘導できます。たとえば、例の集合 {1, 10, 100} と、（反例の）負の集合 {11, 1001, 101, 0} を使用して、正規表現 1⋅0*（1 の後に 0 個以上の 0 が続く）を誘導できます。

• 正規表現エンジンの比較
• 拡張バッカス・ナウア形式
• 一致するワイルドカード
• 正規木文法
• トンプソンの構築– 正規表現を同等の非決定性有限オートマトン (NFA)に変換します。

• ウィキメディア・コモンズの正規表現に関連するメディア
• Curlieの正規表現
• ISO/IEC 9945-2:1993 情報技術 – ポータブル オペレーティング システム インターフェース (POSIX) – パート 2: シェルとユーティリティ
• ISO/IEC 9945-2:2002 情報技術 – ポータブル オペレーティング システム インターフェース (POSIX) – パート 2: システム インターフェース
• ISO/IEC 9945-2:2003 情報技術 – ポータブル オペレーティング システム インターフェース (POSIX) – パート 2: システム インターフェース
• ISO/IEC/IEEE 9945:2009 情報技術 - ポータブル オペレーティング システム インターフェイス (POSIX) 基本仕様、第 7 版
• 正規表現、IEEE Std 1003.1-2017、Open Group