正規表現

フリー百科事典ウィキペディアより
ナビゲーションにジャンプ 検索にジャンプ
パターンの試合結果
(? < = \ .) {2,}(?= [AZ] ) 
少なくとも 2 つのスペースが一致しますが、ピリオド (.) の直後で大文字の前にある場合に限ります。

正規表現( regexまたはregexpと短縮されます。[1]有理式[2] [3]と呼ばれることもあります) は、 text内の検索パターンを指定する一連の文字です。通常、このようなパターンは、文字列に対する「検索」操作または「検索と置換」操作、または入力検証のための文字検索アルゴリズムによって使用されます。正規表現手法は、理論的コンピューター サイエンス形式言語理論で開発されています。

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

正規表現は、検索エンジン、ワード プロセッサテキスト エディタの検索および置換ダイアログ、sedAWKなどテキスト処理ユーティリティ、および字句解析で使用されます。Python [4] C[5] C++ [ 6] Java [ 7] Rust [ 8] OCaml [ 9 ]および JavaScript . [10]

歴史

コンセプトを導入したスティーブン・コール・クリーネ

正規表現は、1951 年に数学者Stephen Cole Kleeneが正規イベントと呼ばれる数学表記を使用して正規言語を記述したときに始まりました[11] [12]これらは、オートマトン理論(計算モデル)のサブフィールド、および形式言語の記述と分類において、理論的コンピューター サイエンスで発生しました。パターン マッチングのその他の初期の実装には、正規表現を使用せず、代わりに独自のパターン マッチング構造を使用する SNOBOL言語が含まれます。

正規表現は、テキスト エディターでのパターン マッチング[13]とコンパイラでの字句解析の2 つの用途で、1968 年から一般的に使用されるようになりました。[14]プログラム形式で正規表現が最初に登場したのは、Ken Thompsonがテキスト ファイル内のパターンを照合する手段としてエディタQEDに Kleene の表記法を組み込んだときでした[13] [15] [16] [17]速度のために、Thompsonは、JIT コンパイルの初期の重要な例である、 Compatible Time-Sharing System上のIBM 7094コードにJust-In -Time コンパイル(JIT)による正規表現マッチングを実装しました。[18]彼は後に、この機能を Unix エディターedに追加し、最終的に人気のある検索ツールgrepで正規表現を使用するようになりました (「grep」は、ed エディターでの正規表現検索のコマンドから派生した単語で、「グローバル検索」を意味します)。正規表現と一致する行の印刷」)。[19] Thompson が QED を開発したのとほぼ同時期に、Douglas T. Rossを含む研究者グループが、コンパイラ設計で字句解析に使用される正規表現に基づくツールを実装しました。[14]g/re/p

これらの元の形式の正規表現の多くのバリエーションは、1970 年代にベル研究所のUNIX [17]プログラム ( vilexsedAWKexprなど) や、 Emacsなどの他のプログラムで使用されました。その後、正規表現は幅広いプログラムで採用され、これらの初期の形式は 1992 年 にPOSIX.2標準で標準化されました。

1980 年代に、より複雑な正規表現がPerlで発生しました。これは、 Henry Spencer (1986)によって作成された正規表現ライブラリから派生したもので、後にAdvanced Regular Expressions for Tclの実装を作成しました。[20] Tcl ライブラリは、パフォーマンス特性が向上したハイブリッドNFA / DFA実装です。Spencer の Tcl 正規表現実装を採用したソフトウェア プロジェクトには、PostgreSQLが含まれます。[21] Perl は後に Spencer の元のライブラリを拡張して、多くの新機能を追加しました。[22]のデザインの一部(以前は Perl 6 と呼ばれていました) は、Perl の正規表現の統合を改善し、その範囲と機能を拡大して、構文解析式の文法を定義できるようにすることです。[23]その結果、Raku rulesと呼ばれるミニ言語ができあがり、Raku の文法を定義し、言語のプログラマーにツールを提供するために使用されます。これらのルールは、Perl 5.x 正規表現の既存の機能を維持しますが、サブルールを介し て再帰降下パーサーのBNFスタイルの定義も可能にします。

ドキュメントおよびデータベース モデリングのための構造化情報標準における正規表現の使用は 1960 年代に始まり、 ISO SGML (ANSI "GCA 101-1983" によって先行)などの業界標準が統合された 1980 年代に拡大しました。構造仕様言語標準のカーネルは、正規表現で構成されています。その使用は、DTD要素グループの構文で明らかです。正規表現を使用する前は、多くの検索言語で単純なワイルドカードを使用できました。たとえば、「*」は任意の文字列に一致し、「?」は「?」です。単一の文字に一致します。この遺物は、現在、ファイル名のglob構文とSQL LIKE演算子に見られます。

1997 年以降、Philip HazelPCRE (Perl Compatible Regular Expressions) を開発しました。これは、Perl の正規表現機能を厳密に模倣しようとするもので、 PHPApache HTTP Serverなどの多くの最新のツールで使用されています[要出典]

現在、正規表現は、プログラミング言語、テキスト処理プログラム (特にlexers )、高度なテキスト エディター、およびその他のプログラムで広くサポートされています。正規表現のサポートは、 JavaPythonなどの多くのプログラミング言語の標準ライブラリの一部であり、Perl やECMAScriptなどの他の言語の構文に組み込まれています正規表現機能の実装はregex エンジンと呼ばれることが多く、多数のライブラリを再利用できます。2010 年代後半に、いくつかの企業がハードウェア、FPGA[24] GPU [25]のPCRE互換の実装を提供し始めました。 CPU実装に比べて高速な正規表現エンジン

パターン

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

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

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

Kleene スター翻訳
( s * は「0 個以上のs」を意味します)

正規表現プロセッサは、上記の構文の正規表現を、検索対象のテキストを表す文字列に対して実行および照合できる内部表現に変換します。考えられるアプローチの 1 つは、非決定論的有限オートマトン(NFA)を構築するトンプソンの構築アルゴリズムです。その後、決定論的になり、結果の決定論的有限オートマトン(DFA) がターゲット テキスト文字列に対して実行され、正規表現に一致する部分文字列が認識されます。この図は、正規表現 から得られた NFA スキームを示しています。ここで、sN(s*)s*は、NFA N ( s ) に再帰的に変換された、より単純な正規表現を順番に示します。

基本概念

多くの場合パターンと呼ばれる正規表現は、特定の目的に必要な文字列のセットを指定します。文字列の有限セットを指定する簡単な方法は、その要素またはメンバーをリストすることです。ただし、多くの場合、もっと簡潔な方法があります。たとえば、3 つの文字列 "Handel"、"Händel"、および "Haendel" を含むセットは、 pattern で指定できますH(ä|ae?)ndelこのパターンは 3 つの文字列のそれぞれに一致すると言えます。ただし、同じ文字列セットの正規表現を記述する方法は多数あります(Hän|Han|Haen)del。たとえば、この例では 3 つの文字列の同じセットも指定しています。

ほとんどの形式主義は、正規表現を構築するために次の操作を提供します。

