はじめに
現在、正規表現はコンピュータで文字列の検索や置換、コンパイラの基盤等で広く使われていますが、元々は 1950 年代に数学者の Stephen Cole Kleene が用いた正規集合と呼ばれる独自の数学的表記法です。それを Ken Thompson がコンピュータに持ち込こみいくつもの UNIX コマンドに広まっていきました。そしてそれらの UNIX コマンドで使われていた正規表現を標準化したのが POSIX です。この記事では正規表現がコンピュータに持ち込まれ、そして POSIX で標準化するまでの歴史を紐解いてみました。
なお、コンピュータに持ち込む以前の話は「正規表現の"正規"とは何か気になったら正規表現の歴史を紐解くことになってしまった話」で大変わかりやすくまとめられておりとても参考になりました。
補足 この記事はシェルスクリプトで使う正規表現（各コマンドの正規表現の違い等）についてまとめた「シェルスクリプトの正規表現の詳細解説」におまけで書いていた歴史の話を単体の記事として独立し加筆修正したものです。
POSIX の正規表現 (BRE & ERE)
まず最初に POSIX で標準化されている正規表現がどういうものかを簡単に説明しておきたいと思います。POSIX では 基本正規表現 (BRE）と 拡張正規表現 (ERE）という ２ つの正規表現が標準化されています。"基本"と"拡張"という名前から、基本の BRE があってそれを拡張したのが ERE だと勘違いされがちですが、以下のように正規表現の基本構造が異なっており互換性がありません。
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| BRE |
^ $
|
. |
[ ] |
* |
\{ \} |
\( \) |
\1..\9
|
\ |
|
| ERE |
^ $
|
. |
[ ] |
* + ?
|
{ } |
( ) |
| |
\ |
- A: アンカー
- B: 任意の文字へのマッチ
- C: 特定の文字へのマッチ（ブラケット表現・文字クラス）
- D: 量指定子
- E: 量指定子（インターバル表現）
- F: 部分式・グループ
- G: 選択子
- H: 後方参照
- I: エスケープ文字
では、なぜ POSIX では互換性がない正規表現が 2 つも定義されているのか？その成り立ちを説明したのがこの記事の内容というわけです。
注意 これらは POSIX で標準化されている BRE と ERE です。GNU や macOS（BSD 含まず）では BRE と ERE の両方で足りないところを埋める形で拡張されています。macOS ではこの拡張された BRE と ERE を enhanced BRE と enhanced ERE と呼んでいます。
補足 POSIX では BRE と ERE の他に SRE（単純正規表現）というのも策定していたようですが、廃止されたものである事とあまり情報がないので省略します。SRE は互換性のために作られたものらしいのでおそらく細かい違いが有るのだと思いますが、私には BRE とほとんど同じに見えます。気づいた違いは SRE には POSIX 文字クラスに [:blank:] が含まれていないことぐらいです。
QED - 最初の正規表現
Ken Thompson によって 1968 年に Regular Expression Search Algorithm という論文が発表され、1970 年頃に QED - Text Editor に実装されたのがコンピュータにおける正規表現の始まりです。Ken Thompson は 正規表現だけではなく UNIX 初のシェルである Thompson シェル、C 言語の元となった B 言語、UTF-8 の発案者など UNIX 発展に大きく関わっている人で、最近では Go の開発にも関わっています。
当時の QED の PDF を見ると、最初の時点ですでに ^ $ . [ ] [^ ] * | () という正規表現に対応していたということがわかります。QED 正規表現を BRE と ERE と比較すると、両方の中間といえるような正規表現となっています。これが最初の正規表現です。
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| BRE |
^ $
|
. |
[ ] |
* |
\{ \} |
\( \) |
\1..\9
|
\ |
|
| QED |
^ $
|
. |
[ ] |
* |
( ) |
| |
\ |
||
| ERE |
^ $
|
. |
[ ] |
* + ?
|
{ } |
( ) |
| |
\ |
ed - 簡略化された正規表現
Ken Thompson はこの QED の正規表現を ed テキストエディタに追加します。この時に QED の正規表現のサブセットとして ^ $ . [ ] * \ のみを実装しました。「詳解 シェルスクリプト」には、当時のコンピュータの性能は遅くテキストエディタとしての用途では、これだけで十分だろうと判断したため Ken Thompson は実装しなかったというようなことが書かれています。（こちらも参照「An incomplete history of the QED Text Editor）
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| QED |
^ $
|
. |
[ ] |
* |
( ) |
| |
\ |
||
| ed 初期 |
^ $
|
. |
[ ] |
* |
\ |
||||
| ed 後期 |
^ $
|
. |
[ ] |
* |
\( \) |
\1..\9
|
\ |
||
| BRE |
^ $
|
. |
[ ] |
* |
\{ \} |
\( \) |
\1..\9
|
\ |
上記の通り ed テキストエディタの正規表現は純粋に QED テキストエディタの正規表現の簡略版であることがわかります。そして ed テキストエディタの正規表現は機能が追加されながら最終的に BRE の姿へと拡張されていくことになります。
Version 1 UNIX (1971) で登場した ed テキストエディタに実装された簡略化された正規表現には \( \) はありませんでした。これは Version 6 UNIX (1975) までに追加された事がわかります。この時、元々の ( ) ではなく \ を頭につけたエスケープシーケンスとして追加されました。なぜなら簡略化された正規表現では ( ) はただの文字だったからです。互換性を考慮するとただの文字である ( ) を別の意味に変えるわけにはいきません。そこでエスケープ文字が使われたわけです。エスケープ文字は特殊な文字をエスケープするものとしてすでに実装されていたので、これを利用すれば互換性を保ちながら拡張することが出来ます。
ということで ed テキストエディタに \( \) が追加されます。しかしこの時 | は実装されませんでした。このことから \( \) は元々は「グループ」としてではなくテキストエディタの置換機能でマッチした部分を参照するための全く別の機能として導入されたのではないかと推測しています。実際 BRE では「部分式」、ERE は「グループ」と名前が異なっています。
Version 6 UNIX の ed テキストエディタには「置換文字列」として正規表現にマッチした文字列全てを意味する & と \1..\9 による参照がサポートされています。しかし後方参照はまだ導入されていなかったようです（「置換文字列でのマッチ部分の参照」と「正規表現の後方参照」は異なる機能なので混同しないようにしてください）。おそらく置換文字列で参照できることで思いついたのでしょう。後方参照は次の Version 7 UNIX (1979) のed テキストエディタで導入されます。
この Version 7 UNIX は UNIX が商用化する前に広く配布された最後のリリースと言われており「最後の真のUNIX」と称する人もいるようです（参考）。Version 7 UNIX が登場するまでに UNIX には正規表現を利用する新しいコマンドが誕生します。それが Version 4 UNIX (1973) の grep と、 ersion 7 UNIX (1979) の expr と sed です。これらも ed コマンドと同様の正規表現を実装しています。また BSD 系 Unix では more (1978) や Bill Joy が開発した ex テキストエディタ (1978) とその後継の vi テキストエディタ (1979) で同様の正規表現が採用されます。
また「詳解 シェルスクリプト」 P49 によると、この頃に UNIX の世界の正規表現に \< と \> （単語の前と後にマッチ） というエスケープシーケンスが導入されたようです。\< と \> を GNU 拡張と解説しているものを見かけますが、実際には UNIX で導入されたものであり、例えば Solaris 10 の /usr/bin/grep でも使用することが出来ます。
egrep - 拡張された正規表現
さて、一方で Version 7 UNIX では新しく egrep というコマンドが登場します。これはその名の通り、拡張された正規表現を使用する grep で、簡略化された正規表現ではなく QED の最初の正規表現がベースとなっています。新しく作成したコマンドであるため互換性を気にする必要はなく、素直に正規表現の基本構造が拡張（+ と ? が追加）されました。
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| QED |
^ $
|
. |
[ ] |
* |
( ) |
| |
\ |
||
| egrep |
^ $
|
. |
[ ] |
* + ?
|
( ) |
| |
\ |
||
| ERE |
^ $
|
. |
[ ] |
* + ?
|
{ } |
( ) |
| |
\ |
これが後に awk にも採用され 最終的に ERE として標準化されることになります。ちなみに egrep の開発者の Alfred Aho は awk の開発者の一人でもあるため awk に egrep の正規表現 （ERE) が採用されるのは自然な流れです。
インターバル表現 {m,n} の登場
さて、ここまでの話の中で { } はまだ登場していません。{ } が登場したのは、Version 7 UNIX のlex (ERE) からのようです（参考 "either iteration or definition" で検索）が、この時点では ed、grep、sed、expr、egrep、awk のいずれにも実装されていません。
「詳説 正規表現 第 3 版」の「3.1.1.2 grep の発展」 (P84) によると AT&T が lex から \{min,max\} 記法を取り入れたと書かれています。System III のソースコード にはそれらしきものは見つかりませんが SunOS 4.1.3 - man grep にはあるようなので、おそらく System V の SVR1 (1983) から SVR4 (1988) の間に grep （やその他のコマンド？）に導入されたようです。
しかしこの時点（POSIX 標準化前）の egrep と awk には取り入れられませんでした。おそらく + と ? で十分だったことと互換性上の理由でしょう。エスケープシーケンスであるegrep では { } はただの文字ですからこの意味を変えるわけには行きません。
Solaris 10 の歴史的な（POSIX に準拠してない方の）/usr/bin/grep は \{m,n\} に対応していますが /usr/bin/egrep は {m,n} に対応していないので辻褄は合います。
POSIX での標準化
ここまでで ed コマンドを起点とする「簡略化された正規表現」の流れと egrep コマンドを起点とする「拡張された正規表現」の２つの流れを見てきました。これが BRE と ERE の仕様へとつながっていきます。
BRE に関しては（少なくとも） grep にインターバル表現 {m,n} が導入されており、実際の UNIX の実装がほぼそのまま BRE の仕様となったように思えます。問題は ERE です。POSIX 策定時点で egrep にも awk にも {m,n} は追加されていません。その上正規表現の基本構造を変えるため互換性上の問題が発生します。つまり ERE の仕様に {m,n} を含める理由が見当たりません。
どうやらこれは歴史的な実装の動作ではなく POSIX が追加した仕様のようです。Rationale: Base Definitions - A.9 Regular Expressions には次のように書かれています。
The interval expression, "{m,n}", has been added to EREs. Historically, the interval expression has only been supported in some ERE implementations. The standard developers estimated that the addition of interval expressions to EREs would not decrease consensus and would also make BREs more of a subset of EREs than in many historical implementations.
補足 ここでいう一部の歴史的な ERE の実装でのみ {m,n} がサポートされていたというのはおそらく lex のことでしょう。
もし {m,n} が BRE だけにしかなければ、"拡張"正規表現である ERE よりも"基本"正規表現である BRE の方が機能が多いじゃんと言われてしまいます。そういう理由もあり POSIX の開発者は {m,n} を ERE に追加しても合意は得られると考えたようです。（lex が {m,n} を実装しているから POSIX で標準化されたとも考えられますが、lex は POSIX の必須コマンドではなくオプションコマンドです。これだけを理由に ERE に {m,n} に組み込むのは少し理由が弱いと思います。）
おそらく同様の理由で BRE にしか実装されていなかった後方参照も ERE に追加しようという提案がされたのですが、こちらは合意が得られなくなりそうだということで却下されています。
It was suggested that, in addition to interval expressions, back-references ( '\n' ) should also be added to EREs. This was rejected by the standard developers as likely to decrease consensus.
今でこそ ERE は他の言語の正規表現と互換性がある文法として広く使われていますが、POSIX 策定当時は BRE の方がまだ多く使われていたのでしょう。そのため ERE に互換性問題を引き起こす {m,n} を取り込んでもさほど大きな問題にはならなかったのかもしれません。問題になりそうなのは実質 awk と grep -E (egrep) だけですが、egrep は POSIX で標準化されたものの当時の時点ですでに非推奨とされており、同等の機能を持つ grep -E への移行が予定されていたので、多少の非互換性は許容できたと考えられます。
残る問題は awk だけですが、結局 awk の {m,n} 対応はなかなか進みませんでした。gawk は 2010 年から、nawk に関しては 2020 年頃（macOS 版の nawk は 2007 年頃）からようやく対応しましたが、mawk に至っては未だに対応していません。互換性問題を引き起こすものであるため慎重になるのは当然だと思います。それでも nawk は対応されましたし、残っているのは mawk だけですから、他の awk との互換性のためにもいずれは導入されるでしょう。
このような問題を抱えつつも、多くの UNIX コマンドで使われていた正規表現は POSIX によって基本正規表現 (BRE) と拡張正規表現 (ERE) という 2 つの正規表現として標準化されることになります。（とは言え実は各コマンドによって細かい違いが残っていたりするのですが・・・）
まとめ
1970 年にコンピュータの世界に持ち込まれた正規表現はゆっくりと UNIX のコマンドに広まっていきました。そして 1986 年頃に POSIX が発表され 1988 年（シェルとユーティリティは 1992 年）に標準化されます
シェルスクリプト、特に POSIX 準拠や Linux と macOS の両対応のシェルスクリプトを書いていると、各コマンドによって正規表現の文法が違っていて面倒なのですが、歴史的を紐解くとこのような事情があるのだということがわかります。これで少しは正規表現が動かないというイライラも軽減できるかもしれません。
さてここで一つ嬉しいお知らせがあります。2022 年後期に登場予定の次期 POSIX (Issue) 8 では sed の -E (ERE) オプションが標準化がされます。（詳細は「sedで拡張正規表現 (ERE) を使う時は -r ではなく -E オプション（POSIX Issue 8 準拠）を使いましょう」を参照）
これでシェルスクリプトで正規表現を使うコマンドは awk、grep -E、sed -E のよく使われる 3 つのコマンドが POSIX 準拠で ERE が使えることになります。ERE がつかないコマンドとして expr がまだ残っていますが、expr は bash の [[ ... ]] や POSIX シェルの $(( ... )) で代替可能であるため、そこまで必要はないでしょう。つまりこれからシェルスクリプトの正規表現は安心して ERE だけを使って良くなるということです。長い UNIX コマンドと POSIX の正規表現の歴史はようやく BRE を卒業して ERE メインへと移行することでしょう。
おまけ POSIX 後 - Perl への採用
さて、ここまでは UNIX コマンドと POSIX の正規表現の話でしたが、POSIX 策定時期と時を同じくして 1986 年に Henry Spencer が C 言語で書いた正規表現パッケージが登場します。「詳説 正規表現」によるとこれは、他のプログラマが自由に自分のプログラムに組み込めるようになっており、そのようなものは当時としては初めてだったと書かれています。この正規表現パッケージは Tcl、MySQL、PostgreSQL など多くのソフトウェアで使われることになりますが、その中で特に重要なものとして Perl への採用があります。Perl 1.0 (1987) では正規表現ライブラリに James Gosling の Emacs のコードが使われていましたが Perl 2.0 (1988) では Henry Spencer の正規表現パッケージを大幅に拡張したバージョンに置き換わりました。正規表現は Perl の進化と共にさらに大幅に改良されていき、Perl 互換の正規表現はプログラミング言語の世界で広まっていくのですが、その歴史については他の記事に託したいと思います。