RustでSQLパーサーを書く(SELECT文)
前回の続き。今回はSELECT文をパースしてASTに落としてみます。
SELECT文の仕様
字句解析してTokenに落としたので、それを先頭から呼んでいって構文木に落としてみます。
リファレンスなどを参考にして抜粋したBNFが下記になります。
<query specification> ::=
SELECT [ <set quantifier> ] <select list> <table expression><select list> ::=
<asterisk>
| <select sublist> [ { <comma> <select sublist> }... ]<table expression> ::=
<from clause>
[ <where clause> ]
[ <group by clause> ]
[ <having clause> ]
[ <window clause> ]
まずは簡単に実装したいのと細かく仕様を追っていくと満たせすべき式が多くて大変なので、ざっくり雑に下記のようにやっていこうと思います。(一旦whereまで。)
<select statement> ::=
SELECT [ <expression> ] <table expression><table expression> ::=
<from clause>
[ <where clause> ]<where clause> ::= <value expression><value expression> ::= <clause> | <clause> (+|-|+|/|=|AND|OR) <clause>
<clause> ::= <identifier> | <number> | <function>...
抽象構文木(AST)
value expressionを下記の用に定義してみました。
table expressionは下記です。
最終的なselect statementは下記です。カラムはaliasがあるのでvalue expressionをラップしました。
構文解析
parserはlexerと現在位置(current_token)と一つ先の位置(peek_token)のTokenを持っています。
まず先頭のTokenがSELECTであればSELECT文と期待してパースしていきます。その後、current_tokenとpeek_tokenが期待したものであるかどうかをチェックしながらパースしていきます。
FROM区に到達したらtable expressionと期待してパースしていきます。次にテーブル名取得して、次にWHERE句があるならvalue expressionとしてパースしていきます。
結果
がっつり端折りましたがprefix expression(ex. -x)やinfix expression(ex. a + b)をパースするために、Pratt構文解析を利用しましたがそれは別途やる気になったら書きます。
input
SELECT id, name FROM user WHERE id = 1;output
Select {
columns: [
Column { value: Identifier("id"), alias: "" },
Column { value: Identifier("name"), alias: "" }
],
table: TableExpression {
from: "user",
where_cond: Some(
Infix {
op: Eq,
left: Identifier("id"),
right: Number(1)
}
)
}
}期待通りにパースできた気がします。ColumnとWHEREを同じ式としてパースしてますが、厳密には違そうなので改善の余地はまだありそうです。
SELECT文としてはまだorder by、group by、havingなどあるので対応しつつ、他の文やDDLあたりもやっていけたらなと思います。
