Dart で 正規表現 Engine を作成する (1) VMの作成

Dartで正規表現のエンジンを作成しました。いくつかノウハウを得ることができたので、その情報をまとめてみました。

基本的、作成した正規表現エンジンについて解説しています。

また、記事や本や論文を参考にして作成しました。

• 正規表現エンジンをつくろう
  http://codezine.jp/article/detail/3039
  * 正規表現技術入門 (←おすすめ)
  http://gihyo.jp/book/2015/978-4-7741-7270-5
  http://www.amazon.co.jp/o/ASIN/4774172707/gihyojp-22
• Regular Expression Matching: the Virtual Machine Approach
  https://swtch.com/~rsc/regexp/regexp2.html

車輪の再構築

車輪の再発明でなくて、再構築を目指していますよ的なアジ

正規表現の枠を超えて

[さまざまな実装]

　今から、50年以上も前から、正規表現は、テキストデータのパターンマッチングの手法として利用されてきました。
　その有効性は皆さんご存知の通りで、とても便利なので、ほとんどの言語で正規表現を利用することができます。Python Perl JavaScript Dart とかです。正規表現を利用したいだけならば、新たに正規表現エンジンを作成する必要はないでしょう。

[エッセンスを生かす]

　正規表現はとても有効ですが、その利用範囲はテキストに限られています。しかし、正規表現エンジンが利用している仕組みは、テキスト処理にとらわれません。様々なものに応用可能です。
例えば、テキストではなくて、バイナリデータへのパターンマッチングへの応用とかいかがですか?
例えば、神羅万象のさまざまな構造を表現するのに応用できないだろうか?
難しいかも知れないけど、それらのヒントやエッセンスは学ぶことができます。

正規表現エンジンのおさらい

正規表現はテキストマッチングのための表現

正規表現は文字列集合を一つの文字列で表現する方法のひとつです。(ref https://ja.wikipedia.org/wiki/%E6%AD%A3%E8%A6%8F%E8%A1%A8%E7%8F%BE)

例えば、"sabce" と "sxyze"は、"s(abc|xyz)e" とひとつの文字列で表現で。"se" "sae" "saae" "saaaae"　は、"sae"で表現できます。"(" ")" "|" "" 演算子を利用して、複数の文字列を表現するのです。

今回対象としている演算子は以下の通り

ab|xy abまたはxyにマッチする。 
(ab) abをひとつのパターンとする。
a* aを0回以上繰り返す。 

VM型の正規表現エンジンを作成してみよう

「Regular Expression Matching: the Virtual Machine Approach」を元に、Dartで動作する正規表現エンジンを作成しました。
VM型の正規表現エンジンです。

Virtual Machine は超便利

[複雑な問題を単純な問題の集まりに分割する]

Virtual Machineを利用する言うことは、複雑な問題を単純な命令に落と方法を考えるということを意味します。基本的に Virtual Machine は支持された単純な命令を順番にこなす事しかできません。例えば、lua vmでは、「local a,i;a=a+i」は以下のような命令で実現しています。

lua4.0opcode

1: PUSHNIL 2
2: GETLOCAL 0; a
3: GETLOCAL 1; i
4: ADD
5: SETLOCAL 0; 1

http://www.lua.org/doc/jucs05.pdf (The Implementation of Lua 5.0)

単純な命令を上から順番にこなしているだけですね。例えばlua5.0では、以下のようなオプコードで実現しています。

lua5.0opcode

MOVE A B
LOADK A Bx
LOADBOOL A B C
LOADNIL A B
GETUPVAL A B
GETGLOBAL A Bx
GETTABLE A B C
SETGLOBAL A Bx
SETUPVAL A B
SETTABLE A B C
NEWTABLE A B C
SELF A B C
ADD A B C
SUB A B C
MUL A B C
DIV A B C
POW A B C
UNM A B
NOT A B
CONCAT A B C
JMP sBx
EQ A B C
LT A B C
LE A B C
TEST A B C
CALL A B C
TAILCALL A B C
RETURN A B
FORLOOP A sBx
TFORLOOP A C
TFORPREP A sBx
SETLIST A Bx 
SETLISTO A Bx
CLOSE A 
CLOSURE A Bx 

フログラミング言語的な複雑な表現も、こう言った単純な命令を上から順にこなしていくという問題に還元する事ができるわけです。

[正規表現のための Opcodeは4つだけ]

本対象の正規表現のためのOpcodeは4つだけです。

regexopcode

char C 文字がCでなければ、タスクを終了する
match パターンマッチに成功した。
jmp x 次に実行する命令の位置を、x番目に移動する。
split x,y 次に実行する位置を、x番目に移動する。y番目から始まるタスクを生成する。

ref Regular Expression Matching: the Virtual Machine Approach
(https://swtch.com/~rsc/regexp/regexp2.html)

実際に通してみると以下のような感じ

"ab"をOPコードに落とすと

1: char a
2: char b
3: match

"a*b"をOPコードに落とすと(1)

1: split 2 4; 次に実行するコマンドは2番目。4番目から始まるタスクを生成する。
2: char a; 参照している文字がaであること。
3: jmp 1; 1番目に移動する。
4: char b; 参照している文字がbであること。
5: match

(1)に、"aab"という文字(src)が与えた場合、以下のような順序でマッチする文字であると判定されます。

※ []はリスト
※ {}はタスク
※　command:コマンドの位置
※　src:参照している文字列の位置

1. "1: split 2 4" でタスクが二つになる。[{command:2, src:0} {command:4, src:0]]
2. "2: char" にマッチする。[{command:3, src:1} {command:4, src:0]]
3. "jmp 1" で、1番目に移動する。[{command:1, src:1} {command:4, src:0]]
4. "1: split 2 4" でタスクが二つになる。[{command:2, src:1} {command:4, src:1} {command:4, src:0]]
5. "2: char" にマッチしない。タスクを破棄する。[{command:4, src:1} {command:4, src:0]]
6. "4: char b"にマッチする。[{command:5, src:2} {command:4, src:0]]
7. "5: match"でマッチした事がわかる。

"a|b"をOPコードに落とすと

1: split 2 4; 次に実行するコマンドは2番目。4番目から始まるタスクを生成する。
2: char a; 参照している文字がaであること。
3: jmp 5; 5番目に移動する。
4: char b; 参照している文字がbであること。
5: match

"a(bc)*d"をOPコードに落とすと

1: char a;
2: split 2 4;
3: char b;
4: char c;
5: jmp 2;
4: char d;
5: match

VM部分を実装する

以下に私が実装したものおきました。
https://github.com/kyorohiro/dart_hetimaregex/tree/master/lib/src/vm
ただし、「Regular Expression Matching: the Virtual Machine Approach」に乗っているコードの方が読みやすいと思います。

次回

木構造に落としてパースする部分を解説します。
http://qiita.com/kyorohiro/items/eed9617aebdbe450aad3