作者:謝其駿
北京航空航天大學(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 語句進(jìn)行詞法分析之后得到的Token
數(shù)組,令牌包含關(guān)鍵字、標(biāo)識符片林、運(yùn)算符等信息。
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)可以更方便地對程序語言進(jìn)行分析和處理衣盾。
Nom 庫
Databend 的 Parser 模塊主要使用了nom 庫和 nom-rule 庫寺旺。
nom
是一個基于parser
組合器的庫爷抓,它允許開發(fā)者定義小型的 parser,然后將它們組合成更復(fù)雜的 parser阻塑。
nom-rule
是基于 nom
庫的一個規(guī)則引擎庫蓝撇,可以用于語法分析、解析和轉(zhuǎn)換陈莽。它提供了一種聲明式的方式來定義語法規(guī)則渤昌,同時支持錯誤處理和自定義語法擴(kuò)展虽抄。
2.1 parser
在 nom 中,parser
是一個 trait独柑,定義了一個通用的解析器接口迈窟,任何實現(xiàn)了該 trait 的解析器都可以用于解析。這個 trait 定義了一個名為parse
的方法忌栅,該方法接受一個輸入數(shù)據(jù)车酣,進(jìn)行解析,返回一個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é)果進(jìn)行轉(zhuǎn)換,將數(shù)字字符串的長度作為解析結(jié)果返回蒸眠。
2.3 alt
alt
是一個組合子漾橙,它用于在多個解析器之間進(jìn)行選擇。它接受兩個或多個解析器作為參數(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é)果進(jìn)行轉(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