正規表現

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ
パターンの一致結果
(?< = \ 。){2、}(?= [AZ]  
少なくとも2つのスペースが一致しますが、ピリオド(。)の直後で大文字の前にある場合に限ります。
コンセプトを紹介したスティーブン・コール・クリーン
正規表現を使用して悪いタイトルを識別するウィキペディアのブラックリスト

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

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

正規表現は、検索エンジン、ワードプロセッサテキストエディタの検索および置換ダイアログ、sedAWKなどテキスト処理ユーティリティ、および字句解析で使用されます。多くのプログラミング言語は、多くの状況で使用されるため、 組み込みまたはライブラリを介して正規表現機能を提供します。

歴史

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

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

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

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

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

1997年以降、Philip HazelPCRE (Perl互換正規表現)を開発しました。これは、Perlの正規表現機能を厳密に模倣しようとし、 PHPApache HTTPServerなどの多くの最新ツールで使用されています

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

パターン

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

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

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

クリーネ閉包翻訳
s *は「 sの0個以上」を意味します

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

基本的な考え方

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

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

ブール「または」
縦棒選択肢を区切ります。たとえば、「灰色」または「灰色」に一致させることができます。gray|grey
グループ化
括弧は、演算子のスコープと優先順位を定義するために使用されます(他の用途の中でも)。たとえば、gray|greyは同等のパターンであり、どちらも「灰色」または「灰色」のセットを表します。gr(a|e)y
定量化
要素(トークン、文字、グループなど)の後の数量詞は、前の要素の繰り返しを許可する回数を指定します。最も一般的な数量詞は、疑問符アスタリスク(クリーネ閉包から派生)、およびプラス記号クリーネ閉包)です。 ? * +
? 疑問符は、前の要素が0回または1回出現することを示します。たとえば、colou?r「color」と「color」の両方に一致します。
* アスタリスクは、先行する要素が0回以上出現することを示します。たとえば、ab*c「ac」、「abc」、「abbc」、「abbbc」などに一致します。
+ プラス記号は、前の要素が1つ以上出現することを示します。たとえば、ab+c「abc」、「abbc」、「abbbc」などに一致しますが、「ac」には一致しません。
{n}[19] 前の項目は正確にn一致します。
{min,}[19] 前の項目が最小回数以上 一致しています。
{,max}[19] 前の項目は最大回数まで一致します。
{min,max}[19] 上記の項目は、少なくとも最小回一致しますが、最大回以下です。
ワイルドカード

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

これらの構成を組み合わせて、任意の複雑な式を形成できます。これは、数値と演算+、-、×、および÷から算術式を構成できるのと同じです。たとえば、H(ae?|ä)ndelはどちらも前の例と同じ文字列に一致する有効なパターンですH(a|ae|ä)ndelH(ä|ae?)ndel

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

形式言語理論

正規表現は形式言語理論で正規言語を記述します。それらは正規文法と同じ表現力を持っています。

正式な定義

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

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

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