ブール値の「または」
垂直バー代替案を区切ります。たとえば、「グレー」または「グレー」に一致できます。gray|grey
グループ化
括弧は、演算子の範囲と優先順位を定義するために使用されます(他の用途の中でも)。たとえば、gray|greyはどちらも「グレー」または「グレー」のセットを表す同等のパターンです。gr(a|e)y
定量化
要素 ( token 、文字、またはグループなど) の後の量指定子は、前の要素を何回繰り返すことができるかを指定します。最も一般的な量指定子は、疑問符アスタリスク( Kleene starから派生)、およびプラス記号( Kleene plus ) です。 ? * +
? 疑問符は、前の要素が0 回または 1回出現することを示します。たとえば、colou?r「color」と「color」の両方に一致します。
* アスタリスクは、前の要素が0 回以上出現することを示します。たとえば、ab*c「ac」、「abc」、「abbc」、「abbbc」などに一致します。
+ プラス記号は、前の要素が1 つ以上出現することを示します。たとえば、ab+c「abc」、「abbc」、「abbbc」などには一致しますが、「ac」には一致しません。
{n}[26] 前の項目は正確にn一致します。
{min,}[26] 前のアイテムがmin回以上 一致しています。
{,max}[26] 前のアイテムはmax回まで一致します。
{min,max}[26] 前のアイテムは少なくともmin回一致しますが、 max回を超えません
ワイルドカード

ワイルドカード.は任意の文字に一致します。たとえばa.b、「a」、任意の文字、「b」を含むすべての文字列に一致します。そしてa.*b、"a" を含み、その後に文字 "b" を含む任意の文字列に一致します。

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

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

形式言語理論

正規表現は形式言語理論で正規言語を記述します。通常の文法と同じ表現力があります。

正式な定義

正規表現は、文字列のセットを表す定数と、これらのセットに対する操作を表す演算子記号で構成されます。次の定義は標準的なものであり、形式言語理論に関するほとんどの教科書にそのように記載されています。[27] [28]有限のアルファベットΣ が与えられると、次の定数が正規表現として定義されます。

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

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

  • ( concatenation )(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"} を記述する場合、式(R|S)は { を記述します"ab"、"c"、"d"、"ef"}。
  • ( Kleene star )は、 ε を含み、文字列連結の下で閉じている、 Rによって記述されるセット(R*)の最小のスーパーセットを示します。これは、R によって記述されるセットから任意の有限数 (0 を含む) の文字列を連結することによって作成できるすべての文字列のセットです。たとえば、R が {"0", "1"} を表す場合、すべての文字列のセットを表します。有限バイナリ文字列(空の文字列を含む)。R が {"ab", "c"} を表す場合、{ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "abcab", を表します。 ..}。(R*)(R*)

括弧を避けるために、Kleene スターが最も優先度が高く、次に連結、次に代替であると想定されます。あいまいさがなければ、括弧は省略できます。たとえば、(ab)cと書くことができabc、 と書くa|(b(c*))ことができますa|bc*多くの教科書では、縦棒の代わりに記号 ∪、+、または ∨ を交互に使用しています。

例:

  • a|b*{ε, "a", "b", "bb", "bbb", ...}を表す
  • (a|b)*空の文字列を含む、"a" と "b" 以外の記号を含まないすべての文字列のセットを示します: {ε, "a", "b", "aa", "ab", "ba", "bb" 、「ああ」、...}
  • 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」、...}

表現力とコンパクトさ

正規表現の正式な定義は意図的に最小限に抑えられており、 and の定義を避け?ています。これらは= 、 and =の+ように表現できます一般化された正規表現を与えるために、補数演算子が追加されることがあります。ここでR cは、 Rに一致しない Σ* 上のすべての文字列に一致します原則として、補数演算子は冗長です。それ以上の表現力を与えないからです。ただし、正規表現をより簡潔にすることができます。1 つの補数演算子を削除すると、その長さが2 倍の指数関数的に爆発する可能性があります。[29] [30] [31]a+aa*a?(a|ε)

この意味での正規表現は、決定論的有限オートマトンによって受け入れられる言語のクラスである正規言語を表現できます。ただし、コンパクトさには大きな違いがあります。正規言語の一部のクラスは、決定論的有限オートマトンによってのみ記述できます。そのサイズは、同等の最短の正規表現のサイズで指数関数的に増加します。ここでの標準的な例は 、アルファベット { a , b }のすべての文字列で構成される言語L kで、最後から k番目の文字がaに等しい言語です。一方、L 4を記述する正規表現は次のように与えられます 。.

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

一方、言語L kを受け入れるすべての決定論的有限オートマトンは、少なくとも 2 k 個の状態を持たなければならないことが知られています。幸いなことに、正規表現からより一般的な非決定論的有限オートマトン(NFA) への単純なマッピングがあり、サイズがそれほど大きくなることはありません。このため、NFA は通常の言語の代替表現としてよく使用されます。NFA は、チョムスキー階層のタイプ 3文法の単純なバリエーションです[27]

逆に言えば、DFA では簡単に記述でき、正規表現では簡単に記述できない言語がたくさんあります。たとえば、特定のISBNの有効性を判断するには、11 を底とする整数のモジュラスを計算する必要があり、11 ステート DFA を使用して簡単に実装できます。ただし、11 で割り切れるという同じ問題に答える正規表現は、少なくとも数メガバイトの長さになります。[要出典]

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

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

正規表現の等価性の決定

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

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

正規表現の代数法則は、例に沿って最もよく説明されているGischer による方法を使用取得できますXY 、特定の正規表現 ( a + b ) *および ( a * b * ) *がアルファベット Σ={ a , bで同じ言語を表すかどうかを確認する必要があり、十分です。 }。より一般的には、変数を含む正規表現項間の方程式E = Fが成立するのは、異なるシンボル定数で置き換えられた異なる変数を使用したインスタンス化が成立する場合に限られます。[32] [33]

すべての正規表現は、Kleene starおよびset unionに関してのみ記述できます。これは意外と難しい問題です。正規表現は単純ですが、体系的に正規表現に書き直す方法はありません。過去の公理の欠如は、星の高さの問題につながりました。1991 年、Dexter Kozenは正規表現をKleene 代数として公理化し、方程式とホーン節の公理を使用しました。[34] すでに 1964 年に、Redko は、正規言語の代数を特徴付ける純粋な等式公理の有限集合は存在しないことを証明していました。[35]

構文

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

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

区切り記号

プログラミング言語で正規表現を入力すると、正規表現は通常の文字列リテラルとして表される場合があるため、通常は引用符で囲みます。reこれは、正規表現が として入力されるC、Java、および Python などで一般的です"re"ただし、正規表現のように、区切り文字としてスラッシュを使用して記述されることがよくありますこれはedに由来し、は検索用のエディター コマンドであり、式を使用して (パターンに一致する) 行の範囲を指定できます。これはgrep ("global regex print") は、LinuxなどのほとんどのUnixベースのオペレーティング システムに含まれています。/re/re//re/g/re/pディストリビューション。同様の規則がsedで使用されます。ここで、検索と置換は で指定されs/re/replacement/、パターンをコンマで結合して、 のように行の範囲を指定できます/re1/,/re2/この表記法は、通常の文字列リテラルとは異なる構文の一部を形成するPerlで使用されているため、特によく知られています。sed や Perl などの一部のケースでは、代替の区切り文字を使用して、コンテンツとの衝突を回避し、コンテンツ内の区切り文字の出現をエスケープする必要を回避できます。たとえば、sed では、コマンドはカンマを区切り文字として使用 して、a をs,/,X,に置き換えます。/X

