はじめに

https://www.oreilly.co.jp/books/9784873113593/
詳説正規表現第3版を読んで、ざっと内容をまとめました。この記事で興味が湧いたら是非読んでみてください。
ちゃんと確認してないので、typoなどが合ったらバシバシ編集リクエストいただけるとmm

１章正規表現入門

正規表現は、強力で柔軟、かつ効率的なテキスト処理の鍵を握る存在だ。
1章はegrepを例に基本的な正規表現の文法を紹介している。

egrepのメタ文字

行頭と行末 `^`と`$`記号

「cat」という正規表現は行内のあらゆる位置にあるc・a・tにマッチするが、「^cat」は、c・a・tが行頭にあるときのみマッチする。
つまり、「^」はアンカーとして（正規表現のその他の部分の）マッチを実質的に行頭に固定するために使われている。
同様に、「cat$」は、行末がscatになっている行のように、行の末尾のc・a・ｔだけにマッチする。

文字クラス

複数の文字のどれか一つとマッチさせる `[…]`

grayという文字にマッチさせたいが、greyという文字にもマッチさせたいとする。このようなときは 文字クラス を使う。
「e」という正規表現はeだけ、「a」という正規表現はaだけにしかマッチしないが、「[]」という正規表現は両方にマッチする。前述の問題は「gr[ae]y」と解ける。
文字クラスの中で 文字クラスメタ文字 の「-」（ダッシュ）を使うと文字の範囲を示すことができる。
例えばHTMLタグの「<H1>,<H2>,<H3>」などにマッチさせたい場合、「<H[1-6]>」とする。
文字クラスメタ文字の「-」で注意しなければいけないのは

文字クラス内だけでしかメタ文字と扱われない
文字クラスの先頭にある場合、範囲の指定ができないので、メタ文字として扱われない

の２点である。

否定文字クラス　`[^…]`

「[…]」ではなく「[^…]」をつかうと、文字クラスは、リストに含まれていない任意の文字にマッチするようになる。例えば「[^1-6]」は1から6以外の任意の１文字にマッチする。

任意の１文字にマッチするドット `.`

メタ文字の「.」（ドットとかポイントとか呼ばれることが多い）は、任意の文字にマッチする文字クラスの略記法である。例えば、03/19/76、03-19-76、03.19.76、などの日付の表記を探したいときに役立つ。しかし、曖昧が故に'lottery numbers: 19 2 03319 76 39'（宝くじの番号）などにもマッチしてしまうので注意が必要である。

複数の部分表現のどれかにマッチさせる（選択） `|`

「|」は、”または”という意味の非常に便利なメタ文字である。これを使うと、複数の正規表現を組み合わせて、これらのどれかとマッチする１つの正規表現を作ることができる。例えば「Bob」と「Rovert」は別々の正規表現だが、「Bob|Rovert」はどちらかにマッチする１つの正規表現である。このように結合された部分正規表現（部分式）は 選択肢 と呼ばれる。

大文字と小文字の違いを無視する　`-i`オプション

egrepのコマンド行オプションの「-i」を指定すると、大文字と小文字を区別をしないマッチをせよという意味になる。これを指定すると「from」という正規表現は「from」・「From」の両方に関係なくマッチさせることができる。

単語の境界 `\<`と`\>`

egrepは一部のバージョンで制限された形ではあるが、単語の認識をサポートしている。つまり、単語の境界（単語の先頭と末尾）にマッチさせることができる。
この機能をサポートしているバージョンなら（全てのegrepがこれをサポートしているわけではない）、「<」と「>」というメタ文字を使える。「<cat>」という正規表現の文字通りの意味は、”単語の先頭の位置を見つけることができ、c・a・tが続き、その後に単語の終わりの位置が続いたらマッチする”ということになる。より自然にすると”cat”という単語を探せと言うことになる。

量指定子

「?」、「+」、「*」の３つのメタ文字は、それぞれがくっついている要素の繰り返しの方法を支持するものなので、 量指定子 と呼ばれる。

オプション　`?`

メタ文字の「?」（疑問符）は、オプション（あってもなくてもよい）という意味である。
colorかcolourにマッチする正規表現を考えてみる。このようなときは「colou?r」という正規表現でどちらにもマッチさせることができる。

**その他: 繰り返し `+` `*`**

「+」（プラス記号）は”直前の要素の１回以上の繰り返し”という意味で、「*」（アスタリスク（書籍内ではスター））は”直前の要素の０回を含む繰り返し”という意味になる。

マッチの範囲指定: 範囲指定 `{min, max}`

egrepの一部のバージョンでは、「…{min,max}」という形で、繰り返しの最小限と最大限を指定するためのメタ文字列をサポートしている。このメタ文字は 範囲指定繰り返し制御 (quantifier)と呼ばれている。

例えば「…{3,12}」は可能であれば12回マッチするが、3回あればよしとする。

括弧と後方参照 `\1, \2, \3 …`

後方参照 とは、正規表現内ですでにマッチしたテキストと同じものがもう一度現れたときに、それにマッチすることができるという正規表現の機能である。
例えば「<the +the>」という正規表現の「the」の代わりに「[a-zA-Z]」のような"単語全般"にマッチさせたいとする。この場合の正規表現は「<([a-zA-Z]+) +\1>」となる。

