Terraは、Luaを拡張し、メタプログラミングでネイティブコードを出力できるようになった言語です。どんな言語かは、以前ブログに書いた記事があるので、そちらも参照して下さい。

Thompson’s VM

正規表現マッチングの実装方法に、仮想マシンを使う方法があり、Regular Expression Matching: the Virtual Machine Approachに詳しく書かれています。今回は、Thompson’s VMを正規表現ごとに特殊化してみました。

文字列として与えられた正規表現を、Luaのlpegライブラリを使ってパースした後、VMの命令列にコンパイルします。例えば、(a|b)*cという正規表現はコンパイルされて次のような命令列になります。

1	gate	0
2	split	3	9
3	split	4	6
4	char	97
5	jump	7
6	char	98
7	gate	1
8	jump	1
9	char	99

charは1文字マッチ、jumpは指定された行番号へのジャンプ、splitは分岐（新しいスレッドを生成します）、gateは無限ループやスレッドの重複を防ぐためのフラグを操作する命令です。（gate命令は分岐したスレッドがジャンプして合流する部分に置かれています。）

この命令列から、特殊化したマッチング関数を生成します。Thompson’s VMでは、各スレッドはプログラムカウンターのみ保持しています。オリジナルの実装では、命令列からプログラムカウンターの位置の命令を読み取り、その命令に応じて分岐して処理を行っていますが、それをプログラムカウンターに応じて直接分岐するように特殊化してしまいます。switch(insts[pc].opcode) {case Char: ...}の代わりにswitch(pc) {case 1: ...} としてしまうイメージです。（実際には、Terraにはswitch文が存在していないので、if文による分岐で実現しています。）

成果物

mandel59/terrare at a5c42b20cd715854efa0a12ea5ef14a8e3b01a7e