基準

IEEE POSIX標準には、 BRE (基本正規表現)、[36] ERE (拡張正規表現)、およびSRE (単純正規表現)3 つの準拠セットがあります。SRE は非推奨[37]、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 基本および拡張

POSIX標準では、基本正規構文 ( BRE ) ではメタ文字 ( ){ }を指定する必要が\(\)ありますが\{\}、拡張正規構文 ( ERE ) では指定しません。

メタキャラクター 説明
^ 文字列内の開始位置に一致します。線ベースのツールでは、任意の線の開始位置に一致します。
. 任意の 1 文字に一致します (多くのアプリケーションは newlines を除外します。正確にどの文字が改行と見なされるかは、フレーバー、文字エンコード、およびプラットフォーム固有ですが、改行文字が含まれていると想定するのは安全です)。POSIX ブラケット式内では、ドット文字はリテラル ドットと一致します。たとえば、a.c「abc」などに[a.c]一致しますが、「a」、「.」、または「c」のみに一致します。
[ ] ブラケット式。括弧内に含まれる単一の文字に一致します。たとえば[abc]、「a」、「b」、または「c」に一致します。[a-z]"a" から "z" までの任意の小文字に一致する範囲を指定します。これらの形式を混在させることができます: と[abcx-z]同様に、"a"、"b"、"c"、"x"、"y"、または "z" に一致し[a-cx-z]ます。

文字が括弧内の最後の文字または最初の文字 (存在する場合は の後) である場合、その-文字はリテラル文字として扱われます: , . バックスラッシュのエスケープは許可されていないことに注意してください。その文字が最初の ( の後の) 文字である場合、その文字をブラケット式に含めることができます: . ^[abc-][-abc]]^[]abc]

[^ ] 括弧内に含まれていない単一の文字に一致します。たとえば[^abc]、「a」、「b」、または「c」以外の任意の文字に一致します。[^a-z]"a" から "z" までの小文字以外の任意の 1 文字に一致します。同様に、リテラル文字と範囲を混在させることができます。
$ 文字列の終了位置または文字列終了の改行の直前の位置に一致します。線ベースのツールでは、任意の線の終了位置に一致します。
( ) マークされた部分式を定義します。括弧内で一致した文字列は、後で呼び出すことができます (次のエントリを参照)。マークされた部分式は、ブロックまたはキャプチャ グループとも呼ばれます。BRE モードには が必要です。 \n\( \)
\n n番目にマークされた部分式が一致したものと一致します。ここで、 nは 1 から 9 までの数字です。この構成は、POSIX.2 標準で漠然と定義されています。一部のツールでは、9 つ​​を超えるキャプチャ グループを参照できます。後方参照とも呼ばれます。後方参照は BRE モードでのみサポートされます
* 直前の要素に 0 回以上一致します。たとえば、ab*c「ac」、「abc」、「abbbc」などに[xyz]*一致します。「」、「x」、「y」、「z」、「zx」、「zyx」、「xyzzy」などに一致します。(ab)*""、"ab"、"abab"、"ababab" などに一致します。
{m,n} 直前の要素にm回以上n回以下一致します。たとえば、a{3,5}「aaa」、「aaaa」、および「aaaaa」のみに一致します。これは、正規表現のいくつかの古いインスタンスでは見つかりません。BRE モードには が必要\{m,n\}です。

例:

  • .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"、"saw"、"seed"、"s3w96.7"、"s6#h%(>>>mn mQ" など、s の後に 0 個以上の文字が続くものと一致します。

POSIX 拡張

バックスラッシュでエスケープされたメタ文字の意味は、POSIX 拡張正規表現 ( ERE ) 構文の一部の文字で逆になります。この構文では、円記号によってメタ文字がリテラル文字として扱われます。たとえば、\( \)is now( )\{ \}is now{ }です。さらに、後方参照のサポートが削除され、次のメタ文字が追加されました。 \n

メタキャラクター 説明
? 直前の要素と 0 回または 1 回一致します。たとえば、ab?c「ac」または「abc」のみに一致します。
+ 直前の要素に 1 回以上一致します。たとえば、ab+c「abc」、「abbc」、「abbbc」などには一致しますが、「ac」には一致しません。
| 選択 (代替またはセット ユニオンとも呼ばれます) 演算子は、演算子の前の式または後の式のいずれかに一致します。たとえば、abc|def「abc」または「def」に一致します。