括弧を避けるために、クリーネ閉包が最も優先度が高く、次に連結、次に交互であると想定されます。あいまいさがない場合は、括弧を省略できます。たとえば、は(ab)cと書くことができ、はと書くことができます多くの教科書では、縦棒の代わりに記号∪、+、または∨を交互に使用しています。 abca|(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と一致しないΣ*上のすべての文字列と一致します原則として、補集合演算子は、これ以上表現力を与えないため、冗長です。ただし、正規表現をはるかに簡潔にすることができます。単一の補数演算子を削除すると、その長さが二重指数関数的に爆発する可能性があります。[22] [23] [24]

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

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

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

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

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

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

正規表現の同等性の決定

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

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

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

すべての正規表現は、クリーネ閉包集合和の観点からのみ記述できますこれは驚くほど難しい問題です。正規表現は単純ですが、体系的に正規表現に書き直す方法はありません。過去の公理の欠如は、星の高さの問題につながりました。1991年、デクスターコーゼンは、等式およびホーン節の公理を使用して、正規表現をクリーネ代数として公理化しました。[27] すでに1964年に、Redkoは、純粋に等式の公理の有限集合が正規言語の代数を特徴付けることができないことを証明しました。[28]

構文

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

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

区切り文字

プログラミング言語で正規表現を入力する場合、それらは通常の文字列リテラルとして表される場合があるため、通常は引用符で囲まれます。これは、たとえばC、Java、Pythonで一般的であり、正規表現reは。として入力され"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(基本正規表現)、[29] ERE(拡張正規表現)、およびSRE(単純正規表現)3つの準拠セットがあります。SREは非推奨であり[30]、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)では必要ありません。

メタ文字 説明
^ 文字列内の開始位置と一致します。行ベースのツールでは、任意の行の開始位置と一致します。
. 任意の単一文字に一致します(多くのアプリケーションは改行を除外し、改行と見なされる文字はフレーバー、文字エンコード、およびプラットフォーム固有ですが、改行文字が含まれていると想定しても安全です)。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の後に0個以上の文字が続く場合に一致します。たとえば、「s」、「saw」、「seed」、「s3w96.7」、「s6#h%(>>> mnmQ」)。

POSIX拡張

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

メタ文字 説明
? 前の要素に0回または1回一致します。たとえば、ab?c「ac」または「abc」のみに一致します。
+ 前の要素と1回以上一致します。たとえば、ab+c「abc」、「abbc」、「abbbc」などに一致しますが、「ac」には一致しません。
| choice(alternationまたはset unionとも呼ばれます)演算子は、演算子の前の式または後の式のいずれかに一致します。たとえば、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 Vim Java ASCII
ASCII文字 [:ascii:][31] \p{ASCII} [\x00-\x7F]
英数字 [:alnum:] \p{Alnum} [A-Za-z0-9]
英数字と「_」 [:word:][31] \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は単語クラスと単語ヘッドクラスをさらに区別します(表記とを使用)。通常、数字は除外されるため、識別子はのように、またはPOSIX表記で表示されます。 [:word:][:alnum:]\w\h\h\w*[[:alpha:]_][[:alnum:]_]*

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

PerlとPCRE

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

レイジーマッチング

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

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

最初の部分だけを照合するのではなく、行全体を照合します(行全体が二重引用符で開始および終了するため)"Ganymede,"ただし、前述の数量詞は、疑問符を追加することにより、可能な限り少ない文字に一致するように、怠惰または最小限または消極にすることができます。[33]".+?""Ganymede,"

ただし、状況によっては、文全体を一致させることができます。疑問符演算子はドット演算子の意味を変更しないため、入力の二重引用符と一致させることができます。これが文字列の場合、のようなパターン".*?" EOFは入力全体に一致します。

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

二重引用符を一致の一部にできないようにするには、ドットを置き換える必要があります(例"[^"]*")。これは、追加の二重引用符なしで引用符で囲まれたテキスト部分と一致します。(固定接尾辞と一致する可能性を排除することにより、つまり"、これによりレイジーマッチが貪欲マッチに変換されたため、?は不要になりました。)[要出典]

所有格マッチング

Javaでは、プラス記号を追加することで数量詞を所有格にすることができます。これにより、(バックトラッキングエンジンで)バックオフが無効になります。これにより、全体的な一致が成功する場合でも、次のようになります。[34]正規表現".*"が文字列に適用されている 間

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

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

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

所有格の数量詞は、欲張りで怠惰な数量詞よりも実装が簡単で、通常、実行時に効率的です。[34]

非正規言語のパターン

事実上すべての最新の正規表現ライブラリに見られる多くの機能は、正規言語を超える表現力を提供しますたとえば、多くの実装では、括弧を使用して部分式をグループ化し、同じ式で一致する値を呼び出すことができます(後方参照)。これは、とりわけ、パターンが、形式言語理論で正方形これらの文字列のパターンはです(.+)\1

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

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

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

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

正規言語の記述にはないその他の機能には、アサーションが含まれます。これらには、ユビキタスな^$、およびルックアラウンドのようないくつかのより洗練された拡張機能が含まれます。これらは一致の周囲を定義し、一致自体にはこぼれません。これは、文字列検索のユースケースにのみ関連する機能です。それらのいくつかは、周囲を言語の一部として扱うことにより、正規言語でシミュレートすることもできます。[38]

実装と実行時間

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

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

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

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

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

