がりらぼ

WindowsRuntimeの応援ブログ

にゅーろにあのフィルタクエリコンパイラを作りました

Neuronia v1のタイムラインフィルタはクエリではありません。限られた条件を指定してフィルタを作ります。

限られた条件でのフィルタだと、フィルタを作りやすいのでユーザーには便利だったりしますが、開発側にとってみると、限られた条件でがんばってフィルタ処理をしてツイートを分類しなければいけないのでいろいろ悲しいです*1

大人気TwitterクライアントAristeaにはフィルタウィザードがあり、

ジェネレータ→クエリ自動生成→フィルタ完成

という流れが非常にすばらしかったのでパクります参考にしたいと思います。

f:id:garicchi:20140909090948p:plain

というわけでクエリ作成の流れを考えてみる。

そもそもクエリ文字列からどうやってタイムラインを分類するのか

クエリ文字とは「 user.id_str == "hogehoge" 」みたいなやつのことです。

ではどうやってこの文字列からフィルタを作るのか考えます。

タイムラインフィルタというものは言い換えると、あるツイートをそのタイムラインに入れるかどうか分類すると言い換えることができます。

ようするにTweetを入力するとbooleanを出力する何かがあればいいわけです。

さらにクエリ文字を使うとTweetを入力するとbooleanを出力する何かをStringから作ることができればいいわけです。

f:id:garicchi:20140909092026p:plain

フィルタクエリにある「user.id_str」みたいなやつはプロパティを指定しています。

これを、すべてのプロパティに対して文字列をif分岐していたら日が暮れてしまいます。

なので「user.id_str」みたいな文字列がクエリにあると、Tweetクラスのuserプロパティのid_strプロパティをC#からアクセスする必要があります。

さらに==や>=など様々な比較演算子に応じた比較をしてbooleanを出力しなければいけません。

これは通常のプログラムでは実現不可能なのでメタプログラミングを使います。

メタプログラミング

メタプログラミングとは、簡単に言うとプログラムをプログラムから生成します。

この場合では、「Tweetを入れるとフィルタクエリの条件に従ったbooleanを出力するプログラム」をプログラムから生成します。

f:id:garicchi:20140909093045p:plain

C#メタプログラミングをする方法の一つに、式木(Expression)があります。 Expressionは、Expressionを組み合わせて木構造を生成し、最終的にラムダ式コンパイルすることが可能なヤツです。

なので

Expression.Equals()とかExpression.And()とかを組み合わせて最終的には以下のラムダ式みたいなのにコンパイルすればオッケーです。

Func<Tweet,bool> func=(tweet)=>{
bool bln;    
//何らかの条件にtweetが当てはまるかでblnの値を変える
return bln;
};

であとはタイムラインに流れてきたTweetをそのラムダ式に与えて、booleanを出力します。

Tweet tweet;//タイムラインの新着ツイート
bool b=func(tweet);
if(b){
    //タイムラインに追加
}

なので、式木を使ってクエリ文字列からラムダ式を生成し、ツイートを分類するフィルタを作ります。

コンパイラ

ここまでの流れを大まかに表すと、タイムラインクエリフィルタリングには

「クエリ文字列→Expression→ラムダ式

という流れで変換をしなければいけません。Expression→ラムダ式は式木がやってくれるので 今回の問題点はクエリ文字列→Expressionの変換です。

なのでクエリ文字列をExpressionに変換するコンパイラを作ることがタイムラインクエリフィルタリングの目的となります。

コンパイラにはソースコードの単語の区切りを見つける「字句解析」と字句間の関係性を考える「構文解析」を行い、最終的に変換結果を出力するひつようがあります。

コンパイラの知識についてはこちらの参考書から引っ張ってきています。

コンパイラ (新コンピュータサイエンス講座)

コンパイラ (新コンピュータサイエンス講座)

字句解析

クエリに関しては「字句間にスペースが必要」という条件を与えてやれば、あとはSplit関数で字句ごとに区切ることができます。 「user.id_str == 'hoge' && text contains 'hoge'」 を

  • user.id_str
  • ==
  • 'hoge'
  • text
  • contains
  • 'hoge'

のようなものに分けることができればいいのでSplitで十分です。

でもまあなんか悲しいのでStringReaderを使って位置文字ずつ解析しました。

本当なら正規文法から非決定性オートマトンを作って状態数最小化して決定性オートマトンを作って、その文字列が整数ならば整数のオートマトンで受理されるかを見て、初めて字句解析プログラムを作ることができますが、C#にはint.TryParseという便利なやつがあるので数字とか文字とかの判定はわりと簡単にできました。

構文解析

構文解析再帰下向き構文解析を使いました。

再帰下向き構文解析とは1字句先読みするだけでバックトラックなしかつ左再帰なしの解析をすることができる構文解析手法です。

再帰下向き構文解析を行うにはBNF(バッカスナウア記法)で文法を記述する必要があります。

実際に書いたBNFがこちら

f:id:garicchi:20140909095924p:plain

LL(1)っぽくない気もしますがFirstFollowとか使って判定するのはだるいのでこのままいくことにしました。

このBNFの<>で囲んであるやつが非終端記号で、この非終端記号ごとにクラスを作って、再帰的に構文解析を行います。

Expression生成

構文解析が完了したので、解析結果を使ってExpressionを出力しました。

ここらへんはわりと楽だったかも?

結果

なんやかんややってたら、クラスがこんなに増えてしまいました。

f:id:garicchi:20140909100341p:plain

コンパイルしてみるとちゃんとクエリ文字列の条件にあったboolean値が返ってきます。

f:id:garicchi:20140909100417p:plain

もし、クエリ文字にエラーがあったら、ちゃんとエラーも出力するようにしました。

f:id:garicchi:20140909100507p:plain

とりあえず簡易コンパイラを作ってみましたがまあわりといい感じにうごいてくれました。 にゅーろにあのクエリフィルタリング対応も近いですね!!

*1:実際悲しかった