例:

  • [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 ユーティリティで使用できます。

文字クラス

文字クラスは、リテラル一致に続く最も基本的な正規表現の概念です。これにより、1 つの小さな一連の文字が、より大きな一連の文字と一致します。たとえば、英語のアルファベットの大文字を表すことができ、任意の数字を意味することができます。文字クラスは両方の POSIX レベルに適用されます。 [A-Z]\d

(つまり、小文字から大文字)のように文字の範囲を指定する場合、コンピュータのロケール設定は、文字エンコードの数値順序によって内容を決定します。それらはその順序で数字を格納するか、順序がabc…zABC…ZまたはaAbBcC… zZ になる可能性があります。したがって、POSIX 標準では文字クラスが定義されており、これはインストールされている正規表現プロセッサによって認識されます。これらの定義を次の表に示します。 [a-Z]aZ

説明 POSIX 非標準 Perl/Tcl ヴィム ジャワ アスキー
アスキー文字 [:ascii:][38] \p{ASCII} [\x00-\x7F]
英数字 [:alnum:] \p{Alnum} [A-Za-z0-9]
英数字と「_」 [:word:][38] \w \w \w [A-Za-z0-9_]
単語以外の文字 \W \W \W [^A-Za-z0-9_]
英字 [:alpha:] \a \p{Alpha} [A-Za-z]
スペースとタブ [:blank:] \s \p{Blank} [ \t]
単語境界 \b \< \> \b (?<=\W)(?=\w)|(?<=\w)(?=\W)
非単語境界 \B (?<=\W)(?=\W)|(?<=\w)(?=\w)
制御文字 [:cntrl:] \p{Cntrl} [\x00-\x1F\x7F]
数字 [:digit:] \d \d \p{Digit}また\d [0-9]
数字以外 \D \D \D [^0-9]
目に見える文字 [:graph:] \p{Graph} [\x21-\x7E]
小文字 [:lower:] \l \p{Lower} [a-z]
可視文字とスペース文字 [:print:] \p \p{Print} [\x20-\x7E]
句読点 [:punct:] \p{Punct} [][!"#$%&'()*+,./:;<=>?@\^_`{|}~-]
空白文字 [:space:] \s \_s \p{Space}また\s [ \t\r\n\v\f]
非空白文字 \S \S \S [^ \t\r\n\v\f]
大文字 [:upper:] \u \p{Upper} [A-Z]
16 進数 [:xdigit:] \x \p{XDigit} [A-Fa-f0-9]

POSIX 文字クラスは、ブラケット式内でのみ使用できます。たとえば、大文字と小文字の「a」および「b」に一致します。 [[:upper:]ab]

一部のツールで理解される追加の非 POSIX クラスは です。これは通常プラス アンダースコアとして定義されます。これは、多くのプログラミング言語でこれらの文字が識別子に使用される可能性があるという事実を反映しています。多くのプログラミング言語では、識別子を開始できる文字は、他の位置で発生する可能性のある文字と同じではないため、エディターVimはさらに単語クラスと語頭クラスを (表記法andを使用して) 区別します。数字は一般に除外されるため、識別子またはのように見えますPOSIX表記。 [:word:][:alnum:]\w\h\h\w*[[:alpha:]_][[:alnum:]_]*

POSIX 正規表現標準が文字クラスと呼ぶものは、それらをサポートする他の正規表現フレーバーでは一般にPOSIX 文字クラスと呼ばれることに注意してください。他のほとんどの正規表現フレーバーでは、文字クラスという用語は、POSIX がブラケット式と呼ぶものを説明するために使用されます

Perl と PCRE

その表現力と (相対的な) 読みやすさのために、他の多くのユーティリティやプログラミング言語がPerlに似た構文を採用しています— たとえば、JavaJavaScriptJuliaPythonRubyQt、 Microsoft の.NET Framework、およびXMLスキーマBoostPHPなどの一部の言語とツール複数の正規表現フレーバーをサポートします。Perl 派生の正規表現の実装は同一ではなく、通常、1994 年にリリースされた Perl 5.0 にある機能のサブセットを実装しています。Perl は、他の言語で最初に見つかった機能を組み込むことがあります。たとえば、Perl 5.10 は、もともと PCRE と Python で開発された構文拡張を実装しています。[39]

遅延マッチング

Python およびその他の実装 (Java など) では、3 つの一般的な量指定子 ( *+および?) は、可能な限り多くの文字に一致するため、デフォルトで貪欲です。[40]文字列に適用される正規表現".+"(二重引用符を含む)

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

は、最初の部分"Ganymede,". ただし、前述の量指定子は、疑問符を追加することにより、遅延または最小または消極的になり、できるだけ少ない文字に一致するようにすることができます:".+?"一致のみ"Ganymede,". [40]

所有格一致

Java では、プラス記号を追加することで量指定子を所有格にすることができます。これにより、(バックトラッキング エンジンでの) バックオフが無効なり".*"ます 。

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

行全体に一致しますが、正規表現はまったく一致し".*+"ません。最終的な. したがって、所有量指定子は、否定された文字クラス (たとえば、同じ文字列に適用された場合に 一致する) で最も役立ちます。.*+""[^"]*+""Ganymede,"

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

所有量指定子は、貪欲で怠惰な量指定子よりも実装が容易であり、通常は実行時に効率的です。[41]

非正規言語のパターン

ほぼすべての最新の正規表現ライブラリに見られる多くの機能は、通常の言語を超える表現力を提供しますたとえば、多くの実装では、部分式を括弧でグループ化し、同じ式で一致する値を呼び出すことができます (後方参照)。これは、とりわけ、パターンが「パパ」や「ウィキウィキ」などの単語の繰り返しの文字列に一致する可能性があることを意味しますは形式言語理論で四角形これらの文字列のパターンは(.+)\1.

ポンピング補題により、正方形の言語は規則的ではなく、文脈自由でもありません。ただし、多数の最新ツールでサポートされているように、無制限の数の後方参照を使用したパターン マッチングは、依然として状況依存です。[43]任意の数の後方参照に一致する一般的な問題はNP 完全であり、使用される後方参照グループの数によって指数関数的に増加します。[44]

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

「正規表現」[…] は、実際の正規表現とはわずかにしか関連していません。とはいえ、この用語は私たちのパターン マッチング エンジンの機能とともに成長してきたので、ここで言語の必要性と戦おうとするつもりはありません。ただし、私は一般的にそれらを「正規表現」(または、アングロサクソン気分のときは「正規表現」) と呼びます。[23]

アサーション

アサーション 後ろを見て 先のことを考える
ポジティブ (? <=パターン) (? =パターン)
ネガティブ (? <!パターン) (? !パターン)
Perl正規表現
での後読みアサーションと先読みアサーション

通常の言語の記述には見られないその他の機能には、アサーションが含まれます。これらには、少なくとも 1970 年から使用されているユビキタスな^$が含まれます[45] 。また、1994 年に登場したルックアラウンドのようないくつかのより洗練された拡張機能も含まれます[46] 。 、文字列検索のユースケースにのみ関連する機能。それらのいくつかは、周囲も言語の一部として扱うことにより、通常の言語でシミュレートできます。[47]

[46]後読みアサーション(?=…)andは、1997 年以降、 Ilya (?!…)Zakharevichによる Perl 5.005 へのコミットで証明されています。[48](?<=…)(?<!…)

実装と実行時間

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

最も古く、最も速いものは、すべての非決定論的有限オートマトン(NFA) を決定論的有限オートマトン(DFA)に変換できる形式言語理論の結果に依存しています。DFA を明示的に作成し、結果の入力文字列に対して一度に 1 シンボルずつ実行できます。サイズmの正規表現の DFA を構築するには、 O (2 m )の時間とメモリ コストがかかりますが、時間O ( n )でサイズnの文字列に対して実行できます。式のサイズは、数値量指定子などの省略形が展開された後のサイズであることに注意してください。

別のアプローチは、NFA を直接シミュレートすることです。基本的に、各 DFA 状態をオンデマンドで構築し、次のステップで破棄します。これにより、DFA が暗黙的に保持され、指数関数的な構築コストが回避されますが、ランニング コストはO ( mn ) に上昇します。明示的なアプローチは DFA アルゴリズムと呼ばれ、暗黙的なアプローチは NFA アルゴリズムと呼ばれます。NFA アルゴリズムにキャッシングを追加することは、「遅延 DFA」アルゴリズム、または区別せずに単に DFA アルゴリズムと呼ばれることがよくあります。これらのアルゴリズムは高速ですが、グループ化された部分式の呼び出し、遅延定量化、および同様の機能に使用するのは難しいです。[49] [50]最新の実装には、Cox のコードに基づく re1-re2-sregex ファミリーが含まれます。

3 番目のアルゴリズムは、バックトラッキングによって入力文字列に対してパターンを照合することです。このアルゴリズムは一般に NFA と呼ばれますが、この用語は混乱を招く可能性があります。その実行時間は指数関数的である可能性があります。単純な実装では、代替と無制限の量化の両方を含むような式と照合するときに示され、指数関数的に増加する数のサブケースをアルゴリズムに考慮するように強制します。この動作は、正規表現サービス拒否(ReDoS) と呼ばれるセキュリティ上の問題を引き起こす可能性があります。(a|aa)*b

バックトラッキングの実装は、最悪の場合に指数関数的な保証しか与えませんが、はるかに優れた柔軟性と表現力を提供します。たとえば、後方参照の使用を許可する実装、または Perl によって導入されたさまざまな拡張機能を実装する実装には、何らかの種類のバックトラッキングが含まれている必要があります。一部の実装では、最初に高速な DFA アルゴリズムを実行することで両方のアルゴリズムの最良の部分を提供しようとし、一致中に後方参照が検出された場合にのみ、潜在的に低速なバックトラッキング アルゴリズムに戻ります。GNU grep (および基礎となる gnulib DFA) は、このような戦略を使用します。[51]

サブリニア ランタイム アルゴリズムは、Boyer-Moore (BM) ベースのアルゴリズムと、リバース スキャンなどの関連する DFA 最適化手法を使用して実現されています。[52]多種多様な POSIX 構文と拡張機能をサポートする GNU grep は、最初のパスの事前フィルタリングに BM を使用し、次に暗黙の DFA を使用します。近似マッチングを実装するWu agrepは、プレフィルタリングを BDM の DFA に結合します (後方 DAWG マッチング)。NR-grep の BNDM は、Shift-Or ビットレベルの並列処理で BDM 手法を拡張します。[53]

後方参照のバックトラッキングに代わる理論的な代替手段がいくつか存在し、それらの「指数」は、POSIX などの一部の正規表現言語の固定プロパティである後方参照の数にのみ関連するという点でより使いやすいです。各後方参照ノートに対して非バックトラッキング NFA を複製する単純な方法の 1 つは、次のような複雑さがあります。時間とRegExp 内の長さ n および k の後方参照の干し草の山のためのスペース。[54]メモリ オートマトンに基づく非常に最近の理論的研究では、使用される「アクティブな」変数ノードに基づくより厳密な境界と、一部の逆参照正規表現の多項式の可能性が示されています。[55]

ユニコード

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

  • サポートされているエンコーディング一部の正規表現ライブラリは、抽象的な Unicode 文字ではなく、特定のエンコーディングで動作することを期待しています。これらの多くはUTF-8エンコーディングを必要としますが、他のものはUTF-16またはUTF-32を期待するかもしれません対照的に、Perl と Java はエンコーディングにとらわれず、内部でデコードされた文字を操作します。
  • サポートされている Unicode 範囲多くの正規表現エンジンはBasic Multilingual Plane、つまり 16 ビットのみでエンコードできる文字のみをサポートしています。現在 (2016 年現在)、21 ビットの Unicode 範囲全体を処理できる正規表現エンジンはごくわずかです (Perl や Java など)。
  • ASCII 指向の構造を Unicode に拡張しますたとえば、ASCII ベースの実装では、xyコード ポイントが [0x00,0x7F] の範囲で codepoint( x ) ≤ codepoint( y[x-y] ) である場合、この形式の文字範囲は有効ですこのような文字範囲を Unicode に自然に拡張すると、エンドポイントが [0x00,0x7F] にあるという要件が [0x0000,0x10FFFF] にあるという要件に単純に変更されます。しかし、実際にはそうではないことが多い。gawkなどの一部の実装、文字範囲が Unicode ブロックをまたがることを許可しないでください。[0x61,0x7F] のような範囲は両方のエンドポイントが Basic Latin ブロック内にあるため有効であり、[0x0530,0x0560] は両方のエンドポイントがアルメニア ブロック内にあるため有効ですが、[0x0061,0x0532] のような範囲は含まれているため無効です。複数の Unicode ブロック。Vimエディターのエンジンなど、他のエンジンではブロック交差が許可されますが、文字値は 256 を超えて離れてはなりません。[56]
  • 大文字と小文字を区別しません。一部の大文字と小文字を区別しないフラグは、ASCII 文字のみに影響します。その他のフラグはすべての文字に影響します。一部のエンジンには、ASCII 用と Unicode 用の 2 つの異なるフラグがあります。正確にどの文字が POSIX クラスに属しているかも異なります。
  • 大文字と小文字を区別しないのいとこASCII には大文字と小文字の区別があるため、大文字と小文字を区別しないことがテキスト検索の論理的な機能になりました。Unicode では、デーバナーガリーのように大文字と小文字を区別しないアルファベット スクリプトが導入されました。これらの場合、大文字と小文字の区別は適用されません。中国語のようなスクリプトの場合、もう 1 つの区別は理にかなっているように見えます。それは、繁体字と簡体字です。アラビア語のスクリプトでは、最初、中間、最後、および孤立した位置に鈍感であることが望ましい場合があります。日本語では、ひらがなカタカナの間の無感覚が役立つ場合があります。
  • 正規化Unicode には結合文字があります. 古いタイプライターのように、単純な基本文字 (空白、句読点、記号、数字、または文字) の後に 1 つまたは複数の非間隔記号 (通常は文字を修飾するアクセント記号などの分音符号) を続けて、1 つの印刷可能な文字を形成できます。ただし、Unicode は、事前に構成された文字の限られたセット (つまり、1 つ以上の結合文字を既に含む文字) も提供します。基本文字 + 結合文字のシーケンスは、同一の単一の構成済み文字と一致する必要があります (これらの結合シーケンスの一部のみが単一の Unicode 文字に事前構成できますが、無限に多くの他の結合シーケンスが Unicode で可能であり、さまざまな言語に必要です) 、最初の基本文字の後に 1 つまたは複数の結合文字を使用する; これらの結合シーケンスは、基本文字または部分的に事前構成された結合文字を含みますが、必ずしも正規の順序ではなく、必ずしも正規の事前構成を使用するとは限りません)。基本文字のシーケンスを標準化し、これらの標準的に同等のシーケンスを分解して文字を組み合わせてから、それらを標準的な順序に並べ替える (オプションで、いくつかの結合文字を先頭の基本文字に再構成する) プロセスは、正規化と呼ばれます。
  • 新しい制御コードとりわけ導入された Unicode、バイト オーダー マーク、テキスト方向マーカー。これらのコードは、特別な方法で処理する必要がある場合があります。
  • Unicode ブロック、スクリプト、その他多数の文字プロパティの文字クラスの導入ブロック プロパティは、スクリプト プロパティほど有用ではありません。ブロックは複数の異なるスクリプトのコード ポイントを持つことができ、スクリプトは複数の異なるブロックのコード ポイントを持つことができるからです。[57] Perljava.util.regexライブラリでは、フォームのプロパティまたは\p{InX}ブロックX\p{Block=X}の文字に一致する、そのブロックにないコード ポイントに一致します。同様に、、またはは、アルメニア スクリプトの任意の文字と一致します。一般に、バイナリ プロパティXまたは一般カテゴリ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 スクレイピング)、データ ラングリング、単純な解析構文強調表示システムの作成、およびその他の多くのタスクが含まれます。

正規表現はインターネット検索エンジンでは便利ですが、正規表現の複雑さと設計によっては、データベース全体で正規表現を処理すると、過剰なコンピューター リソースが消費される可能性があります。多くの場合、システム管理者は正規表現ベースのクエリを内部で実行できますが、ほとんどの検索エンジンは一般に正規表現サポートを提供していません。注目すべき例外には、Google Code SearchExaleadが含まれます。しかし、Google Code Search は 2012 年 1 月に閉鎖されました。[58]

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

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

例では、次の規則が使用されています。[59]

メタ文字 ;; metacharacters 列は、実証されている正規表現構文を指定します
=~m// ;; Perl での正規表現一致操作を示します
=~ s/// ;; Perl で
の正規表現置換操作を示します

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

特に明記しない限り、次の例は、2006 年 1 月 31 日のリリース 5.8.8のPerl\( \)プログラミング言語に準拠しています。 、またはPOSIXの代わりにの()欠如)。 \d [:digit:]

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

