BT

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

| 作者: Jonathan Allen フォローする 595 人のフォロワー , 翻訳者 伊藤 幸博 フォローする 0 人のフォロワー 投稿日 2009年4月17日. 推定読書時間: 3 分 |

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

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

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

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

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

[…]

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

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

インデックス

命令

操作コード/引数

文字列テーブル参照

説明

0

Lazybranch(リンク)

23

 

遅延的に21番目の Stop(リンク)命令に分岐。

1

 

21

 

2

Setmark(リンク)

31

 

後でバックトラックが必要な場合のために現在の状態をスタックにプッシュ。

3

Multi(リンク)

12

 

文字列テーブルの0番目の要素「http://」の複数文字マッチを実行。

4

 

0

"http://"

5

Setmark(リンク)

31

 

後でバックトラックが必要な場合のために現在の状態をスタックにプッシュ。

6

Setrep(リンク)

2

 

文字列テーブルの1番目に格納された [\s/] で表される文字のセットによる長さ1の反復マッチを実行。

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 で設定されたマークと現在の位置との間の文字列をグループ番号1にキャプチャ。

13

 

1

 

14

 

-1

 

15

Oneloop(リンク)

3

 

最大1回のループで Unicode 文字 47 ('/') のマッチを実行。

16

 

47

 

17

 

1

 

18

Capturemark(リンク)

32

 

最初の Setmark 命令と現在の位置の間の内容をグループ番号0にキャプチャ。

19

 

0

 

20

 

-1

 

21

Stop(リンク)

40

 

正規表現の停止。

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

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

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

この記事に星をつける

おすすめ度
スタイル

こんにちは

コメントするには InfoQアカウントの登録 または が必要です。InfoQ に登録するとさまざまなことができます。

アカウント登録をしてInfoQをお楽しみください。

あなたの意見をお聞かせください。

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする
コミュニティコメント

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする

ディスカッション

InfoQにログインし新機能を利用する


パスワードを忘れた方はこちらへ

Follow

お気に入りのトピックや著者をフォローする

業界やサイト内で一番重要な見出しを閲覧する

Like

より多いシグナル、より少ないノイズ

お気に入りのトピックと著者を選択して自分のフィードを作る

Notifications

最新情報をすぐ手に入れるようにしよう

通知設定をして、お気に入りコンテンツを見逃さないようにしよう!

BT