正規表現
これは X {\displaystyle X} に含まれる記号列の集合と Y {\displaystyle Y} に含まれる記号列の集合の和集合を表す。 X Y {\displaystyle XY} も正規表現である。これは X {\displaystyle X} に含まれる記号列に Y {\displaystyle Y} に含まれる記号列をつなげてできる記号列の集合 { a b ∣ a ∈ X , b ∈ Y } {\displaystyle \{ab\mid a\in X,b\in Y\}} を表す。 X ∗ {\displaystyle X*} も正規表現である。これは X {\displaystyle X} に含まれる記号列を 0 個以上つなげてできる文字列の集合 ⋃ n { X n ∣ n ≥ 0 } {\displaystyle \bigcup _{n}\{X^{n}\mid n\geq 0\}} を表す(クリーネ閉包)。
上記の帰納的導出によって構成される記号列のみが正規表現である。
正規表現の定義に、次の項目を含めることもある:
ε {\displaystyle \varepsilon } は正規表現である。
Boost C++ライブラリによる実装。デフォルトでPerl互換の文法が使われるが、POSIXやECMAScriptなどの文法プロファイルを任意に選択することもできる。C++11規格にてBoost.Regexのサブセットが標準化された。
正規表現の起源は、言語学と、理論計算機科学の一分野であるオートマトン理論や形式言語理論にみることができる。20世紀の言語学では数理的に言語を扱う数理言語学が発展しその過程の一部として、また後者は計算のモデル化(オートマトン)や形式言語の分類方法などを扱う学術分野である。数学者のスティーヴン・クリーネは1950年代に正規集合と呼ばれる独自の数学的表記法を用い、これらの分野のモデルを記述した。
Unix系のツールに広まったのは、ケン・トンプソンがテキストファイル中のパターンにマッチさせる手段として、この表記法をエディタQEDに導入したことなどに始まる。彼はこの機能をUNIXのエディタedにも追加し、後に一般的な検索ツールであるgrepの正規表現へと受け継がれていった。これ以降、トンプソンの正規表現の適用にならい、多くのUnix系のツールがこの方法を採用した(例えば expr, awk, Emacs, vi, lex, Perl など)。
PerlとTclの正規表現はヘンリー・スペンサーによって書かれたものから派生している(Perlは後にスペンサーの正規表現を拡張し、多くの機能を追加した)。フィリップ・ヘーゼルはPerlの正規表現とほぼ互換のものを実装する試みとしてPerl Compatible Regular Expressions (PCRE) を開発した。
基本正規表現はBREとも呼ばれる。ほとんどの正規表現を利用する UNIXのユーティリティ(grepやsed)のデフォルトはこれである。
この文法では、ほとんどの文字はリテラル(機能を意味せず書かれたそのまま)に扱われる。つまり、ある文字はその文字にのみマッチする。例えば、正規表現「a」は文字「a」にマッチし、正規表現「(bc」は文字列「(bc」にマッチするなど。例外はメタ文字と呼ばれる。
古いバージョンのgrepは選言演算子「\|」をサポートしていない。
例
正規表現「.at」は文字列「hat」「cat」「5at」のような3文字の文字列にマッチする
正規表現「[hc]at」は文字列「hat」と「cat」にマッチする
正規表現「[^b]at」は文字列「bat」以外の「.at」でマッチする全ての文字列にマッチする
正規表現「^[hc]at」は行の最初にあるときだけ、文字列「hat」と「cat」にマッチする
正規表現「[hc]at$」は行の最後にあるときだけ、文字列「hat」と「cat」にマッチする
言語処理系やアプリケーションが正規表現をサポートしていない場合であっても、正規表現に必要な処理を提供する外部ライブラリを導入することで正規表現を使うことができる。以下にその一例を挙げておく。