ANTLRを使ってクエリパーサーを実装する

MNTSQの溝口です。 普段からMNTSQの検索周りの開発を行っています。

MNTSQを含め、情報検索を行うモダンなアプリケーションではシンプルなUIが好まれます。 一方で、複雑な検索条件などを指定したい場合、シンプルなUIでは実現が難しいという問題があります。

その場合、シンプルなUIとは別に「詳細検索ページ」を用意するか、キーワードを入れるテキストボックスで検索式をサポートさせたりします。 今回は、直近で検索式のことを考える機会があったので、その実装手順について簡単に書こうと思います。

検索式とは

簡単に言えば、AND / OR / NOT などの論理記号と、 () での評価の優先順位の指定などです。あとは、 [フィールド名]:[キーワード] など、特定のフィールドに対するオペレーション、 ” をつかった明示的なフレーズ検索などをサポートすることもあります。

検索式を実装するに当たっては、仕様が多くなると当然実装も複雑になっていくので、この記事では以下のようなシンプルな仕様を考えます。

• AND / OR / NOT を演算子としてサポート
  • NOTを最優先で評価
  • ANDを次点に評価
  • ORを最後に評価
• () で括られている部分は上記の演算子よりも優先的に評価する

演算子の評価順について少し掘り下げると、例えば以下の等式が成り立つというという意味です。

A AND NOT B OR C = (A AND (NOT B)) OR C

もしANDとORの評価の優先順位が逆になった場合には、以下のようになります。

A AND NOT B OR C = A AND ((NOT B) OR C)

この辺りは決めの問題なので、上述の通り NOT > AND > OR の順として進めます。

ANTLRを使った実装

検索式の実装のために、ANTLRを使います。

ANTLRのセットアップ

まずはANTLRのセットアップをします。今回はとりあえずUbuntu 20.04で以下のような公式サイトのセットアップをそのまま利用します。

sudo apt install openjdk-11-jdk
cd /usr/local/lib
sudo curl -O https://www.antlr.org/download/antlr-4.9-complete.jar
export CLASSPATH=".:/usr/local/lib/antlr-4.9-complete.jar:$CLASSPATH"
alias antlr4='java -Xmx500M -cp "/usr/local/lib/antlr-4.9-complete.jar:$CLASSPATH" org.antlr.v4.Tool'
alias grun='java -Xmx500M -cp "/usr/local/lib/antlr-4.9-complete.jar:$CLASSPATH" org.antlr.v4.gui.TestRig'

実装

準備も終わったので、パーサーを書いていきます。 とりあえず、SimpleQueryParser.g4というファイルを作り、先頭に以下を書きます。

grammar SimpleQueryParser;

パーサーを書くときには小さく実装し、都度挙動を確かめながら進めたいので、まずは AND / OR / NOT を区別するところを書きます。

他のパーサージェネレータと同じく、ANTLRでもまずは要素を列挙していきます。まずはわかりやすいところから、 AND / OR / NOT はすべて大文字のときのみ論理演算子として認識させることとします。

AND
   :'AND'
   ;
OR
   :'OR'
   ;
NOT
   :'NOT'
   ;

検索キーワードと論理式の区切りは改行記号と全角半角スペースが1つ以上連続しているものとします。

WHITE_SPACE
   :[ \t\r\n\u3000]+
   ;

検索キーワードは上記の区切り文字以外の文字列から作られるので、 KEYWORD_CHARACTER を一旦以下のように設定しておきます。

KEYWORD_CHARACTER
   :~(' '
   |'\t'
   |'\r'
   |'\n'
   |'\u3000')
   ;

以上が基本要素です。これらを使って式(意味を持つ基本要素の集合)の形を考えていきます。

まず、検索キーワードは KEYWORD_CHARACTER が1文字以上連なっているので、以下のようになります。

keyword
   :KEYWORD_CHARACTER+
   ;

上述の演算子の優先順位の通り、今回は NOT を最優先に評価するので、まずはキーワードの前に NOT がついているか否かをNOT式( notExpression )としてひとまとめにします。

notExpression
   :(NOT WHITE_SPACE)? keyword
   ;

例えば A AND NOT B OR C の場合には、A / NOT B / C が notExpression に相当します。

次は演算子の優先順位的に notExpression に対してAND条件がどのように作用するかを考えると、一つの notExpression に対して0回以上 AND notExpression が連なるものと考えられます。

また、全てAND条件ならばその評価順は関係ないので、ひとまとめにしても問題なさそうです。そのため、AND式( andExpression )は以下のようになります。

andExpression
   :notExpression (WHITE_SPACE AND WHITE_SPACE notExpression)*
   ;

上の例だと、 andExpression は A AND NOT B / C に相当します。

同様にOR条件を以下のように実装します。なお、AND / ORが省略された場合にはORとして扱うように OR WHITE_SPACE はあってもなくても良いものとしています。

orExpression
   :andExpression (WHITE_SPACE (OR WHITE_SPACE)? andExpression)*
   ;

一旦できたものが期待通り動くか確認してみます。これもANTLRのチュートリアル通りに以下を実行します。

antlr4 SimpleQueryParser.g4
javac SimpleQueryParser*.java
grun SimpleQueryParser orExpression -gui
A AND NOT B OR C
^D

きちんと期待通りパースされていそうです。

次に () の処理を追加します。まずは () の要素を定義して、 KEYWORD_CHARACTER もそれに合わせて更新します。

LEFT_PAREN
   :'('
   ;

RIGHT_PAREN
   :')'
   ;

KEYWORD_CHARACTER
   :~(' '
   |'\t'
   |'\r'
   |'\n'
   |'\u3000'
   |'('
   |')')
   ;

次に処理の優先順位を考えます。

() 内のすべての処理が優先評価されるので () のあるものは NOT よりも前、つまり keyword と同等の扱いとなります。また、() の中身には AND / OR / NOT を含む論理式が入りうるので、これは orExpression と同等と言えます。

ただ、意味を持つ最小単位である keyword とは区別したいので、以下のように keyword と notExpression の間に 基本式( baseExpression ) という式を追加して、ここに括弧に括られた orExpression と keyword を定義します。

baseExpression
   :keyword
   :LEFT_PAREN WHITE_SPACE? orExpression WHITE_SPACE? RIGHT_PAREN
   ;
 
notExpression
   :(NOT WHITE_SPACE)? baseExpression
   ;

これで上述の仕様を満たすものが完成しました。挙動を試してみます。

antlr4 SimpleQueryParser.g4
javac SimpleQueryParser*.java
grun SimpleQueryParser orExpression -gui
A AND NOT (B OR C)
^D

要素のネストがちょっと深いですが、期待通りの挙動になっています。

まとめ

シンプルなクエリパーサーをANTLRを使って書いてみました。実際に使われるものはより複雑なものになりますが、自作のパーサーによって簡単に検索サービスを拡張できることは多いので、検討する価値は十分にあると思います。

この記事を書いた人

溝口泰史

MNTSQ社で検索エンジニアをしています。