はじめに

この記事はスタンバイ Advent Calendar 2024 の21日目の記事です。
昨日の記事は @arata-honda さんの「goのテスト関連で最近まで知らなかったことをまとめてみた」でした。

概要

弊社では検索エンジンにVespaを導入しており、検索クエリにはYQLを使用しています。
YQLは、SQLに似た構文を持つクエリ言語で、大量のデータを効率的に扱える柔軟性を備えています。

業務の中でクエリを綺麗にフォーマットしたい場面が増えてきましたが、適切なフォーマッターが見つからなかったため、自作することにしました。
フォーマッターを作成するには、まずクエリを解析し、各要素を正確に認識できる必要があります。
そのため、YQLの構造を学びつつ、ANTLRを使ってクエリの解析に取り組みました。

ANTLR（Another Tool for Language Recognition）は、文法ファイルを基にトークナイザーやパーサーを生成するツールです。
プログラミング言語だけでなく、SQLライクなクエリ言語やドメイン固有言語（DSL）の解析に広く利用されています。

今回は、Go言語を使い、YQLの基本的な解析方法を紹介します。
サンプルクエリは、学びやすさを優先してSQLに近いシンプルな構成にしています。

1. 事前準備

ANTLRのセットアップ

ANTLRを利用するためには、以下の環境を準備します。

Java（JDK 11以上）
ANTLRはJavaで動作します。JDKは公式サイトからインストールします。
ANTLR4 JARファイル
公式サイトからダウンロードするか、Macの場合はHomebrewを使ってインストールします。

brew install antlr

Goプロジェクト用パッケージ

GoでANTLRを利用するには、go.modに以下を追加します。

github.com/antlr4-go/antlr/v4

開発環境用プラグイン

ANTLRの文法ファイルを扱いやすくするため、以下のプラグインをインストールします

2. YQLの文法定義

YQLはSQLに似た構文を持つクエリ言語ですが、VespaのYQLは検索エンジン特化の機能をいくつか備えています。
詳細は文法は公式ドキュメントから参照できます。

今回の文法定義では、わかりやすさを重視して、以下の特徴のみを取り入れます。

SELECT句：取得するフィールドを指定します。複数のフィールドをカンマ区切りで指定できます。
FROM句：データソースを指定します。*で全てのデータソースを指定できます。
WHERE句：検索条件を指定します。複数の条件をANDやORで結合できます。

文法ファイルの概要とLexerとParserの役割

ANTLRの文法ファイル（.g4）は、以下の2つの要素で構成されています。

Lexer（字句解析器）

Lexerはテキストをトークン（単語や記号）に分解する役割を持ちます。

例：SELECT name, age FROM users WHERE age >= 30
[SELECT] [name] [,] [age] [FROM] … などがトークンとして認識されます。

Parser（構文解析器）

Lexerが生成したトークンを解析し、文法に基づいて構文木を構築します。
SELECT句やWHERE句といった文法ルールを定義します。

文法ファイルの例

Lexerファイル

Lexerはキーワードや記号の定義を行います。
以下はYQLに対応したLexerファイルの例です。

YQLLexser.g4

lexer grammar YQLLexer;

options {
    caseInsensitive = true;
}

SELECT          : 'SELECT';
FROM            : 'FROM';
WHERE           : 'WHERE';
AS              : 'AS';

WILDCARD        : '*';

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

EQUALS          : '=';
LESS            : '<';
GREATER         : '>';
LESS_EQUALS     : '<=';
GREATER_EQUALS  : '>=';

COMMA           : ',';
DOT             : '.';

fragment DIGIT  : [0-9];
NUMBER          : DIGIT+ ('.' DIGIT+)?;
IDENTIFIER      : [a-z][a-z0-9]*;
STRING          : '"' .*? '"';
WS              : [ \t\r\n]+ -> skip;

caseInsensitiveオプションを有効にして、大文字小文字を区別せずに解析します。
また、IDENTIFIERはデータソース名やフィールド名を表し、[a-z][a-z0-9]の正規表現で定義します。
STRINGはダブルクォートで囲まれた文字列を表し、".?"の正規表現で定義します。
WSトークンは、空白文字、タブ、改行をスキップするためのルールです。

Parserファイルの例

Parserは文法規則を定義し、クエリの構造を解析します。

YQLParser.g4

parser grammar YQLParser;

options {
    tokenVocab = YQLLexer;
}

query       
    : select_clause where_clause?;

