作者：謝其駿
北京航空航天大學(xué)在讀碩士， Databend 研發(fā)工程師實習(xí)生
基本介紹
Parser 模塊主要負(fù)責(zé)將 SQL 字符串經(jīng)過詞法分析得到的 Token 列表轉(zhuǎn)換為 AST（抽象語法樹）的過程。
下面是函數(shù)定義：
/// Parse a SQL string into `Statement`s.
pub fn parse_sql<'a>(
sql_tokens: &'a [Token<'a>],
dialect: Dialect,
) -> Result<(Statement, Option<String>)>
parse_sql 接受兩個參數(shù)：sql_tokens 和 dialect，返回一個 Result，其中包含一個 Statement 和一個可選的輸出格式String（如 CSV 格式等）。
sql_tokens 參數(shù)是一個對 SQL 語句進行詞法分析之后得到的Token數(shù)組，令牌包含關(guān)鍵字、標(biāo)識符、運算符等信息。
dialect 參數(shù)表示 SQL 方言，Rust 提供了幾種常見的方言，比如 SQLite、MySQL 等。
parse_sql 函數(shù)的主要作用是將 SQL 的 Token 解析為 AST（ Abstract Syntax Tree 抽象語法樹）。AST 是一個用于表示程序語言語法結(jié)構(gòu)的樹形數(shù)據(jù)結(jié)構(gòu)，它的節(jié)點代表程序語法的不同部分，通過這個數(shù)據(jù)結(jié)構(gòu)可以更方便地對程序語言進行分析和處理。
Nom 庫
Databend 的 Parser 模塊主要使用了nom 庫和 nom-rule 庫。
nom是一個基于parser組合器的庫，它允許開發(fā)者定義小型的 parser，然后將它們組合成更復(fù)雜的 parser。
nom-rule 是基于 nom 庫的一個規(guī)則引擎庫，可以用于語法分析、解析和轉(zhuǎn)換。它提供了一種聲明式的方式來定義語法規(guī)則，同時支持錯誤處理和自定義語法擴展。
2.1 parser
在 nom 中，parser是一個 trait，定義了一個通用的解析器接口，任何實現(xiàn)了該 trait 的解析器都可以用于解析。這個 trait 定義了一個名為parse的方法，該方法接受一個輸入數(shù)據(jù)，進行解析，返回一個IResult類型的結(jié)果，I、O 和 E 分別表示剩余未解析的數(shù)據(jù)、解析結(jié)果和錯誤類型。
pub trait Parser<I, O, E> {
/// A parser takes in input type, and returns a `Result` containing
/// either the remaining input and the output value, or an error
fn parse(&mut self, input: I) -> IResult<I, O, E>;
}
接下來，我們將介紹一些 Databend 中用到的重要的 parser 組件。
2.2 map
map 組件是一個函數(shù)式編程工具，用于將解析器解析出的數(shù)據(jù)轉(zhuǎn)換為其他類型或格式。map 組件接受兩個參數(shù)：一個解析器和一個函數(shù)，用于將解析器的結(jié)果轉(zhuǎn)換為另一種格式。
map 組件的函數(shù)參數(shù)是一個閉包，它接受解析器解析出的數(shù)據(jù)，并將其轉(zhuǎn)換為其他類型或格式。通常，閉包的返回值將成為解析器的最終結(jié)果。下面是一個簡單的示例：
use nom::{Err,error::ErrorKind, IResult,Parser};
use nom::character::complete::digit1;
use nom::combinator::map;
let mut parser = map(digit1, |s: &str| s.len());
// the parser will count how many characters were returned by digit1
assert_eq!(parser.parse("123456"), Ok(("", 6)));
// this will fail if digit1 fails
assert_eq!(parser.parse("abc"), Err(Err::Error(("abc", ErrorKind::Digit))));
在這個例子中，首先使用了 nom 中的digit1 parser 組件來解析連續(xù)的數(shù)字字符，然后使用map組件對解析結(jié)果進行轉(zhuǎn)換，將數(shù)字字符串的長度作為解析結(jié)果返回。
2.3 alt
alt 是一個組合子，它用于在多個解析器之間進行選擇。它接受兩個或多個解析器作為參數(shù)，并依次嘗試將輸入數(shù)據(jù)解析為這些解析器中的一個，返回第一個成功解析的結(jié)果。下面是一個簡單的示例：
use nom::character::complete::{alpha1, digit1};
use nom::branch::alt;
fn parser(input: &str) -> IResult<&str, &str> {
alt((alpha1, digit1))(input)
};
// the first parser, alpha1, recognizes the input
assert_eq!(parser("abc"), Ok(("", "abc")));
// the first parser returns an error, so alt tries the second one
assert_eq!(parser("123456"), Ok(("", "123456")));
// both parsers failed, and with the default error type, alt will return the last error
assert_eq!(parser(" "), Err(Err::Error(error_position!(" ", ErrorKind::Digit))));
在這個例子中，我們使用alt組件將兩個 parser 拼接在一起：alpha1和digit1。這兩個 parser 都是 nom 中的字符解析器，alpha1解析一個或多個字母，digit1解析一個或多個數(shù)字。因此，alt嘗試首先使用alpha1解析輸入，如果解析成功，則返回其結(jié)果（即解析的字母字符串）。否則，alt將使用digit1解析輸入，如果解析成功，則返回其結(jié)果（即解析的數(shù)字字符串）。如果兩個 parser 都解析失敗，則返回一個錯誤。
2.4 tuple
tuple 是一個組合子，用于將多個解析器按順序組合起來，形成一個元組。
除了可以嵌套多個解析器之外，tuple 還支持使用 map 函數(shù)對解析結(jié)果進行轉(zhuǎn)換。
use nom::sequence::tuple;
use nom::character::complete::{alpha1, digit1};
let mut parser = tuple((alpha1, digit1, alpha1));
assert_eq!(parser("abc123def"), Ok(("", ("abc", "123", "def"))));
assert_eq!(parser("123def"), Err(Err::Error(("123def", ErrorKind::Alpha))));
這段代碼演示了如何使用tuple組合子將多個解析器按順序組合起來。tuple會將多個解析器打包成一個元組返回，元組中包含了每個解析器的結(jié)果。
在上面的例子中，tuple包含了三個解析器：alpha1，digit1和另一個alpha1。它們按順序解析輸入字符串中的字符，并將結(jié)果打包成一個三元組。
2.5 rule!
#[macro_export]
macro_rules! rule {
($($tt:tt)*) => { nom_rule::rule!(
$crate::match_text,
$crate::match_token,
$($tt)*)
}
}
rule! 首先給定了 match_text（匹配文本）和 match_token（匹配 TokenKind ）的方法，接著再調(diào)用nom_rule中的 rule 宏定義，這樣可以方便的拼裝成上文提到的tuple組合子。
舉例如下
let mut rule = rule!(
CREATE ~ TABLE ~ #ident ~ ^"(" ~ (#ident ~ #ident ~ ","?)* ~ ")" ~ ";" : "CREATE TABLE statement"
);
最終會被展開為
let mut rule =
nom::error::context(
"CREATE TABLE statement",
nom::sequence::tuple((
(crate::match_token)(CREATE),
(crate::match_token)(TABLE),
ident,
(nom::combinator::cut(crate::match_text)("(")),
nom::multi::many0(nom::sequence::tuple((
ident,
ident,
nom::combinator::opt((crate::match_text)(",")),
))),
(crate::match_text)(")"),
(crate::match_text)(";"),
))
);
源碼分析
在了解了 parser 組件之后，我們繼續(xù)探究實際的源碼。
在parser_sql函數(shù)中，調(diào)用了statement(Input(sql_tokens, dialect, &backtrace))。
statement函數(shù)實際上解析 token 的地方：
map(
rule! {
#statement_body ~ (FORMAT ~ #ident)? ~ ";"? ~ &EOI
},
|(stmt, opt_format, _, _)| StatementMsg {
stmt,
format: opt_format.map(|(_, format)| format.name),
},
)(i)
通過調(diào)用 rule 宏定義，解析statement_body，而statement也是用 alt 組件拼成的多個 parser 。
let statement_body = alt((
rule!(
#map(query, |query| Statement::Query(Box::new(query)))
| #explain : "`EXPLAIN [PIPELINE | GRAPH] <statement>`"
| #explain_analyze : "`EXPLAIN ANALYZE <statement>`"
| #delete : "`DELETE FROM <table> [WHERE ...]`"
| #update : "`UPDATE <table> SET <column> = <expr> [, <column> = <expr> , ... ] [WHERE ...]`"
| #show_settings : "`SHOW SETTINGS [<show_limit>]`"
| #show_stages : "`SHOW STAGES`"
| #show_engines : "`SHOW ENGINES`"
| #show_process_list : "`SHOW PROCESSLIST`"
| #show_metrics : "`SHOW METRICS`"
| #show_functions : "`SHOW FUNCTIONS [<show_limit>]`"
| #kill_stmt : "`KILL (QUERY | CONNECTION) <object_id>`"
| #set_role: "`SET [DEFAULT] ROLE <role>`"
| #show_databases : "`SHOW [FULL] DATABASES [(FROM | IN) <catalog>] [<show_limit>]`"
| #undrop_database : "`UNDROP DATABASE <database>`"
| #show_create_database : "`SHOW CREATE DATABASE <database>`"
| #create_database : "`CREATE DATABASE [IF NOT EXIST] <database> [ENGINE = <engine>]`"
| #drop_database : "`DROP DATABASE [IF EXISTS] <database>`"
| #alter_database : "`ALTER DATABASE [IF EXISTS] <action>`"
| #use_database : "`USE <database>`"
),
......
// catalog
rule!(
#show_catalogs : "`SHOW CATALOGS [<show_limit>]`"
| #show_create_catalog : "`SHOW CREATE CATALOG <catalog>`"
| #create_catalog: "`CREATE CATALOG [IF NOT EXISTS] <catalog> TYPE=<catalog_type> CONNECTION=<catalog_options>`"
| #drop_catalog: "`DROP CATALOG [IF EXISTS] <catalog>`"
),
));
每一個 parser，如第六行的delete都是 map 組件，會轉(zhuǎn)換成Statement。delete會最終轉(zhuǎn)換成Statement::Delete。
let delete = map(
rule! {
DELETE ~ FROM ~ #table_reference_only
~ ( WHERE ~ ^#expr )?
},
|(_, _, table_reference, opt_selection)| Statement::Delete {
table_reference,
selection: opt_selection.map(|(_, selection)| selection),
},
);
最終通過拼裝出來的 parser 來轉(zhuǎn)換成Statement。至此，整個 Parser 解析的過程就完成了。
關(guān)于 Databend
Databend 是一款開源、彈性、低成本，基于對象存儲也可以做實時分析的新式數(shù)倉。期待您的關(guān)注，一起探索云原生數(shù)倉解決方案，打造新一代開源 Data Cloud。
???? Databend Cloud：https://databend.cn
?? Databend 文檔：https://databend.rs/
?? Wechat：Databend