メタキャラクター 説明 [61]
. 通常、改行以外の任意の文字に一致します。
角括弧内のドットはリテラルです。
$string1  =  "Hello World\n" ; 
if  ( $string1  =~  m/...../ )  { 
  print  "$string1 の長さ >= 5.\n" ; 
}

出力:

Hello World
の長さは >= 5 です。
( ) 一連のパターン要素を 1 つの要素にグループ化します。
括弧内のパターンに一致する場合は$1、 、$2、 ... のいずれかを後で使用して、以前に一致したパターンを参照できます。\1一部の実装では、 , のように、代わりにバックスラッシュ表記を使用する場合があります\2
$string1  =  "Hello World\n" ; 
if  ( $string1  =~  m/(H..).(o..)/ )  { 
  print  "'$1' と '$2' が一致しました。\n" ; 
}

出力:

「Hel」と「o W」を一致させました。
+ 先行するパターン要素に 1 回以上一致します。
$string1  =  "Hello World\n" ; 
if  ( $string1  =~  m/l+/ )  { 
  print  "$string1 には 1 つ以上の連続した文字 \"l\" があります。\n" ; 
}

出力:

Hello World に 1 つ以上の連続した文字 "l" があります。
? 先行するパターン要素と 0 回または 1 回一致します。
$string1  =  "Hello World\n" ; 
if  ( $string1  =~  m/H.?e/ )  { 
  print  "" で区切られた 'H' と 'e' があります。
  print  "0-1 文字 (例: He Hue Hee).\n" ; 
}