劣線形ランタイムアルゴリズムは、ボイヤームーア(BM)ベースのアルゴリズムと、リバーススキャンなどの関連するDFA最適化手法を使用して実現されています。[42]さまざまなPOSIX構文と拡張機能をサポートするGNUGrepは、ファーストパスの事前フィルタリングにBMを使用し、次に暗黙のDFAを使用します。近似マッチングを実装するWuagrepは、プレフィルタリングをBDMのDFAに結合します(後方DAWGマッチング)。NR-grepのBNDMは、Shift-Orビットレベルの並列処理でBDM手法を拡張します。[43]

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

Unicode

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

  • サポートされているエンコーディング一部の正規表現ライブラリは、抽象的なUnicode文字ではなく、特定のエンコーディングで機能することを期待しています。これらの多くはUTF-8エンコーディングを必要としますが、 UTF-16またはUTF-32を期待するものもあります。対照的に、PerlとJavaはエンコーディングにとらわれず、代わりに内部でデコードされた文字を操作します。
  • サポートされているUnicode範囲多くの正規表現エンジンは、基本多言語面、つまり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]のような範囲は、両方のエンドポイントが基本ラテンブロック内にあるため有効です。[0x0530,0x0560]は、両方のエンドポイントがアルメニアブロック内にあるため有効ですが、[0x0061,0x0532]のような範囲は、含まれているため無効です。複数のUnicodeブロック。Vimエディターのエンジンなど、他のエンジンではブロック交差が許可されていますが、文字値の間隔は256を超えてはなりません。[46]
  • 大文字と小文字の区別。一部の大文字と小文字を区別しないフラグは、ASCII文字にのみ影響します。他のフラグはすべての文字に影響します。一部のエンジンには2つの異なるフラグがあります。1つはASCII用で、もう1つはUnicode用です。正確にどの文字がPOSIXクラスに属するかも異なります。
  • 大文字と小文字を区別しないいとこASCIIには大文字と小文字が区別されるため、大文字と小文字を区別しないことがテキスト検索の論理的な機能になりました。Unicodeは、デーバナーガリーのように大文字と小文字を区別せずにアルファベットのスクリプトを導入しました。これらの場合、大文字と小文字の区別は適用されません。中国語のようなスクリプトの場合、もう1つの違いは論理的であるように思われます。つまり、繁体字と簡体字の違いです。アラビア文字では、初期、中間、最終、および孤立した位置に鈍感であることが望ましい場合があります。日本語では、ひらがなカタカナの間の鈍感さが役立つ場合があります。
  • 正規化Unicodeには結合文字があります古いタイプライターと同様に、プレーンベース文字(空白、句読点、記号、数字、または文字)の後に1つ以上の非間隔記号(通常、文字を修飾するアクセント記号などの発音区別符号)を続けて、単一の印刷可能な文字を形成できます。ただし、Unicodeは、合成済み文字の限定されたセット、つまり1つ以上の結合文字をすでに含む文字も提供します。基本文字+結合文字のシーケンスは、同一の単一の合成済み文字と一致する必要があります(これらの結合シーケンスの一部のみを単一のUnicode文字に事前合成できますが、Unicodeでは他の無限に多くの結合シーケンスが可能であり、さまざまな言語で必要です、最初の基本文字の後に1つ以上の結合文字を使用します。これらの結合シーケンスは、基本文字または部分的に合成された結合文字を含めますが、必ずしも正規の順序である必要はなく、必ずしも正規の合成を使用する必要はありません)。基本文字のシーケンスを標準化する+これらの正規の等価シーケンスを分解して結合文字を正規の順序に並べ替える(およびオプションでいくつかの結合文字を先頭の基本文字に再構成する)プロセスは、正規化と呼ばれます。
  • 新しい制御コードUnicode、特にバイト順マークとテキスト方向マーカーが導入されました。これらのコードは、特別な方法で処理する必要がある場合があります。
  • Unicodeブロック、スクリプト、およびその他の多数の文字プロパティの文字クラスの紹介ブロックは複数の異なるスクリプトからのコードポイントを持つことができ、スクリプトはいくつかの異なるブロックからのコードポイントを持つことができるため、ブロックプロパティはスクリプトプロパティよりもはるかに有用ではありません。[47] Perlおよびライブラリでjava.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コード検索Exaleadが含まれます。ただし、Googleコード検索は2012年1月にシャットダウンされました。[48]

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

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

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

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

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

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

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