select_clause 
    : SELECT column (COMMA column)* FROM sources;

column      
    : WILDCARD
    | operand (AS IDENTIFIER)?
    ;

sources    
    : WILDCARD
    | IDENTIFIER (COMMA IDENTIFIER)?
    ;

where_clause 
    : WHERE expression (operator expression)*;

expression   
    : operand
    | expression operator expression
    ;

operand
    : IDENTIFIER (DOT IDENTIFIER)?
    | STRING
    | NUMBER
    ;

operator
    : EQUALS
    | LESS
    | GREATER
    | LESS_EQUALS
    | GREATER_EQUALS
    ;

YQLではSQLとは異なり、FROM句で複数のデータソースを指定できるため、IDENTIFIERをカンマ区切りで指定します。
また、SELECT句やFROM句でワイルドカード（*）を指定できるため、WILDCARDを定義します。
WHERE句では、比較演算子（=、<、>、<=、>=）を定義します。
また、WHERE句では複数の条件がANDやORで結合される場合があります。
そのため、expressionルールを再帰的に定義します。
この再帰的な構造により、age > 30 AND (salary < 50000 OR department = "HR")のような複雑な条件を解析できます。
実際は括弧の考慮や優先順位の定義が必要ですが、今回は簡略化しています。

この文法を使うと、以下のようなクエリを解析できます。

SELECT name, age FROM users WHERE age >= 30

文法の可視化

拡張機能を利用すると、文法の確認にRailroad Diagramなど色々な形式のグラフで視覚的に確認することができます。

ANTLRで作成した文法をRailroad Diagramで視覚化すると、以下のように文法構造を理解しやすくなります。

select_clause：SELECTキーワードに続く列名（カンマ区切り）とFROM句を表します。
where_clause：WHEREキーワードの後に続く条件式を示します。

3. パーサーの生成

文法ファイルからGoコードを生成するには、以下のコマンドを実行します。

antlr4 -Dlanguage=Go -o generated YQLLexer.g4 YQLParser.g4

これにより、generatedディレクトリ内にLexerやParserのクラスが生成されます。
開発環境の拡張機能を利用すれば、文法ファイルの保存時に自動生成されるため便利です。

4. クエリの解析

以下は生成されたクラスを使い、YQLを解析するGoコードの例です。

package main

import (
	"fmt"
	parser "yql-formatter/internal/grammers/gen"
	antlr "github.com/antlr4-go/antlr/v4"
)

func main() {
    // 解析するYQLクエリ
    input := `SELECT name, age FROM users WHERE age >= 30`

	// ANTLRの入力ストリーム
	is := antlr.NewInputStream(input)

	// LexerとParserを生成
	lexer := parser.NewYQLLexer(is)
	stream := antlr.NewCommonTokenStream(lexer, antlr.TokenDefaultChannel)
	p := parser.NewYQLParser(stream)

	// 構文解析
	tree := p.Query()

	// 構文木を表示
	fmt.Println(tree.ToStringTree(nil, p))
}

サンプル出力

このコードを実行すると、以下の構文木が得られます。
構文木は、クエリ構造を階層的に表現したものです。この解析結果を基に、フォーマッターやクエリ検証ツールを実装できます。

(query (select_statement SELECT (summary_fields (indexing (summary name)) , (indexing (summary age))) from (sources account) (where_clause WHERE (expression (expression (operand age)) (comparison_operator =) (expression (operand "30"))))) <EOF>)

この構文木では、SELECT句のフィールドリスト、FROM句のデータソース、WHERE句の条件式がそれぞれのノードとして分割されています。
たとえば、(operand age)はフィールド名ageを指し、(operator >=)は比較演算子を表します。
このようにクエリの各部分を明確に分解することで、フォーマッターやクエリ最適化に利用できます。

まとめ

ANTLRは、文法の定義からトークン分解・構文解析までを簡単に実現できるツールです。
今回の例では簡略化して基本的な文法のみを扱いましたが、必要に合わせてより高度な機能を追加することで実用性を高められます。
ASTや構文木は再帰的な構造なため、構造を把握するためのツールが不可欠です。
ANTLRでは、文法ファイルを通して、スキーマを作れ、自動生成までできるので使い勝手が良いです。

木構造が必要な文字列処理、DSLやクエリ解析に困ったときの選択肢としてぜひ活用してみてください。

明日は@moritanuさんの記事がでるそうです！ぜひご覧ください！