出力:

'H' と 'e' は 0 ~ 1 文字で区切られています (例: He Hue Hee)。
? 、、、または'd の前にある正規表現を一致する回数をできるだけ少なくするように *変更します。+?{M,N}
$string1  =  "Hello World\n" ; 
if  ( $string1  =~  m/(l.+?o)/ )  { 
  print  "'l' の後に 1 つまたは " が続く非貪欲な一致; 
  print  "より多くの文字は 'llo Wo' ではなく 'llo' です.\n" ; 
}

出力:

'l' の後に 1 つ以上の文字が続く非貪欲な一致は、'llo Wo' ではなく 'llo' です。
* 直前のパターン要素に 0 回以上一致します。
$string1  =  "Hello World\n" ; 
if  ( $string1  =~  m/el*o/ )  { 
  print  "'e' の後にゼロから多数が続きます " ; 
  print  "'l' の後に 'o' (例: eo、elo、ello、elllo)。\n" ; 
}

出力:

「e」の後に 0 から多数の「l」が続き、その後に「o」が続きます (例: eo、elo、ello、elllo)。
{M,N} 最小の M と最大の N の一致カウントを示します。
N は省略でき、M は 0 です。{M}「正確に」M 回一致します。{M,}「少なくとも」M 回一致します。{0,N}"最大" N 回一致します。
x* y+ z?したがって、 は と同等x{0,} y{1,} z{0,1}です。
$string1  =  "Hello World\n" ; 
if  ( $string1  =~  m/l{1,2}/ )  { 
  print  "少なくとも 1 つの部分文字列が存在します " ; 
  print  "そして $string1 には最大で 2 つの l があります\n" ; 
}

出力:

Hello World には、l が 1 つ以上 2 つ以下の部分文字列が存在します
[…] 可能な文字の一致のセットを示します。
$string1  =  "Hello World\n" ; 
if  ( $string1  =~  m/[aeiou]+/ )  { 
  print  "$string1 には 1 つ以上の母音が含まれています。\n" ; 
}

出力:

Hello World
には 1 つ以上の母音が含まれます。
| 別の可能性を分離します。
$string1  =  "Hello World\n" ; 
if  ( $string1  =~  m/(Hello|Hi|Pogo)/ )  { 
  print  "$string1 には、Hello、Hi、または Pogo の少なくとも 1 つが含まれています。" ; 
}

出力:

Hello World
には、Hello、Hi、または Pogo の少なくとも 1 つが含まれます。
\b 単語クラスの文字 (次を参照) と非単語クラスの文字またはエッジの間のゼロ幅境界に一致します。と同じ

(^\w|\w$|\W\w|\w\W).

$string1  =  "Hello World\n" ; 
if  ( $string1  =~  m/llo\b/ )  { 
  print  "「llo」で終わる単語があります。\n" ; 
}

出力:

「ろ」で終わる言葉があります。
\w 「_」を含む英数字に一致します。ASCII
と同じ、および[A-Za-z0-9_]
[\p{Alphabetic}\p{GC=Mark}\p{GC=Decimal_Number}\p{GC=Connector_Punctuation}]

Unicode では、[57]Alphabeticプロパティにラテン文字以上が含まれ、プロパティDecimal_Numberにアラビア数字以上が含まれます。

$string1  =  "Hello World\n" ; 
if  ( $string1  =~  m/\w/ )  { 
  print  "少なくとも 1 つの英数字があります" ; 
  print  "$string1 の文字 (AZ、az、0-9、_)。\n" ; 
}

出力:

Hello World には少なくとも 1 つの英数字
(AZ、az、0-9、_) があります。
\W 「_」を除く英数字以外の文字に一致します。ASCII
と同じ、および[^A-Za-z0-9_]
[^\p{Alphabetic}\p{GC=Mark}\p{GC=Decimal_Number}\p{GC=Connector_Punctuation}]

ユニコードで。

$string1  =  "Hello World\n" ; 
if  ( $string1  =~  m/\W/ )  { 
  print  "Hello と " の間のスペース; 
  print  "ワールドは英数字ではありません。\n" ; 
}

出力:

Hello と World の間のスペースは英数字ではありません。
\s 空白文字に一致します
。ASCII では、タブ、ライン フィード、フォーム フィード、キャリッジ リターン、およびスペースです。
Unicode では、改行なしスペース、次の行、および可変幅スペース (とりわけ) にも一致します。
$string1  =  "Hello World\n" ; 
if  ( $string1  =~  m/\s.*\s/ )  { 
  print  "$string1 には 2 つの空白文字があります。" ; 
  print  " 他の文字で区切られます。\n" ; 
}

出力:

Hello World
には 2 つの空白文字があり、他の文字で区切られている場合があります。
\S 空白以外に一致し ます
$string1  =  "Hello World\n" ; 
if  ( $string1  =~  m/\S.*\S/ )  { 
  print  "$string1 には 2 つの非空白文字があります。" ; 
  print  " は他の文字で区切られている可能性があります。\n" ; 
}

出力:

Hello World
には 2 つの非空白文字があり、他の文字で区切られている場合があります。
\d 数字に一致します。ASCII
と同じ。Unicode では、orプロパティと同じで、それ自体はプロパティと同じです。 [0-9]
\p{Digit}\p{GC=Decimal_Number}\p{Numeric_Type=Decimal}
$string1  =  "壁に 99 本のビール。" ; 
if  ( $string1  =~  m/(\d+)/ )  { 
  print  "$1 は '$string1' の最初の数字です\n" ; 
}

出力:

99は「99本のビールが壁に飾られている」の最初の数字です。
\D 数字以外に一致します。ASCII またはUnicode
と同じです。[^0-9]\P{Digit}
$string1  =  "Hello World\n" ; 
if  ( $string1  =~  m/\D/ )  { 
  print  "$string1 には少なくとも 1 文字あります" ; 
  print  "これは数字ではありません。\n" ; 
}

出力:


Hello Worldには、数字以外の文字が少なくとも 1 つ含まれています。
^ 行または文字列の先頭に一致します。
$string1  =  "Hello World\n" ; 
if  ( $string1  =~  m/^He/ )  { 
  print  "$string1 は文字 'He' で始まります。\n" ; 
}

出力:

Hello World
は文字「He」で始まります。
$ 行または文字列の末尾に一致します。
$string1  =  "Hello World\n" ; 
if  ( $string1  =~  m/rld$/ )  { 
  print  "$string1 は行または文字列です" ; 
  print  "それは 'rld' で終わります。\n" ; 
}

出力:

Hello World
は、「rld」で終わる行または文字列です。
\A 文字列の先頭に一致します (ただし、内部行には一致しません)。
$string1  =  "こんにちは\n世界\n" ; 
if  ( $string1  =~  m/\AH/ )  { 
  print  "$string1 は文字列です" ; 
  print  "それは 'H' で始まります。\n" ; 
}

出力:

Hello 
World
は「H」で始まる文字列です。
\z 文字列の末尾に一致します (ただし、内部行には一致しません)。[62]
$string1  =  "こんにちは\n世界\n" ; 
if  ( $string1  =~  m/d\n\z/ )  { 
  print  "$string1 は文字列です" ; 
  print  "'d\\n' で終わる。\n" ; 
}

出力:

Hello 
World
は、'd\n' で終わる文字列です。
[^…] 括弧内の文字を除くすべての文字に一致します。
$string1  =  "Hello World\n" ; 
if  ( $string1  =~  m/[^abc]/ )  { 
 print  "$string1 には " 以外の文字が含まれています。
 print  "a、b、および c.\n" ; 
}

出力:

Hello World
に a、b、c 以外の文字が含まれています。

誘導

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

も参照