メタ文字 説明 [51]
. 通常、改行を除くすべての文字に一致します。
角括弧内のドットはリテラルです。
$ string1  =  "Hello World \ n" ; 
if  $ string1  =  〜m /...../){print " $  string1の長さは> = 5です。\ n " 
  ; } 

出力:

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

出力:

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

出力:

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

出力:

0-1文字で区切られた「H」と「e」があります(例:He Hue Hee)。
? *前に来る、、、または'd正規表現を、可能な限り一致するように +変更します。?{M,N}
$ string1  =  "Hello World \ n" ; 
if  $ string1  =  〜m /(l。+?o)/){print "欲張り ない一致と 'l'の後に1つまたは" ; print "より多くの文字は 'lloWo'ではなく 'llo'です。\ n" ; }
   
   

出力:

'l'の後に1つ以上の文字が続く欲張りでない一致は、 'lloWo'ではなく 'llo'です。
* 前のパターン要素と0回以上一致します。
$ string1  =  "Hello World \ n" ; 
if  $ string1  = 〜m  / el * o /  { 
  print  "「e」の後に0から多数が続く" ; 
  「 '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には、1つ以上2つのlを持つサブストリングが存在します
[…] 可能な文字一致のセットを示します。
$ string1  =  "Hello World \ n" ; 
if  $ string1  = 〜m  / [aeiou] + /  { 
  print  "$ string1には1つ以上の母音が含まれています。\ n" ; 
}

出力:

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

出力:

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

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

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

出力:

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

Unicodeでは[47]Alphabeticプロパティにはラテン文字より多くがDecimal_Number含まれ、プロパティにはアラブ数字より多くが含まれます。

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

出力:

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

Unicodeで。

$ 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つの空白文字があり、" ; 
  印刷 "他の文字で区切る。\ n" ; 
}

出力:

HelloWorldで
 2つの空白文字があり、他の文字で区切ることができます。
\S 空白以外の もの一致します。
$ string1  =  "Hello World \ n" ; 
if  $ string1  = 〜m  / \ S。* \ S /  { 
  print  "$ string1には2つの非空白文字があり、" ; 
  print  "は他の文字で区切ることができます。\ n" ; 
}

出力:

HelloWorldで
 空白以外の文字が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文字あります; 
  印刷 "これは数字ではありません。\ n" ; 
}

出力:

HelloWorldには少なくとも1人のキャラクターがいます
 それは数字ではありません。
^ 行または文字列の先頭に一致します。
$ string1  =  "Hello World \ n" ; 
if  $ string1  = 〜m  / ^ He /  { 
  print  "$ string1は文字 'He'で始まります。\ n" ; 
}

出力:

こんにちは世界
 文字「彼」で始まります。
$ 行または文字列の終わりに一致します。
$ string1  =  "Hello World \ n" ; 
if  $ string1  =  〜m / rld $ /  { 
  print  "$ string1は行または文字列です" ; 
  print  "'rld'で終わります。\ n" ; 
}

出力:

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

出力:

こんにちは
世界
 'H'で始まる文字列です。
\z 文字列の終わりに一致します(ただし、内部行には一致しません)。[52]
$ string1  =  "こんにちは\ n世界\ n" ; 
if  $ string1  = 〜m  / d \ n \ z /  { 
  print  "$ string1 is a string" ; 
  print  "'d \\ n'で終わります。\ n" ; 
}

出力:

こんにちは
世界
 'd \ n'で終わる文字列です。
[^…] 角かっこ内の文字を除くすべての文字に一致します。
$ string1  =  "Hello World \ n" ; 
if  $ string1  = 〜m  / [^ abc] /  { 
 print "$ string1には"  ;以外の文字が含まれています 印刷"a、b、およびc。\ n" ; }
  

出力:

こんにちは世界
 a、b、c以外の文字が含まれています。

誘導

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

も参照してください