後方参照をサポートするツールはマッチしたテキストを全て"覚えて"おり、マッチの1番目,２番め,３番目,…　はそれぞれ「\1」,「\2」,「\3」, … と表される。

大脱走--偉大なるエスケープ `\`

メタ文字の前に「\」を置くとその文字自体にマッチする正規表現になる。

基礎を発展させる

言語の多様性

これまで、egrepの殆どのバージョンがサポートする正規表現機能の多くを説明してきた。他にも機能はあり、その一部は全てのバージョンがサポートしているわけではない。

正規表現の目的

マッチしたテキストに 何かの処理を加える （ファイルへの保存、追加、置換など）つもりなら、どの数字がマッチしたのかが重要な意味を持つ。

正規表現の用語

”regex”

”regular expression”の略。プログラムの中で実際にマッチを試みる仕事をする部分のことを”regex engine”と呼ぶ。

”マッチ”

正規表現が文字列に”マッチする”と言うとき、実際には文字列の一部にマッチしているのである。
厳密に言えば、正規表現の「a」はcatにマッチするのではなく、catの中のaにマッチしているのである。

”メタ文字”

ある文字列がメタ文字かどうかは、正規表現のどこで使われているのかによって決まる。
例えば「*」は文字クラスの外でかつ直前に「\」が置かれていない場合のみメタ文字である。

”方言”

様々なツールが異なる目的のために正規表現を使っており、それぞれのサポートするメタ文字の種類やその他の機能はまちまちになり得る。
1990年代後半に、プログラミング言語のPerlが特に表現力の高い方言をサポートするようになって、その能力が広く認められると、他の言語も競ってPerl風の正規表現をサポートするようになった。

”部分式”

”部分式”または”部分正規表現”という言葉は、単純に大きな正規表現の一部をさすが、カッコ内の正規表現や「|」の選択肢を指すことも多い。

１章まとめ

egrep のメタ文字のまとめ

単一の文字にマッチするメタ文字

メタ文字	名前	マッチ
.	ドット	任意の１文字にマッチする。
[…]	文字クラス	リスト中の任意の１文字にマッチする。
[^…]	否定文字クラス	リストに含まれていない任意の１文字にマッチする。
\char	エスケープ文字	charがメタ文字であるか、エスケープ文字との組み合わせに特別な意味がなければ、リテラルのcharにマッチする。

”繰り返し” を提供するために付加されるメタ文字：量指定子

メタ文字	名前	マッチ
?	疑問符	１つは認められるが、それはオプション。
*	スター	任意の数が認められるが、それらはみなオプション。
+	プラス	少なくとも１つは必須だが、それ以上はオプション。
{min,max}	範囲指定	min回が必須、max回まで許容（オプション）

位置にマッチするメタ文字

メタ文字	名前	マッチ
^	キャレット	行の先頭の位置にマッチする。
$	ドル記号	行の末尾の位置にマッチする。
\<	語の境界	語の先頭の位置にマッチする。
\>	語の境界	語の末尾の位置にマッチする。

その他

メタ文字	名前	マッチ
｜ (エスケープの仕方がわからなかったので全角)	選択	区切っている正規表現のどれかにマッチする。
(…)	括弧	選択の範囲を限定する。量指定子の対象となるグループを作る。後方参照のためにキャプチャ(マッチしたテキストを記憶)する。
\1, \2, …	後方参照	１番目、２番め、…… のカッコ内がマッチしたテキストと同じものにマッチする。

２章初心者向けのサンプル

この章では実際に正規表現を使ってPerlの簡単なサンプルを作っていくが、サンプル自体が気になる方は書籍を参考にしてください。

キャプチャなしの括弧: `(?:…)`

通常の「(…)」にマッチしたテキストはキャプチャされて、\1などに格納される。この変数を使わないのであれば、この変数へのテキストの格納というオーバーヘッドはなくせないのだろうか。
Perlなどの新しい正規表現は、そのための方法を提供している。グループ化してキャプチャーする「(…)」ではなく、「(?:…)」という特殊な記法を使えば、グループ化はするがキャプチャはしない。

何のメタ文字なのか

殆どの言語と同様に、Perlの文字列にも独自のメタ文字があり、それは正規表現のメタ文字とは全く別物である。例えば、文字列メタ文字の\tを使えば文字列にタブを挿入できるが、正規表現メタ文字の「\t」を使えば、タブにマッチする要素を正規表現に挿入できる。

\tのような単純なものであれば、それほど重要性を感じないかもしれないが、これから様々な言語やツールを見ていくときには、どのメタ文字がどの状況で使われているのかを正確に知っておくことが重要である。

メタ文字の概念は、正規表現の専売特許ではない。シェルとダブルクォート文字列のように、解釈には複数の文脈が関わってくることが多い。様々なコンテキスト（シェル、正規表現、文字列、その他）、それぞれのメタ文字、それらの相互関係は、Perl、PHP、Java、Tcl、GNU　Emacs、awk、Pythonなどの高度な言語を学び、使うようになるにつれて、どんどん重要度を増してくる。

役に立つ略記法

略記法	意味
\n	改行文字
\r	復帰文字
\s	任意の”空白文字”（スペース、タブ、改行、改ページなど）にマッチ
\S	「\s」以外のすべての文字
\w	「[a-zA-Z0-9_]」（単語にマッチさせるには「\w+」というかたちで使うと便利）
\W	「\w」以外のすべての文字（つまり、「[^a-zA-Z0-9_]」）
\d	「[0-9]」（つまり、数字）
\D	「\d」以外のすべての文字（つまり、「[^0-9]」）

先後読みによって数値にカンマを付け加える

”The US population is 298444215”
のような文字列は、英語圏の人々にとっては”298,444,215”という表示のほうがわかりやすい。カンマを挿入する位置とは”右側に３の倍数個の数字があり、左側に何らかの数字がある位置”のことだと考えを整理して、先後読みという機能を使えば解決できる。

先後読み `(?=…)` `(?<=…)`

先後読みの一つである先読みは、テキストの先の方（まだ読んでいない右の方）を覗き込んで、部分正規表現がマッチするかどうかを調べ、マッチするようなら正規表現要素として成功ということになる。肯定の先読みは「(?=)」という特殊なシーケンスによって指定する。例えば、「(?=\d)」は次が数字になっている位置で成功する。

先後読みには、テキストの後ろの方（もう読んだ左の方）を振り返る後読みと言うものもあり、「(?<=…)」という特別なシーケンスで指定する。例えば「(?<=\d)」は、左側に数値がある位置（つまり数値の後ろの位置）で成功する。

否定の先後読み `(?!…)` `(?<!…)`

否定の先読みと否定の後読みもある。これらは部分式がマッチしない位置で成功する。
先程の問題は次の正規表現で解決できる

s/(?<=\d)(?=(?:\d\d\d)+(?!\d))/,/g

先後読み一覧表

タイプ	正規表現	囲まれている部分式が成功する条件
肯定の後読み	(?<=…)	部分式が左側にマッチするときに成功する
否定の後読み	(?<!…)	部分式が左側にマッチしないときに成功する
肯定の先読み	(?=…)	部分式が右側にマッチするときに成功する
否定の先読み	(?!…)	部分式が右側にマッチしないときに成功する

３章正規表現の機能と方言

この章では正規表現の歴史と、各言語の正規表現の方言の違いを広く取り上げている。

正規表現のスケッチ

この項のポイントは、正規表現に対する理解に彩りを添え、何故正規表現が”今ある姿”になったのかを感覚的につかむことである。基本的に軽い読み物として読んでいただきたい。

正規表現の起源

正規表現の種は、1940年代はじめに、Warren McCullochとWalter Pittsという２人の神経生理学によってまかれた。彼らは、神経系がニューロンレベルで働く仕組みのモデルを開発した人々である。その数年後、数学者のStephen Kleeneが正則集合と命名した代数で、これらのモデルを公式に記述したときに正規表現は現実のものとなった。彼は、正則集合を表現するための簡単な記法を考案し、それを正規表現と名付けた。

1950年代から1960年代にかけて、理論数学者のグループが正則表現を深く研究した。Robert Constableは、数学の専門家向けに優れた概論を書いた。

もっと早い段階の業績が存在する形跡は有るが、私が実際に見つけた限りでは、コンピュータにおける正規表現の利用について最初に公刊された論文は、Ken Thompsonが1968年に書いた「Regular Expression Search Algorihtm」である。彼は、この中でIBM 7094オブジェクトコードを生成する正規表現コンパイラについて書いている。この研究が彼のqedエディタを導き、さらにqedがUnixのedエディタの基礎となった。

edの正規表現は、qedのものと比べて見劣りのするものだったが、技術分野以外で初めて広く普及した正規表現である。edには、編集中のファイルの中で、与えられた正規表現にマッチした行を表示するコマンドがあった。このコマンドは、”g/Regular Expression/p”というもので、"Global Regular Expression Print"と読む。この関数はとても役に立ったので、grepという独自のユーティリティになった（egrep---拡張grep---はgrepを基礎として作られたものである）。

POSIX--標準化の試み

POSIX(Portable Operating System Interface)は、オペレーティング・システム間での移植性を確保するために、1986年に発表された広範囲にわたる標準規格である。
POSIXは、混沌に陥った正規表現を再構成するために、各種の方言を**基本正規表現(BRE)と拡張正規表現(ERE)**の２つに分類している。

POSIXの正規表現規定の概要

正規表現の機能	BRE	ERE
., ^, $, […], [^…]
"任意個の"の量指定子	*	*
+,?量指定子		+,?
範囲	\{min,max\}	{min,max}
グループ化	$…$	(…)
()に対する量指定子の適用
後方参照	\1~\9
選択

一見してわかる方言の違い

機能	現代のgrep	現代のegrep	GNU Emacs	Tcl	Perl	.NET	Sunのjavaパッケージ
., ^, $, […]
?,+,｜（エスケープ効かないので大文字）	?,\+,\｜	?,+,｜	?,+,\｜	?,+,｜	?,+,｜	?,+,｜	?,+,｜
グループ化	$…$	(…)	$…$	(…)	(…)	(…)	(…)
(?:…)
単語境界		\<…\\>	\<…\\>, \b, \B	\m,\M,\y	\b,\B	\b,\B	\b,\B
\w,\W
後方参照
: サポート有り

上のような表を見るときは、以下のポイントを考えると良い。

スター（*）などの量指定子はカッコで囲まれたものも対象にできるのか。
ドット（．）は改行にマッチするのか。否定文字クラスは改行にマッチするのか。どちらかはNULにマッチするのか。
行アンカーは本当に行アンカーなのか（つまり、ターゲット文字列に埋め込まれているかもしれない改行を認識するのか）。また、行アンカーは基本要素のメタ文字として扱われているのか、それとも、正規表現の特定の位置でしか有効に使えないのか。
文字クラス内でエスケープは認識されるのか。文字クラスで認められる文字、認められない文字としては他に何があるのか。
括弧は入れ子にすることができるのか。その場合、どの程度の深さまで許されるのか（あるいは、そもそも何組のカッコを使ってもよいのか）。
後方参照がサポートされている場合、大文字と小文字を区別しないマッチを要求したときに、後方参照は正しくマッチするのか。後方参照は、微妙な条件のもので適切に機能するのか。
\123のような8進エスケープは認められているのか。その場合、後方参照との構文上の衝突をどのように解決しているのか。１６進エスケープはどうか。8進及び16進エスケープをサポートしているのは本当に正規表現エンジンなのか、ユーティリティの別の部分なのか。
\wは英数字だけにマッチするのか、他にもマッチする文字があるのか。\wと単語境界のメタ文字は、”単語を構成する文字”がどれかということに関して解釈が一致しているのか。ロケールやUnicodeをサポートしているのか。

正規表現処理のインターフェース

プログラムの正規表現を利用するための実装は統合型、手続き型、オブジェクト指向型の３種類のインターフェースがある。

統合型インターフェース

Perlの統合型アプローチの例

if ($line =~ m/^Subject: (.*)/i) {
    $subject = $1;
}

手続き型インターフェース

PHPは手続き型のアプローチで作られている。

if (preg_match('/^Sunject: (.*)/i', $line, $matches))
    $Subject = $matches[1];

オブジェクト指向型インターフェース

Pythonはオブジェクト指向型のアプローチを取る。

import re;
…
R = re.compile("^Subject: (.*)", re.IGNORECASE)
M = R.search(line)
if M:
    subject = M.group(1)

よく使われるメタ文字とその機能

書籍参照（あとでまとめますmm）

４章正規表現のメカニズム

正規表現エンジンのタイプ

正規表現エンジンには、2つの根本的に異なるタイプがある。１つはDFAと呼ばれ、もう１つはNFAと呼ばれる。

主要なツールの正規表現エンジンのタイプ

エンジンのタイプ	プログラム
DFA	awk（殆どのバージョン）、egrep（殆どのバージョン）、flex、lex、MySQL、Procmail
従来型NFA	GNU Emacs、Java、grep（殆どのバージョン）、less、more、.NET言語、PCREライブラリ、Perl,PHP(３種類の正規表現スイート)、Python、Ruby、sed（殆どのバージョン）、vi
POSIX NFA	mawk、Mortice Kern Systemsのユーティリティ群、GNU Emacs（必要な場合）
NFA/DFAのハイブリット	GNU awk、GNU grep/egrep、Tcl

エンジンのタイプのテスト

エンジンのタイプは、エンジンが幾つかのテスト正規表現をどのように処理するかを見るだけで判断できることが多い（もし違いが見分けられなければ、そもそもその違いに大きな意味はない）。

従来型NFAか否か

まず、最小量指定子（*?、+?、??、{num,num}?）がサポートされているなら、ほぼ確実に従来型NFAだと言って良い。
DFAでは最小量指定子を実装できないし、POSIX NFAではこのような機能は無意味である。

しかし、念のために、'nfa not'という文字列に'nfa|nfa not'という正規表現を適用してみて、nfsにしかマッチしないようであればそれは従来型NFAである。'nfa not'という文字列全体がマッチするなら、POSIX NFAかDFAのどちらかである。

DFAかPOSIX NFAか

次のegrepコマンドのように、「X(.+)+X」という正規表現を'=XX========================='という形の文字列に適用する。

終わるまでに長い時間がかかるようになら、それはNFAである（前のテストの結果、従来型NFAでないことがわかっているなら、それはPOSIX NFAである）。すぐ終わるようなら、DFAか何らかの高度な最適化が施されたNFAだろう。スタックオーバーフローとかマッチに時間がかかるので異常終了したというような警告メッセージが表示されるようなら、それはNFAである。

マッチの基本原則

サンプルについて

この章全体の中で、正規表現全般に当てはまる原則は次の２つしか無い。

最初にマッチしたもの（最も左にあるもの）が優先される。
標準の量指定子（「*」、「+」、「?」、「{m,n}」)は欲張りである。

原則１: 最初にマッチしたものが優先される

この原則は、文字列内で最も早く始まる（最も左にある）マッチが、それよりも後ろのどのマッチよりも優先されることを表している。

この原則を知らないと、マッチの結果に驚くことがある。例えば、次の文字列に対して「cat」という正規表現を適用するとどうなるだろうか。

The dragging belly indicates your cat is too fat

マッチとして報告されるのは行の終わりの方のcatという単語ではなく、indicatesの中の３文字である。単語のcatもマッチする可能性を秘めているが、indicatesのほうが文字列先頭に近い方にあるので、マッチするのはこちらになる。
置換のような用途では、マッチする位置がとても重要な意味を持つ。

”トランスミッション”と前進

この原則は、ギアを調整しながらエンジンと運転装置をつなぐ車のトランスミッションのようなものだと考えるとわかりやすい。

トランスミッションの主な仕事：前進

エンジンが文字列の先頭でマッチを見つけられない場合、文字列の次の位置、更に次の位置、更に次の位置へと正規表現エンジンを先に進めてマッチを試みさせるのは、トランスミッションの仕事である。

DFAエンジンにはない括弧、後方参照、最小量指定子

DFAエンジンは、キャプチャ付き括弧（及び後方参照や$1などの機能）や最小量指定子を、構造上、サポートすることができないのである。

原則２: 標準の量指定子は欲張りである

量指定子は出来る限り長い文字列にマッチしようとする。

標準の両指定子も、必要であれば、許容されている最大限の繰り返し数よりも少ない回数で満足することは有るが、上限が許す限りできるだけ多くの回数マッチしようとすることに変わりはない。
例えば「\b\w+s\b」という正規表現を使って、'regexes'のように's'で終わる単語にマッチさせようとする時、「\w+」単独なら単語全体にマッチするところだが、全体のマッチを優先させて'regexes'の部分だけマッチする。

欲張りになりすぎる時

「^Subject: (.*).*」という正規表現は２つ目の「.*」には常に何もマッチしない。最初の「.*」が非常に欲張りなので、タイトルに含まれる全てのテキストにマッチして、　2番目の「.*」には何も譲らない。

正規表現主導かテキスト主導か

２つのエンジンのタイプは、文字列に正規表現を適用するためのアルゴリズムの根本的な違いを反映したものだ。NFAは”正規表現主導”、DFAは”テキスト主導型”ということができる。

正規表現主導型のNFAエンジン

或るエンジンが'…tonight…'というテキストに対して「to(nite|knight|night)」をマッチさせる場合について考えてみる。
「to(nite|knight|night)」の最初の要素は「t」であり、これはターゲット文字列の't'に行き当たるまで繰り返しマッチ不成功になる。先頭の「t」がマッチすると、次の文字に対して「o」がチェックされ、これがマッチするようなら、更に次の「(nite|knight|night)」に制御が移る。人間であれば３番目の選択肢でなければマッチしないことがわかるが、正規表現が駆動するエンジンは、実際にチェックしてみるまで、その結論に達することができない。
最初の選択肢である「nite」のテストは、先ほどと同じように１度に１要素の照合である。つまり「n」、その次に「i」、次に「t」、最後に「e」がマッチするかどうかを試す。制御が正規表現内の要素から要素に移っていくので、”正規表現主導型”と呼ばれる。

NFAエンジンの制御上の利点

NFAエンジンは正規表現が駆動しているので、自分がやりたいと思うことをかなり自由に作り込むことができる。

テキスト主導型のDFAエンジン

正規表現主導型のNFAエンジンとは対照的に、DFAエンジンは、文字列の走査中、”現在可能性のある”全てのマッチを管理している。tonightのサンプルでは、tを検出したエンジンは、現在の進行中のリストにマッチ候補を追加する

文字列内	正規表現内
…t↑onight	マッチ候補「t↑o(nite｜knight｜night)」

その後の文字を１つ走査するたびに、可能性のあるマッチ候補のリストは更新される。それから何個かの文字がっマッチした後の状態は次のようになっている。

文字列内	正規表現内
…toni↑ght	マッチ候補「to(ni↑te｜knight｜ni↑ght)」

マッチ候補は2つになっている(knightがマッチする可能性は排除されている)。そして、次のgを操作すると、３番目の選択肢以外の可能性はなくなる。更に、hとtが操作されると完全なマッチを検出し、成功を返すことができる。

この方法は、テキストから操作された1つ１つの文字がエンジンを制御しているので、”テキスト主導型”のマッチと呼べるだろう。

我々ユーザーにとっての結論

NFAは正規表現主導という性質を持つため、エンジンがどのようにマッチを試みるかについての細部が非常に重要である。tonightの例で言えば、正規表現が次のどれかのように書かれてれば、恐らく浪費される仕事量は減っていただろう。

「to(ni(ght|te)|knight」
「tonite|toknight|tonight」
「to(k?night|nite)」

DFAはこれとは全く対照的である。DFAでは、エンジンが全てのマッチを同時並行的に管理しているので、表現の見かけ上の違いは全体に影響を与えない。

バックトラック

NFAエンジンは、部分式や要素を順番に見ていき、同等の可能性を持つ２つのオプションの中でどちらかを選ばなければならなくなると、片方を選んだ上で、後で必要になったときにそこに戻れるように、もう片方も覚えておく。

どのコースを選んだとしても、それが成功して正規表現の残りの部分も成功したら、マッチは終了する。しかし、正規表現の残り部分で不成功が起きると、正規表現エンジンは最初に選択を行ったところまでバックトラックし、別のコースに進んでマッチの試行を継続する。NFAはこうして正規表現から作られる全ての順列を試してみる（少なくとも、マッチが見つかるまで必要な限り）。

バックトラックに関する２つの重要なポイント

1. どの選択肢を最初に試すべきか

量指定子の対象となっている要素のように、選択すべきことが”マッチを試行する”か”試行しない”かのどちらかである場合、
最大量指定子では”マッチを試行する”をまず選び、最小量指定子では”マッチを試行しない”をまず選ぶ。これに例外はない。

2. 保存されている選択肢の中からどれを使うべきか

要素の局所的なマッチ不成功によってバックトラックを強いられたときに次に試すべきなのは、最後に保存した選択肢である。選択肢はLIFO（後入れ先出し）で使われる。

保存ステート　

マッチを再開できる場所のことを保存ステート（状態）と呼ぶ。

アトミックグループ `(?>…)`

「(?>…)」の中でのマッチは通常通りに行われるが、構文内でのマッチが成功して構文の外に出られる状態になると（つまり、閉じ括弧を通り過ぎようとするとき）、カッコ内で蓄積された全ての保存ステートは捨てられる。

DFAの処理効率

テキスト主導型のDFAは、バックトラックの持つ効率の悪さを回避するための非常に優れた方法である。DFAは、全ての可能性のあるマッチを同時に管理することで、そのスピードを実現している。

DFAエンジンは、初めて正規表現を操作した後、マッチ試行を開始するまでの間に、時間とメモリを特別に割いて、NFAよりも正規表現を徹底的に（そして全く異なる形で）分析する。実際にマッチ試行を開始したときには、”今これこれの文字を読んでいるのなら、可能性のあるマッチの中のこれとかアレの一部になっているはずだ”ということが書かれた内蔵マップが出来上がっている。エンジンは、このマップを作るために、場合によってはかなりの時間とメモリが必要になることがあるが、特定の正規表現のためにそのようなマップを作ってしまえば、その成果は無限のテキストに適用できる。

正規表現を初めて操作したときに行われる仕事（１つの正規表現につき１回だけ発生するオーバーヘッド）は、正規表現のコンパイルと呼ばれる。

NFAとDFAの比較：まとめ

実行前のコンパイルの違い

NFAのコンパイルのほうが、一般に高速で必要なメモリも少ない。従来型NFAとPOSIX NFAとでは、コンパイルに本質的な違いはない。

マッチスピードの差

DFAのマッチスピードは、一般に正規表現の内容とは無関係である。

従来型NFAは、マッチなしの結論を得るためには、正規表現から作れる全ての順列を試さなければならない。NFAのマッチ試行には無限の時間がかかることがある。

POSIX NFAは最長のマッチを見つけるために、正規表現から作れる全ての順列を毎回試さなければならない。だからマッチが成功するまでにかかる時間は失敗を確かめるためにかかる時間と同じになる。POSIX NFAでは、効率の良い正規表現を書くことが特に重要になってくる。

マッチするものの違い

DFAは最左最長マッチ（最も左で最も長くマッチしたもの）を返す。従来型NFAは最左最長マッチを返すこともあれば、それ以外のものを返すこともある。

機能の違い

NFAエンジンは、DFAがサポートできない様々な機能をサポートできる。

後方参照と、マッチ後情報
先後読みなどのゼロ幅マッチ
最小量指定子と早い者勝ちの選択
絶対最大量指定子

5章　正規表現の実践的なテクニック

この章はサンプルを作ることで実践的なテクニックを紹介している。
実際に手を動かしたほうが良いので書籍を参考にしてください。割愛します。

6章効率の良い正規表現の作り方

バックトラックの意味を強調しながら効率の良い正規表現とは何かを紹介している。

よく見られる最適化

賢いエンジンは、ユーザーが求める結果を高速に生成するために、様々な最適化テクニックを駆使している。通常、最適化は次の２種類に分類できる。

処理の高速化 よく使われる「\d+」などについては、エンジンの通常の処理よりも高速になるように特別なコードが用意されていることがある。
処理の回避 例えば、先頭が「\A」（行頭にマッチ）になっている正規表現は、先頭位置が文字列の先頭のときでなければマッチしないのだから、そこでマッチしないことがわかったら、トランスミッションによって１文字先に進んで行の途中からチェックする必要はない。

正規表現適用のメカニズム

ターゲット文字列に正規表現を適用する手順は次のとおりである。

正規表現のコンパイル 正規表現のエラーをチェックし、正しいものであれば、内部形式にコンパイルする。
トランスミッションの始動 トランスミッションがターゲット文字列の先頭を開始位置として正規表現エンジンの”位置合わせ”をする。
要素のテスト エンジンは4章で説明したように正規表現の要素から要素へと移動しながら、正規表現とテキストを突き合わせていく。
マッチ成功　マッチが見つかると、従来型NFAは現在のステートを”固定”して成功を報告する。それに対し、POSIX NFAは、マッチがそれまでで最長のものならマッチ候補としてそれを記憶するだけで、残されている保存ステートの処理を続行する。保存ステートが無くなるとそれまでの最長マッチを報告する。
トランスミッションによる開始位置の変更 マッチが見つからなければ、トランスミッションは正規表現エンジンの処理開始位置をテキスト内の次の文字に前進させ、正規表現エンジンは最初から正規表現の適用をやり直す（ステップ３に戻る）。
全体としてのマッチ不成功 ターゲット文字列の全ての文字位置（最後の文字の直後を含む）を開始位置として正規表現エンジンを適用してもマッチが見つからなければ、全体としてのマッチ不成功を報告しなければならない。

適用前の最適化

コンパイル結果のキャッシング

毎回正規表現を１つ１つ再コンパイルするのだとしたら効率が悪い。最初にコンパイルした内部形式をキャッシングした方が（メモリのコストは掛かるが）時間的にはずっと効率がよい。

コンパイル結果のキャッシング: 統合型アプローチ

Perlやawkのような統合型アプローチでは、コンパイル結果を簡単にキャッシングすることができる。内部的には、個々の正規表現はコードの特定の部分と結び付けられており、コンパイル済みの形式は、それが初めて実行されたところに結びつけておくことができる。

コンパイル結果のキャッシング: 手続き型アプローチ

手続き型アプローチでは、最近使われた正規表現パターンとそのコンパイル結果を結びつけるマップが使われることが多い。
”この正規表現を適用せよ”関数は呼び出されると、パターン引数と正規表現キャッシュのパターンを比較し、等しいものがあればキャッシングされたバージョンを使う。無ければ、先に進んで正規表現をコンパイルし、キャッシュに保存する。キャッシュがいっぱいになり、コンパイル済みの正規表現を捨てなければならなくなると、最後に使われてから最も時間の経過したものを捨てる。
GNU Emacsは、20コマでの正規表現を管理できるキャッシュを持っている。Tclでは30個まで、PHPでは4,000個以上を管理できる。

コンパイル結果のキャッシング: オブジェクト指向型アプローチ

オブジェクト指向型アプローチでは、正規表現がコンパイルされるタイミングをプログラマが直接コントロールできる。

長さを計算に入れた最適化

「^Subject: (.*)」は、かなり長いテキストにマッチできるが、マッチするためにはターゲットに少なくとも９文字分の長さがなければならない。ターゲット文字列がそれよりも短ければ、エンジンを始動する必要はないのだ。

トランスミッションの最適化

特定の文字列がマッチしないことを正規表現エンジンが予め判断できなくても、トランスミッションが実際に正規表現を適用しなければならない先頭位置の数を減らすことはできる。

文字列/行の先頭アンカーによる最適化

先頭が「^」になっている正規表現は、「^」がマッチする先頭位置でしかマッチする可能性がないので、正規表現を適用するのもその位置だけにしようというのが、この最適化である。
この最適化が有効な場合、正規表現がマッチしない場合に「^」を付けたほうが高速である。

暗黙のアンカーによる最適化

この最適化をサポートするエンジンは、正規表現の先頭が「.*」や「.+」であり、かつ正規表現全体を対象とする選択がなければ、暗黙の「^」を正規表現の先頭につけることができることを認識する。

文字列/行の末尾アンカーによる最適化

「regex(es)?$」という正規表現がマッチするのは、文字列の末尾から８文字以内に先頭位置が有るときだけである。だからトランスミッションをそこまで一気に前進させれば、無駄なマッチ作業の多くを省略できる。

先頭文字/文字クラス/部分文字列の識別による最適化

「this|that|other」は、先頭が「[ot]」にマッチする開始位置以外ではマッチする可能性はないので、トランスミッションに予め文字列内の文字をチェックさせて「[ot]」にマッチする位置だけを開始位置として正規表現を適用させれば、処理を大幅に短縮できる。

長さを計算に入れたトランスミッションによる最適化

文字列の末尾に近すぎてマッチする可能性がなくなったところで、トランスミッションにマッチ試行を中止させる

より高速な正規表現を書くためのテクニック

適用できる最適化の種類を理解していれば、より効率的に処理される正規表現を書く上で有利だ。この知識を、従来型NFAの動作原理についての理解と組み合わせれば、つぎの３つの方法に応用できる。

最適化されるように正規表現を書く 組み込まれていることを知っている（あるいは、将来追加されそうだと思われる）最適化機能が働くような正規表現を書くということ。たとえば、「x+」ではなく「xx*」と書けば、必須とされる文字の事前チェックや先頭文字の識別と言った最適化がすぐに働くようになる。
最適化機能を模倣する ツールが特定の最適化機能をサポートしていないことはわかっているが、自分でその最適化を真似すれば、大幅な高速化が図れる場合がある。「this|that」の先頭に「(?=t)」を追加すると、マッチするには先頭が’t’でなければならないことを正規表現から判断できないシステムにおいても、先頭文字の識別による最適化に近い効果が得られる。
エンジンをマッチに導く 従来型NFAエンジンがどのように動作するかがわかっていれば、エンジンをより高速にマッチに導ける。もう一度「this|that」の例を使うと、すべての選択肢の先頭が「th」なので、最初の選択肢が「th」でマッチしなければ、２番目の選択肢も「th」のところで確実にマッチに失敗する。つまり、２番めの選択肢を検討することは無駄だ。「th(?:is|at)」を使えば、そのようなムダは避けられる。

効率と最適化は、時として非常に難しい問題になりえるという認識が大切だ。この節のこれ以降の部分を読むにあたって、次のことを頭に入れていただきたい。

間違いなく役に立つと思える変更を加えたら、自分では気づかないうちに作用していた他の最適化が効かなくなって、全体に処理が遅くなる場合がある。
組み込まれていない最適化を模倣するために何かを追加したら、その追加部分にかかる時間が節約できる時間よりも長くなり、かえって遅くなってしまう場合がある。
現在は組み込まれていない最適化を模倣するために何かを追加したら、ツールのアップグレードでその最適化が組み込まれて、それを活用できないとか、重複して同じことをしてしまうということになり、効率を下げる場合がある。
同様に、現在は組み込まれている最適化を作動させようとして正規表現をいじったら、将来ツールがアップグレードされて、より高度な最適化が導入されたときに、それが作動しなくなってしまう場合がある。
効率を上げるために正規表現をいじったら、正規表現が理解しづらくメンテナンスしにくいものになってしまう場合がある。
特定の変更によって得られる効果（または被る弊害）の度合いは、殆どの場合、どのデータに適用するかによって大きく変わる。あるデータでは効果のある変更が、他のデータでは有害になることもある。

常識的なテクニック

最も効果的なテクニックの中には、常識だけでわかるものがある。

再コンパイルを回避する

正規表現のコンパイルや定義の回数をできるだけ少なくする。
例えば、ループ内で正規表現を適用したい場合には、正規表現オブジェクトをループの外側で作り、それをループ内で繰り返し使うようにする。

キャプチャなしの括弧を使う

キャプチャ付き括弧のキャプチャ機能が不要なら、キャプチャなしの括弧「(?:…)」をつかう。キャプチャが不要なことによる直接的なコスト削減の他に、バックトラックのために必要なステートを単純化して高速化するという副次的な効率化の効果もある。また不要な括弧の削減などの最適化を適用する道も開けてくる。

余分な括弧を付けない

必要なときにはカッコを使っても良いが、必要でないときに括弧を使うと、最適化が働かなくなる場合がある。

余分な文字クラスを使わない

「^.*[:]」と言った正規表現は文字クラスの無駄なオーバーヘッドがかかるので、「^.*:」と書く。

先頭アンカーを使う

極稀な場合を除き、先頭が「.*」になっている正規表現は、その前に「^」や「\A」をつけるようにしたほうが良い。

リテラルテキストを見立たせる

リテラルテキストを”目立たせる”用に書き方を工夫すると、リテラル文字列の存在をエンジンに認識させやすくなり、様々なリテラルテキスト関連の最適化が働きやすくなる。

量指定子から必須要素を”くくり出す”

「x+」ではなく「xx*」を使うと、'x'が必須だということがより明確になる。同様に、「-{5,7}」は「-----{0,2}」と書いたほうが良い。

**選択肢の先頭にある必須要素を”くくり出す”

「(?:this|that)」ではなく「th(?:is|at)」を使うと、先頭の「th」が必須要素として目立つようになる。

アンカーを目立たせる

エンジンによる正規表現の最適化の中で特に効果が大きいのは、ターゲット文字列の片方の端に正規表現の適用位置を限定するアンカー（「^」、「$」、「\G」など）を利用するものだ。しかし、そのような最適化が適用できる状況を認識するという点では、エンジンの能力はまちまちなので、認識しやすくするために利用できるテクニックがある。

^や\Gを正規表現の先頭に出す

「^(?:abc|123)」と「^abc|^123)」は論理的には同じ正規表現だが、前者を使ったほうが、より多くの正規表現エンジンで”先頭アンカーによる最適化”が利用可能になる。このため、前者のように書いたほうがずっと効率的になる。

$を正規表現の末尾に出す

「abc$|123$」と「(?:abc|123)$」は論理的には同じ正規表現だが、エンジンからは異なるものとして扱われる場合がある。

複数の正規表現への分解

一つの大きな正規表現を適用するよりも、小さな正規表現をたくさん適用したほうがずっと高速になる場合がある。ちょっとわざとらしい例になるが、長い文字列に月の名前が含まれているかどうかをチェックしたいときには、「January|February|March|…」を使うよりも、「January」、「February」、「March」などをバラバラにチェックしたほうがずっと効率が良い。

先頭文字の識別の模倣

”先頭文字の識別による最適化”がサポートされていない場合には、正規表現の先頭に適切な先読みを追加すれば、この最適化を真似ることができる。先読みを使えば、正規表現の残りの部分をマッチさせる前に、適切な先頭文字の位置にいることを”事前チェック”できる。

例えば、「Jan|Feb|…|Dec」のためには、「(?=[JFMASOND](?:Jan|Feb|…|Dec)」が使える。

アトミックグループと絶対最大量指定子を使う

「^[^:]+:」という正規表現でコロンのマッチを初めて試行して失敗した場合、バックトラックで「^[^:]+」のなかにもどったとしても、絶対にマッチが成功することはない。
アトミックグループをつかって「^(?>[^:]+):」または「^[^:]++:」と書けば、+よりも手前のステートは捨てられるか、最初から作られない。こうすると、エンジンがバックトラックする先が消えるので、決して実を結ぶことのないバックトラックを防ぐことができる。

しかし、これらの構文は使い方を誤るとマッチするものが意図せずに変わってしまう危険性が有るので、十二分に注意が必要である。

エンジンをマッチに導く

NFA正規表現の効率を上げるために効果的な方法の一つは、”制御構造”を出来る限り先送りにするということである。
すでに「this|that」ではなく「th(?:is|at)」を使うべきだということには触れたが、これは、前者なら選択が最初の問題になってしますのに対し、後者なら「th」がマッチするまでに比較的高くつく選択を先延ばしにできるという意味だ。

最も出現頻度が高くなるはずの選択肢を前に配置する

順番を変えても正しさに影響がない場合には、最も出現頻度が高いと思われる選択肢を最初に配置すれば、効率が上がる。

7章 Perl

割愛

8章 Java

割愛

9章 .NET

割愛

10章 PHP

割愛