作者：谢其骏
北京航空航天大学在读硕士， Databend 研发工程师实习生
https://github.com/jun0315
基本介绍
Parser 模块主要负责将 SQL 字符串经过词法分析得到的 Token 列表转换为 AST（抽象语法树）的过程。
下面是函数定义：
/// 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 接受两个参数：sql_tokens 和 dialect，返回一个 Result，其中包含一个 Statement 和一个可选的输出格式String（如 CSV 格式等）。
sql_tokens 参数是一个对 SQL 语句进行词法分析之后得到的Token数组，令牌包含关键字、标识符、运算符等信息。
dialect 参数表示 SQL 方言，Rust 提供了几种常见的方言，比如 SQLite、MySQL 等。
parse_sql 函数的主要作用是将 SQL 的 Token 解析为 AST（ Abstract Syntax Tree 抽象语法树）。AST 是一个用于表示程序语言语法结构的树形数据结构，它的节点代表程序语法的不同部分，通过这个数据结构可以更方便地对程序语言进行分析和处理。
Nom 库
Databend 的 Parser 模块主要使用了nom 库和 nom-rule 库。
nom是一个基于parser组合器的库，它允许开发者定义小型的 parser，然后将它们组合成更复杂的 parser。
nom-rule 是基于 nom 库的一个规则引擎库，可以用于语法分析、解析和转换。它提供了一种声明式的方式来定义语法规则，同时支持错误处理和自定义语法扩展。
2.1 parser
在 nom 中，parser是一个 trait，定义了一个通用的解析器接口，任何实现了该 trait 的解析器都可以用于解析。这个 trait 定义了一个名为parse的方法，该方法接受一个输入数据，进行解析，返回一个IResult类型的结果，I、O 和 E 分别表示剩余未解析的数据、解析结果和错误类型。
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 组件是一个函数式编程工具，用于将解析器解析出的数据转换为其他类型或格式。map 组件接受两个参数：一个解析器和一个函数，用于将解析器的结果转换为另一种格式。
map 组件的函数参数是一个闭包，它接受解析器解析出的数据，并将其转换为其他类型或格式。通常，闭包的返回值将成为解析器的最终结果。下面是一个简单的示例：
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 digit1assert_eq!(parser.parse("123456"), Ok(("", 6)));
// this will fail if digit1 failsassert_eq!(parser.parse("abc"), Err(Err::Error(("abc", ErrorKind::Digit))));
复制代码
在这个例子中，首先使用了 nom 中的digit1 parser 组件来解析连续的数字字符，然后使用map组件对解析结果进行转换，将数字字符串的长度作为解析结果返回。
2.3 alt
alt 是一个组合子，它用于在多个解析器之间进行选择。它接受两个或多个解析器作为参数，并依次尝试将输入数据解析为这些解析器中的一个，返回第一个成功解析的结果。下面是一个简单的示例：
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 inputassert_eq!(parser("abc"), Ok(("", "abc")));
// the first parser returns an error, so alt tries the second oneassert_eq!(parser("123456"), Ok(("", "123456")));
// both parsers failed, and with the default error type, alt will return the last errorassert_eq!(parser(" "), Err(Err::Error(error_position!(" ", ErrorKind::Digit))));
复制代码
在这个例子中，我们使用alt组件将两个 parser 拼接在一起：alpha1和digit1。这两个 parser 都是 nom 中的字符解析器，alpha1解析一个或多个字母，digit1解析一个或多个数字。因此，alt尝试首先使用alpha1解析输入，如果解析成功，则返回其结果（即解析的字母字符串）。否则，alt将使用digit1解析输入，如果解析成功，则返回其结果（即解析的数字字符串）。如果两个 parser 都解析失败，则返回一个错误。
2.4 tuple
tuple 是一个组合子，用于将多个解析器按顺序组合起来，形成一个元组。
除了可以嵌套多个解析器之外，tuple 还支持使用 map 函数对解析结果进行转换。
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会将多个解析器打包成一个元组返回，元组中包含了每个解析器的结果。
在上面的例子中，tuple包含了三个解析器：alpha1，digit1和另一个alpha1。它们按顺序解析输入字符串中的字符，并将结果打包成一个三元组。
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 ）的方法，接着再调用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)(";"), )) );
复制代码
摘自 https://github.com/andylokandy/nom-rule#example
源码分析
在了解了 parser 组件之后，我们继续探究实际的源码。
在parser_sql函数中，调用了statement(Input(sql_tokens, dialect, &backtrace))。
statement函数实际上解析 token 的地方：
map( rule! { #statement_body ~ (FORMAT ~ #ident)? ~ ";"? ~ &EOI }, |(stmt, opt_format, _, _)| StatementMsg { stmt, format: opt_format.map(|(_, format)| format.name), },)(i)
复制代码
通过调用 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 组件，会转换成Statement。delete会最终转换成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 来转换成Statement。至此，整个 Parser 解析的过程就完成了。
关于 Databend
Databend 是一款开源、弹性、低成本，基于对象存储也可以做实时分析的新式数仓。期待您的关注，一起探索云原生数仓解决方案，打造新一代开源 Data Cloud。
👨💻 Databend Cloud：https://databend.cn
📖 Databend 文档：https://databend.rs/
💻 Wechat：Databend
✨ GitHub：https://github.com/datafuselabs/databend
评论