メモ

  1. ^ Goyvaerts、1月。「正規表現チュートリアル-正規表現の使用方法を学ぶ」www.regular-expressions.info2016年11月1日にオリジナルからアーカイブされまし2016年10月31日取得
  2. ^ ミトコフ、ルスラン(2003)。計算言語学のオックスフォードハンドブックオックスフォード大学出版局。p。754. ISBN 978-0-19-927634-92017-02-28にオリジナルからアーカイブされました2016年7月25日取得
  3. ^ ローソン、マークV.(2003年9月17日)。有限オートマトンCRCプレス。pp。98–100。ISBN 978-1-58488-255-82017年2月27日にオリジナルからアーカイブされました2016年7月25日取得
  4. ^ Kleene1951
  5. ^ Leung、Hing(2010年9月16日)。「正規言語と有限オートマトン」(PDF)ニューメキシコ州立大学2013年12月5日にオリジナル(PDF)からアーカイブされました2019年8月13日取得正規表現の概念は、正規表現の定義を介してKleeneによって導入されました。
  6. ^ a b Thompson1968
  7. ^ a b Johnson etal。1968
  8. ^ Kernighan、Brian(2007-08-08)。「正規表現マッチャー」ビューティフルコードオライリーメディアpp。1–2。ISBN 978-0-596-51004-62020-10-07にオリジナルからアーカイブされました2013年5月15日取得
  9. ^ Ritchie、DennisM。「QEDテキストエディタの不完全な歴史」1999-02-21にオリジナルからアーカイブされました2013年10月9日取得
  10. ^ a b Aho&Ullman 1992、10.11第10章の参考文献ノート、p。589。
  11. ^ Aycock 2003、2。JITコンパイル手法、2.1ジェネシス、p。98。
  12. ^ Raymond、Eric S.はDennisRitchie(2003)を引用しています。「Jargonファイル4.4.7:grep」2011年6月5日にオリジナルからアーカイブされました2009年2月17日取得
  13. ^ 「Tcl8.1の新しい正規表現機能」2020-10-07にオリジナルからアーカイブされました2013年10月11日取得
  14. ^ 「PostgreSQL9.3.1ドキュメント:9.7。パターンマッチング」2020-10-07にオリジナルからアーカイブされました2013年10月12日取得
  15. ^ Wall、LarryおよびPerl 5開発チーム(2006年)。"perlre:Perl正規表現"2009年12月31日にオリジナルからアーカイブされました2006年10月10日取得
  16. ^ a b 壁(2002)
  17. ^ 「GROVF |ビッグデータ分析アクセラレーション」grovf.com2020-10-07にオリジナルからアーカイブされました2019年10月22日取得
  18. ^ 「CUDAgrep」bkase.github.io2020-10-07にオリジナルからアーカイブされました2019年10月22日取得
  19. ^ a b c d grep(1)のマニュアルページ
  20. ^ a b Hopcroft、Motwani&Ullman(2000)
  21. ^ シプサ(1998)
  22. ^ Gelade &Neven(2008、p。332、Thm.4.1)
  23. ^ Gruber&Holzer(2008)
  24. ^ Gelade&Neven(2008)に基づくになるような長さ約850の正規表現は、 File:RegexComplementBlowup.pngあります。
  25. ^ ジェイL.ギッシャー(1984)。(タイトル不明)(テクニカルレポート)。スタンフォード大学、Comp。Sc。
  26. ^ ジョンE.ホップクロフト; Rajeev Motwani&Jeffrey D. Ullman(2003)オートマトン理論、言語、および計算の概要アッパーサドルリバー/ニュージャージー州:アディソンウェスリー。ISBN 978-0-201-44124-6ここで:Sect.3.4.6、p.117-120。—このプロパティは、正規言語よりも大きなクラスを記述していない場合でも、拡張正規表現に当てはまる必要はありません。cf. p.121。
  27. ^ Kozen(1991)[必要なページ]
  28. ^ VN Redko(1964)。「定期的なイベントの代数の関係を定義することについて」Ukrainskii MatematicheskiiZhurnal16(1):120–126。2018-03-29にオリジナルからアーカイブされました2018年3月28日取得(ロシア語で)
  29. ^ ISO / IEC 9945-2:1993情報技術–ポータブルオペレーティングシステムインターフェイス(POSIX)–パート2:シェルとユーティリティ、ISO / IEC 9945-2:2002情報技術–ポータブルオペレーティングシステムインターフェイス(POSIX)–パート2:システムインターフェイス、ISO / IEC 9945-2:2003、および現在ISO / IEC / IEEE 9945:2009情報技術–ポータブルオペレーティングシステムインターフェイス(POSIX®)基本仕様、第7号
  30. ^ シングルUnix仕様(バージョン2)
  31. ^ a b "33.3.1.2文字クラス— Emacs lispマニュアル—バージョン25.1"gnu.org2016年。2020-10-07のオリジナルからアーカイブ2017年4月13日取得
  32. ^ 「Perl正規表現ドキュメント」perldoc.perl.org。2009年12月31日にオリジナルからアーカイブされました2012年1月8日取得
  33. ^ a b "正規表現構文"Python3.5.0のドキュメントPython SoftwareFoundation2018年7月18日にオリジナルからアーカイブされました2015年10月10日取得
  34. ^ a b "必須クラス:正規表現:数量詞:貪欲、消極的、所有格の数量詞の違い"JavaチュートリアルOracle2020年10月7日にオリジナルからアーカイブされました2016年12月23日取得
  35. ^ 「アトミックグループ化」正規表現チュートリアル2020年10月7日にオリジナルからアーカイブされました2019年11月24日取得
  36. ^ CezarCâmpeanu; Kai Salomaa&Sheng Yu(2003年12月)。「実用的な正規表現の正式な研究」コンピュータサイエンスの基礎の国際ジャーナル14(6):1007-1018。土井10.1142 / S012905410300214X2015年7月4日にオリジナルからアーカイブされました2015年7月3日取得定理3(p.9)
  37. ^ 「Perl正規表現マッチングはNP困難です」perl.plover.com2020-10-07にオリジナルからアーカイブされました2019年11月21日取得
  38. ^ さまようロジック。「有限状態オートマトンで先読みと後読みをシミュレートする方法は?」コンピュータサイエンススタック交換2020年10月7日にオリジナルからアーカイブされました2019年11月24日取得
  39. ^ コックス(2007)
  40. ^ ラウリカリ(2009)
  41. ^ "gnulib / lib /dfa.c"2021-08-18にオリジナルからアーカイブされました2022-02-12を取得スキャナーがbackrefで遷移を検出すると、一種の「半成功」を返し、バックトラッキングマッチャーで一致を検証する必要があることを示します。
  42. ^ カーンズ、スティーブン(2013年8月)。「逆サフィックススキャンを使用した有限オートマトンとの劣線形マッチング」。arXiv1308.3822 [ cs.DS ]。
  43. ^ Navarro、ゴンザロ(2001年11月10日)。「NR-grep:高速で柔軟なパターンマッチングツール」(PDF)ソフトウェア:実践と経験31(13):1265–1312。土井10.1002 /spe.411S2CID3175806_ 2020年10月7日のオリジナルからアーカイブ(PDF)2019年11月21日取得  
  44. ^ 「travisdowns / polyregex」GitHub2019年7月5日。2020年9月14日のオリジナルからアーカイブ2019年11月21日取得
  45. ^ Schmid、Markus L.(2019年3月)。「後方参照を使用した正規表現:多項式時間マッチング手法」。arXiv1903.05896 [ cs.FL ]。
  46. ^ 「Vimドキュメント:パターン」Vimdoc.sourceforge.net。2020-10-07にオリジナルからアーカイブされました2013年9月25日取得
  47. ^ a b "Unicode正規表現のUTS#18、付録A:文字ブロック"2020-10-07にオリジナルからアーカイブされました2010年2月5日取得
  48. ^ ホロウィッツ、ブラッドリー(2011年10月24日)。「フォールスイープ」Googleブログ2018年10月21日にオリジナルからアーカイブされました2019年5月4日取得
  49. ^ 文字「m」はPerlの一致操作を指定するために必ずしも必要ではありませんたとえば、としてレンダリングすることもできます'm'は、ユーザーが正規表現の区切り文字としてスラッシュを使用せずに一致操作を指定する場合にのみ必要です「区切り文字の衝突」を回避するために、代替の正規表現区切り文字を指定すると便利な場合があります詳細については、「 WaybackMachineでアーカイブされたperldocperlre2009-12-31」を参照してください。m/[^abc]//[^abc]/
  50. ^ たとえば、 Java の概要を参照してください。213; 計算科学のためのPythonスクリプティング、p。320; PHPのプログラミング、p。106。
  51. ^ すべてのifステートメントがTRUE値を返すことに注意してください
  52. ^ コンウェイ、ダミアン(2005)。「正規表現、文字列の終わり」Perlのベストプラクティスオライリーp。240. ISBN 978-0-596-00173-52020-10-07にオリジナルからアーカイブされました2017年9月10日取得

参考文献

外部リンク