Dart で 正規表現 Engine を作成する (2) Parserの作成

前回の続きです。(http://qiita.com/kyorohiro/items/cbd2617a979a31efb3ba)

前回のおさらい

VM部分を作成した

前回はVM部分を作成しました。今回は、Parser部分を作成します。

対象は最小限の正規表現

対象の演算子は以下の通り

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

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

対象はOPコードに落とすVM型エンジン

以下ようなOPコードに落とす事ができる

regexopcode

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

Parseして、ソースをOPコードへ落とそう

少しずつ、正規表現をOPコードへ変換していきます。難解な作業に思えますが、ソースから一気にOPコードに変換するのではなくて、段階を踏むことで簡単にOPコードへ落とすことができます。

Tokenに分割する

まずは、演算子とそれ以外の文字に分割しましょう。Tokenに分割するといいます。
Token とは、ソースコードを構成する最小単位の事です。今回の場合だと、"(", ")" "|" "*" それ以外の文字列に分割します。
ref(http://ja.wikipedia.org/wiki/字句解析)

今回作成したものでは、5種類の単位に分割しています。

token

RParanToken "("の場合
LParanToken ")"の場合
UnionToken "|"の場合
StarToken "*"の場合
CharToken それ以外の文字

例えば、"ab*"の場合、[CharToken(a) CharToken(b) StarToken]と変換します。

木構造にしてから、OPコードに落とす

生成したTokenからOPコードを直接生成する事もできます。しかし、そのまま変換するとちょっとだけコード複雑になる場合があります。
そこで、伝統的テクニックとして、木構造に落とす方法がとられます。今回作成したパーサーでも、一度木構造に落とす形式にしています。

[具体的に見る] 変換が簡単な例

"ab"は、とそのまま変換するだけです。木構造に落とす必要はなさそうです。

xx

1:CharOp(a) 
2:CharOp(b)
3:Match

[具体的に見る] 変換が困難な例

"ab*"は、どうでしょうか?そのまま変換するだけでは上手く生成できません。"*" 指定された場合、ひとつ前のCharOp(b)の前に、Sprit(3,5)を挿入する必要があります。でも、まだ大丈夫そう。

xx

1: CharOp(a)
2: Sprit(3,5)　<-- 　ここ
3: Char(b)
4: Jump(2)
5: Match

"(ab)"、"(ab|xy)"　はどうでしょうか?ちょっと面倒ですね。

[木構造にする。]

"(ab)*"は以下のような構造と見なしてから展開すると簡単に描けます。
[star [Char(a), Char(b)]]

xx

1: Sprit(2,5)
2: Char(a)
3: Char(b)
4: Jump(1)
5: Match

左から順番にOPコードに展開しただけです。このように、一度、木構造に通すと事で、OPコードへの展開が楽になるわけです。

例えば、"(ab|xy)*"は､[star　[ Union [[Char(a)Char(b)] [[Char(x)Char(y)]]]] といった感じに書けます。

実装

以下に私が実装したものおきました。
https://github.com/kyorohiro/dart_hetimaregex/tree/master/lib/src/parser

次回

当初の目的であった、正規表現の枠を超えて、色々なパターンマッチをしてみます。
正規表現(文字列)からパターンマッチするのは止めて、直接、木構造を生成するなどして、より柔軟にパターンマッチをしていきます。