Jeff Moser氏による .NET 正規表現の実際の仕組みの調査

作者 Jonathan Allen , 翻訳者 伊藤 幸博 投稿日 2009年4月17日

セクション

デベロップメント,

設計/アーキテクチャ

トピック

コンパイラ ,

.NETフレームワーク ,

Domain Specific Languages ,

.NET

原文(投稿日：2009/4/1)へのリンク

Jeff Moser氏は .NETの正規表現がどのような仕組みになっているのか(リンク)徹底的な調査を行った。 彼の記事は、例えばコンパイルされた正規表現によって使用される機械語などのMicrosoftによる実装の中核的な動作原理を対象としている。

まず彼が明らかにするのは、直近の15個の正規表現がキャッシュされるということである。 これは１つあるいは２つの正規表現を使うだけの小さなユーティリティアプリケーションにとっては、明示的に Regex オプジェクトを作成する必要はおそらく無いということを意味する。

正規表現をコンパイルする際、その最初のステップはRegexTreeを生成するスキャナから構成される。 葉ノード部分を見ると、これはソースコードとかなり類似している。  次にこれは正規表現エンジンの機械語へと翻訳される。

作業の大半はEmitFragment 関数(リンク)を構成する250行のswitchステートメントによって行われます。  この関数はRegexTreeの「断片」を分割してそれらをよりシンプルなRegexCode(リンク)へと変換します。

[…]

この作業が全て終わると RegexCode即ち「操作コード」およびそれらの引数を説明する整数の配列が得られます。 「Setrep」(リンク)のようないくつかの命令は文字列の引数を受け取るのが分かります。 これらの引数は文字列テーブル内のオフセットを指し示します。 先ほど見たはっきりとしない文字列に文字セットの全てを詰め込むことが重要な意味を持っていたのは、この理由に因ります。 その情報を命令に渡すための唯一の方法だったのです。

コードの配列を復号すると、以下のようになります。

インデックス	命令	操作コード/引数	文字列テーブル参照	説明
0	Lazybranch(リンク)	23		遅延的に21番目の Stop(リンク)命令に分岐。
1		21
2	Setmark(リンク)	31		後でバックトラックが必要な場合のために現在の状態をスタックにプッシュ。
3	Multi(リンク)	12		文字列テーブルの０番目の要素「http://」の複数文字マッチを実行。
4		0	"http://"
5	Setmark(リンク)	31		後でバックトラックが必要な場合のために現在の状態をスタックにプッシュ。
6	Setrep(リンク)	2		文字列テーブルの１番目に格納された [\s/] で表される文字のセットによる長さ１の反復マッチを実行。
7		1	"\x1\x2\x1\x2F\x30\x64"
8		1
9	Setloop(リンク)	5		最大 Int32.MaxValue 回のループで文字セット [\s/] のマッチを実行。
10		1	"\x1\x2\x1\x2F\x30\x64"
11		2147483647
12	Capturemark(リンク)	32		最後の Setmark で設定されたマークと現在の位置との間の文字列をグループ番号１にキャプチャ。
13		1
14		-1
15	Oneloop(リンク)	3		最大１回のループで Unicode 文字 47 ('/') のマッチを実行。
16		47
17		1
18	Capturemark(リンク)	32		最初の Setmark 命令と現在の位置の間の内容をグループ番号０にキャプチャ。
19		0
20		-1
21	Stop(リンク)	40		正規表現の停止。

これで正規表現が後々実行されるシンプルな「プログラム」へと変化しているのがわかります。

このプロセスについてより詳しくは Jeff Moser 氏のブログ(リンク)で読むことができる。また彼の記事では下記についても言及している。

• 接頭語の最適化
• インタープリタ
• バックトラック
• 既知のバグ

• 次へ >