注意事項

  1. ^ Goyvaerts, Jan. "Regular Expression Tutorial - Learn How to Use Regular Expressions" . www.regular-expressions.info2016-11-01にオリジナルからアーカイブ2016 年10 月 31 日閲覧
  2. ^ ミトコフ、ルスラン (2003). 計算言語学のオックスフォードハンドブックオックスフォード大学出版局。p。754.ISBN _ 978-0-19-927634-9. 2017-02-28 のオリジナルからのアーカイブ2016 年7 月 25 日閲覧
  3. ^ ローソン、マーク V. (2003 年 9 月 17 日)。有限オートマトンCRCプレス。pp.98–100。ISBN 978-1-58488-255-8. 2017 年 2 月 27 日にオリジナルからアーカイブされました2016年 7 月 25 日閲覧
  4. ^ "re — 正規表現操作 — Python 3.10.4 ドキュメント" . docs.python.org . 2022 年4 月 27 日閲覧
  5. ^ "regex(3) - Linux マニュアル ページ" . man7.org 2022 年4 月 27 日閲覧
  6. ^ "正規表現ライブラリ - cppreference.com" . en.cppreference.com 2022 年4 月 27 日閲覧
  7. ^ 「パターン (Java Platform SE 7)」 . docs.oracle.com . 2022 年4 月 27 日閲覧
  8. ^ "crates.io の正規表現" . Crates.io .{{cite web}}: CS1 maint: url-status (リンク)
  9. ^ "OCaml ライブラリ : Str" . v2.ocaml.org 2022 年8 月 21 日閲覧
  10. ^ "正規表現 - JavaScript | MDN" . developer.mozilla.org . 2022 年4 月 27 日閲覧
  11. ^ クリーネ 1951 .
  12. ^ Leung, Hing (2010 年 9 月 16 日). 「正規言語と有限オートマトン」(PDF) . ニューメキシコ州立大学2013 年 12 月 5 日に元の(PDF)からアーカイブされました2019年8月13日閲覧通常のイベントの概念は、正規表現の定義を通じて Kleene によって導入されました。
  13. ^ a b トンプソン 1968 .
  14. ^ b ジョンソン ら。1968 .
  15. ^ カーニハン、ブライアン(2007-08-08). 「正規表現マッチャー」 . 美しいコードオライリーメディアpp.1–2。ISBN 978-0-596-51004-6. 2020-10-07 のオリジナルからのアーカイブ2013 年5 月 15 日閲覧
  16. ^ Ritchie, Dennis M. "An incomplete history of the QED Text Editor" . 1999-02-21のオリジナルからのアーカイブ2013年 10 月 9 日閲覧
  17. ^ a b Aho & Ullman 1992 , 10.11 第 10 章の書誌事項、p. 589。
  18. ^ Aycock 2003、2. JIT Compilation Techniques、2.1 Genesis、p. 98。
  19. ^ Raymond, Eric S.引用Dennis Ritchie (2003). 「専門用語ファイル 4.4.7: grep」 . 2011-06-05のオリジナルからのアーカイブ2009 年2 月 17 日閲覧
  20. ^ "Tcl 8.1 の新しい正規表現機能" . 2020-10-07 のオリジナルからのアーカイブ2013 年10 月 11日閲覧
  21. ^ "PostgreSQL 9.3.1 ドキュメント: 9.7. パターン マッチング" . 2020-10-07 のオリジナルからのアーカイブ2013 年10 月12 日閲覧
  22. ^ Wall、Larry、および Perl 5 開発チーム (2006 年)。「perlre: Perl 正規表現」 . 2009 年 12 月 31 日のオリジナルからのアーカイブ2006 年10 月 10 日閲覧
  23. ^ a b Wall (2002)
  24. ^ "GROVF | ビッグデータ分析アクセラレーション" . grovf.com2020-10-07 のオリジナルからのアーカイブ2019年10月22日閲覧
  25. ^ "CUDA grep" . bkase.github.io . 2020-10-07 のオリジナルからのアーカイブ2019年10月22日閲覧
  26. ^ a b c d grep(1) man ページ
  27. ^ a b Hopcroft、Motwani & Ullman (2000)
  28. ^ シプサー (1998)
  29. ^ ジェレイド&ネヴェン (2008年, p. 332, Thm.4.1)
  30. ^ グルーバー & ホルツァー (2008)
  31. ^ Gelade & Neven (2008)に基づき、その補数の長さが約 2 32になる長さ約 850 の正規表現は、 File:RegexComplementBlowup.pngにあります。
  32. ^ ジェイ・L・ギッシャー (1984). (タイトル不明)(テクニカルレポート)。スタンフォード大学、コンプ学科。科学。
  33. ^ ジョン・E・ホプクロフト。Rajeev Motwani & Jeffrey D. Ullman (2003)。オートマトン理論、言語、および計算の紹介アッパー サドル リバー/ニュージャージー州: アディソン ウェズリー。ISBN 978-0-201-44124-6.ここ: セクション 3.4.6、p.117-120。— このプロパティは、正規言語より大きなクラスを記述していなくても、拡張正規表現を保持する必要はありません。参照。p.121。
  34. ^ 光善 (1991) [要ページ]
  35. ^ VN Redko (1964). 「正規事象の代数の関係の定義について」 . Ukrainskii Matematicheskii Zhurnal . 16 (1): 120–126. 2018-03-29 のオリジナルからのアーカイブ2018 年3 月 28 日閲覧(ロシア語で)
  36. ^ ISO/IEC 9945-2:1993情報技術 – ポータブル オペレーティング システム インターフェイス (POSIX) – パート 2: シェルとユーティリティ、ISO/IEC 9945-2:2002情報技術 – ポータブル オペレーティング システム インターフェイス (POSIX) – パートとして順次改訂2: System Interfaces、ISO/IEC 9945-2:2003、および現在は ISO/IEC/IEEE 9945:2009 Information technology – Portable Operating System Interface (POSIX®) 基本仕様、第 7 号
  37. ^ シングル Unix 仕様 (バージョン 2)
  38. ^ a b "33.3.1.2 文字クラス — Emacs Lisp マニュアル — バージョン 25.1" . gnu.org2016. 2020-10-07 のオリジナルからのアーカイブ2017年 4 月13 日閲覧
  39. ^ "Perl 正規表現のドキュメント" . perldoc.perl.org. 2009 年 12 月 31 日にオリジナルからアーカイブされました2012年1 月 8 日閲覧
  40. ^ a b 「正規表現の構文」 . Python 3.5.0 ドキュメントPython ソフトウェア財団2018 年 7 月 18 日にオリジナルからアーカイブされました2015年10 月 10 日閲覧
  41. ^ a b 「必須クラス: 正規表現: 量指定子: 貪欲、消極的、および所有量指定子の違い」 . Java チュートリアルオラクル2020 年 10 月 7 日にオリジナルからアーカイブされました2016年 12 月 23 日閲覧
  42. ^ 「アトミック グループ化」 . 正規表現のチュートリアル. 2020 年 10 月 7 日に元の場所からアーカイブされました2019年11月24日閲覧
  43. ^ Cezar Câmpeanu; Kai Salomaa & Sheng Yu (2003 年 12 月)。「実用的な正規表現の正式な研究」 . コンピュータ サイエンスの基礎の国際ジャーナル14 (6): 1007–1018. ドイ10.1142/S012905410300214X2015-07-04 のオリジナルからのアーカイブ2015 年7 月 3 日閲覧定理 3 (p.9)
  44. ^ "Perl 正規表現マッチングは NP 困難" . perl.plover.com2020-10-07 のオリジナルからのアーカイブ2019年11月21日閲覧
  45. ^ DM Ritchie and KL Thompson, "QED Text Editor", MM-70-1373-3 (June 1970), reprinted as "QED Text Editor Reference Manual", MHCC-004, Murray Hill Computing, Bell Laboratories (1972 年 10 月)。
  46. ^ a b ウォール、ラリー (1994-10-18). "Perl 5: perlre.pod" . GitHub .
  47. ^ 流浪のロジック. 「有限状態オートマトンで先読みと後読みをシミュレートする方法は?」. コンピューター サイエンス スタック交換. 2020 年 10 月 7 日にオリジナルからアーカイブされました2019年11月24日閲覧
  48. ^ Zakharevich、Ilya (1997-11-19). "ジャンボ正規表現パッチが適用されました (マイナーな修正の微調整あり): Perl/perl5@c277df4" . GitHub .
  49. ^ コックス (2007)
  50. ^ ラウリカリ (2009)
  51. ^ "gnulib/lib/dfa.c" . 2021-08-18にオリジナルからアーカイブされました2022 年2 月 12 日閲覧スキャナーが backref で遷移を検出すると、バックトラッキング マッチャーで一致を検証する必要があることを示す一種の「半成功」を返します。
  52. ^ カーンズ、スティーブン (2013 年 8 月). 「リバース サフィックス スキャンを使用した有限オートマトンによるサブリニア マッチング」。arXiv : 1308.3822 [ cs.DS ]。
  53. ^ Navarro、Gonzalo (2001 年 11 月 10 日). 「NR-grep: 高速で柔軟なパターン マッチング ツール」(PDF) . ソフトウェア: 実践と経験31 (13): 1265–1312。ドイ: 10.1002/spe.411 . S2CID 3175806 . 2020 年 10 月 7 日にオリジナルからアーカイブ(PDF)されました2019年11月21日閲覧  
  54. ^ "travisdowns/polyregex" . GitHub . 2019 年 7 月 5 日。2020 年9 月 14 日に元の場所からアーカイブされました2019年11月21日閲覧
  55. ^ Schmid、Markus L. (2019 年 3 月)。「後方参照を伴う正規表現: 多項式時間マッチング手法」. arXiv : 1903.05896 [ cs.FL ]。
  56. ^ "Vim ドキュメント: パターン" . Vimdoc.sourceforge.net。2020-10-07 のオリジナルからのアーカイブ2013 年9 月 25 日閲覧
  57. ^ a b "Unicode 正規表現に関する UTS#18、付録 A: 文字ブロック" . 2020-10-07 のオリジナルからのアーカイブ2010 年2 月 5 日閲覧
  58. ^ ホロウィッツ、ブラッドリー(2011 年 10 月 24 日). 「フォールスイープ」 . Google ブログ. 2018 年 10 月 21 日にオリジナルからアーカイブされました2019年5月4日閲覧
  59. ^ 文字 'm' は、 Perlの一致操作を指定するために常に必要なわけではありません。たとえば、m/[^abc]/としてレンダリングすることもできます/[^abc]/「m」は、ユーザーが正規表現区切り文字としてスラッシュを使用せずに一致操作を指定したい場合にのみ必要です「区切り文字の衝突」を避けるために、別の正規表現区切り文字を指定すると便利な場合があります詳細については、「 perldoc perlre Archived 2009-12-31 at the Wayback Machine」を参照してください。
  60. ^ たとえば、 Java in a Nutshellを参照してください。213; 計算科学のためのPythonスクリプト、p. 320; プログラミングPHP、p. 106.
  61. ^ すべての if ステートメントが TRUE 値を返すことに注意してください
  62. ^ コンウェイ、ダミアン(2005). 「正規表現、文字列の終わり」 . Perl のベスト プラクティスオライリーp。240.ISBN _ 978-0-596-00173-5. 2020-10-07 のオリジナルからのアーカイブ2017 年 9月10 日閲覧

参考文献

外部リンク