databend中sql解析器是基于nom來完成的，接下來結(jié)合一個樣例：explain語句

let explain = map_res( // 需要完成sql輸入解析的Parser以及將解析完成后的輸出提供給閉包函數(shù)
        rule! {
            EXPLAIN ~ ( AST | SYNTAX | PIPELINE | JOIN | GRAPH | FRAGMENTS | RAW | OPTIMIZED | MEMO )? ~ #statement
        }, // 解析器
        |(_, opt_kind, statement)| { // 用于使用nom的parser解Input后的結(jié)果當(dāng)成輸入?yún)?shù)，提供給當(dāng)前的閉包函數(shù)
            Ok(Statement::Explain {
                kind: match opt_kind.map(|token| token.kind) {
                    Some(TokenKind::AST) => {
                        let formatted_stmt = format_statement(statement.stmt.clone())
                            .map_err(|_| ErrorKind::Other("invalid statement"))?;
                        ExplainKind::Ast(formatted_stmt)
                    }
                    Some(TokenKind::SYNTAX) => {
                        let pretty_stmt = pretty_statement(statement.stmt.clone(), 10)
                            .map_err(|_| ErrorKind::Other("invalid statement"))?;
                        ExplainKind::Syntax(pretty_stmt)
                    }
                    Some(TokenKind::PIPELINE) => ExplainKind::Pipeline,
                    Some(TokenKind::JOIN) => ExplainKind::JOIN,
                    Some(TokenKind::GRAPH) => ExplainKind::Graph,
                    Some(TokenKind::FRAGMENTS) => ExplainKind::Fragments,
                    Some(TokenKind::RAW) => ExplainKind::Raw,
                    Some(TokenKind::OPTIMIZED) => ExplainKind::Optimized,
                    Some(TokenKind::MEMO) => ExplainKind::Memo("".to_string()),
                    None => ExplainKind::Plan,
                    _ => unreachable!(),
                },
                query: Box::new(statement.stmt),
            })
        },
    );

這里先介紹下nom實現(xiàn)解析文本的

關(guān)于nom實現(xiàn)解析文本: 一種是基于macro來完成的，另一種是function來完成的(目前最新的nom版本比較支持的)

直接引入官方的一個demo

use nom::character::complete::digit1;
use nom::combinator::map_res;

// 這里的組合器包括digit1用來判斷內(nèi)容是否為數(shù)字，當(dāng)滿足是數(shù)字字符串時，則繼續(xù)執(zhí)行后續(xù)的閉包進行類型轉(zhuǎn)換
let mut parse = map_res(digit1, |s: &str| s.parse::<u8>());

// the parser will convert the result of digit1 to a number
assert_eq!(parse("123"), Ok(("", 123)));

// this will fail if digit1 fails
assert_eq!(parse("abc"), Err(Err::Error(("abc", ErrorKind::Digit))));

// this will fail if the mapped function fails (a `u8` is too small to hold `123456`)
assert_eq!(parse("123456"), Err(Err::Error(("123456", ErrorKind::MapRes))));

關(guān)于nom中map_res的定義

pub fn map_res<I: Clone, O1, O2, E: FromExternalError<I, E2>, E2, F, G>(
    parser: F,   // 解析器
    f: G         // 針對解析處理后的內(nèi)容進行后續(xù)處理
) -> impl FnMut(I) -> IResult<I, O2, E>
where
    F: Parser<I, O1, E>,
    G: FnMut(O1) -> Result<O2, E2>,

不過在databend中map_res被改寫了：去掉了FromExternalError，其中被改寫的還有：separated_list1、separated_list0(將原有的函數(shù)聲明中的error定義剔除)
比如在databend中map_res的定義

pub fn map_res<'a, O1, O2, F, G>(
    mut parser: F,  // 使用的parser，一般是nom中的parser
    mut f: G,       // 閉包函數(shù)
) -> impl FnMut(Input<'a>) -> IResult<'a, O2>
where
    F: nom::Parser<Input<'a>, O1, Error<'a>>,
    G: FnMut(O1) -> Result<O2, ErrorKind>,

在databend中如何進行sql解析

map_res( // 需要完成sql輸入解析的Parser以及將解析完成后的輸出提供給閉包函數(shù)
    rule! {
            EXPLAIN ~ ( AST | SYNTAX | PIPELINE | JOIN | GRAPH | FRAGMENTS | RAW | OPTIMIZED | MEMO )? ~ #statement
    }, // 解析器
   | (_, opt_kind, statement)| {
      // 省略代碼
   },
)

map_res來完成sql解析，主要有兩部分：

• rule!(解析器集) 通過解析使用 BNF 來定義 SQL 的語法規(guī)則，
• |(_, opt_kind, statement)|{} 閉包 用于對解析器處理后的內(nèi)容進行處理，獲取當(dāng)前statement的kind

sql解析

通過將用戶輸入的sql字符串提供給詞法解析器生成token序列，接著將token序列提供給語法解析器，并結(jié)合指定的sql方言/語義最終生成statement；
在語法解析過程會進行sql語法檢查，若是整個sql沒有問題就會輸出抽象語法樹AST.

// 樣例sql
select a + 1 from t

// 通過語法解析器輸出抽象語法樹(AST)
SelectStatement {
    projection: Expr::BinaryOp {
        op: Op::Plus,
        args: [
            Expr::ColumnRef("a"),
            Expr::Constant(Scalar::Int(1))
        ]
    }
    from: "t",
}

sql解析分成兩個階段：Tokenize(分詞) 和 Parsing(解析)階段

• Tokenize分詞token化
  主要是將用戶輸入的sql字符串切分成具有獨立語義的單元，稱為token； 一般是通過正則表達式從字符串中識別相鄰有意義的部分，比如關(guān)鍵字、變量名
  、常量、操作符
  類似如下定義

Ident = [_a-zA-Z][_$a-zA-Z0-9]*
Number = [0-9]+
Plus = +
SELECT = SELECT
FROM = FROM

按照從上到下順序嘗試匹配正則表達式，并一直重復(fù)這個步驟最終得到token序列
比如 select a+1 from t，token化序列如下

[
    Keyword(SELECT),
    Ident(a),
    BinOp(+),
    Number(1),
    Keyword(FROM),
    Ident(t),
]

接下來就是parsing階段，首先先來了解下BNF來定義sql語法規(guī)則

關(guān)于BNF定義sql語法規(guī)則

主要來描述了有意義的Token如何進行組合

<select_statement> ::= SELECT <expr> FROM <ident>
<expr> ::= <number>
         | <ident>
         | <expr> <op> <expr>
<op> ::= + | - | * | /

• Parsing解析statement
  在databend中使用BNF來定義sql語法規(guī)則，將上面生成的token序列輸入到解析器，進而生成AST

SelectStatement {
    projection: Expr::BinaryOp {
        op: Op::Plus,
        args: [
            Expr::ColumnRef("a"),
            Expr::Constant(Scalar::Int(1))
        ]
    }
    from: "t",
}

自此sql statement就形成了。

databend的sql token和parsing階段的實現(xiàn)

在databend中使用logos和nom來分別完成token化和解析：
1、使用logos庫來完成sql字符串token化, 詳情見databend sql字符串token化
在databend中定義了TokenKind的enum枚舉類型，每個TokenKind對應(yīng)一個特定的Token: 例如關(guān)鍵字、變量名、常量和操作符。并且每個TokenKind都會有
一個單獨的正則表達式進行匹配，以確保準確地從輸入字符串中提取token，將TokenKind和Logos庫整合，最終編譯一個高效的狀態(tài)機和跳表來達到超過手寫Tokenizer
的極快的分詞性能

#[allow(non_camel_case_types)]
#[derive(Logos)]
pub enum TokenKind {
    #[regex(r"[ \t\r\n\f]+", logos::skip)]
    Whitespace,

    #[regex(r#"[_a-zA-Z][_$a-zA-Z0-9]*"#)]
    Ident,
    #[regex(r"[0-9]+")]
    Number,

    #[token("+")]
    Plus,

    #[token("SELECT", ignore(ascii_case))]
    SELECT,
    #[token("FROM", ignore(ascii_case))]
    FROM,
}

將“select a+1 from t”進行token化,如下

[
    Token { kind: TokenKind::Select, text: "SELECT", span: 0..6 },
    Token { kind: TokenKind::Ident, text: "a", span: 7..8 },
    Token { kind: TokenKind::Plus, text: "+", span: 9..10 },
    Token { kind: TokenKind::Number, text: "1", span: 11..12 },
    Token { kind: TokenKind::From, text: "from", span: 13..17 },
    Token { kind: TokenKind::Ident, text: "t", span: 18..19 },
]

除了 TokenKind 的定義，Token 本身還包括了一個重要的屬性——span。span 記錄了 Token 在原始字符串中的起始和結(jié)束位置。

2、使用nom實現(xiàn)遞歸下降sql解析器，同時nom自身語法規(guī)則構(gòu)建過程相對繁瑣，所以定義了rule!()過程宏，并使用BNF來定義語法規(guī)則， 自動生成nom解析器

// databend中rule過程宏
rule! {
    EXPLAIN ~ ( AST | SYNTAX | PIPELINE | JOIN | GRAPH | FRAGMENTS | RAW | OPTIMIZED | MEMO )? ~ #statement
}

// 底層使用nom中的nom_rule::rule!來完成的
#[macro_export]
macro_rules! rule {
    ($($tt:tt)*) => { nom_rule::rule!(
        $crate::match_text,
        $crate::match_token,
        $($tt)*)
    }
}

在databend中使用nom來實現(xiàn)遞歸下降sql解析器，其中有兩個比較主要的parser組成
1、Terminal Parser：是最基本的解析器，用于匹配特定的TokenKind的Token。在databend中定義了match_token()和match_text()這兩個Terminal Parser

fn match_text(text: &str) -> impl FnMut(&[Token]) -> IResult<&[Token], Token> {
    satisfy(|token: &Token| token.text == text)(i)
}

fn match_token(kind: TokenKind) -> impl FnMut(&[Token]) -> IResult<&[Token], Token> {
    satisfy(|token: &Token| token.kind == kind)(i)
}

2、 Combinator parser：允許將多個小的解析器組合成較大的解析器。也是構(gòu)建復(fù)雜邏輯的基礎(chǔ)。以下是一些常見的組合器：

 -* tuple(a, b, c)：會讓多個 parser 按順序排列（例如先是 a，然后是 b，接著是 c）。它們需要按照預(yù)期的順序逐個成功才算作最后的成功。
 -* alt(a, b, c)：嘗試多個 parser 分支（例如 a，b 或 c），直到滿足第一個成功條件。如果全部失敗，解析器將報告錯誤。
 -* many0(a)：貪婪地循環(huán)調(diào)用相同的 parser。如果無法繼續(xù)，這個解析器將成功返回已匹配的 Token 序列?？赡転榭?。
 -* many1(a)：貪婪地循環(huán)調(diào)用相同的 parser，但至少需要匹配成功一次。如果至少匹配成功一次，解析器會返回 Token 序列。
 -* opt(a)：允許 parser 失敗。當(dāng) parser 失敗時，將返回 `None`。成功時將返回成功匹配的結(jié)果。

舉個例子：

 <select_statement> ::= SELECT <expr>+ FROM <ident>

接下來使用nom來組裝語法樹: 使用match_token識別關(guān)鍵字；使用many1來實現(xiàn)循環(huán)多個 <expr>+。

tuple((
    match_token(SELECT),
    many1(expr),
    match_token(FROM),
    match_token(Ident),
))

將‘select a+1 from t’進行token化和解析，結(jié)果如下：

Query {
    span: Some(0..17,),
    with: None,
    body: Select(
            SelectStmt {
                span: Some(0..17,),
                hints: None,
                distinct: false,
                select_list: [
                    AliasedExpr {
                        expr: BinaryOp {
                                span: Some(8..9,),
                                op: Plus,
                                left: ColumnRef {
                                    span: Some(7..8,),
                                    database: None,
                                    table: None,
                                    column: Name(
                                        Identifier {
                                            name: \"a\",
                                            quote: None,
                                            span: Some(7..8,),
                                        },
                                    ),
                                },
                                right: Literal {
                                      span: Some(9..10,),
                                      lit: UInt64(1,),
                                },
                        },
                        alias: None,
                    },
                ],
                from: [
                    Table {
                        span: Some(16..17,),
                        catalog: None,
                        database: None,
                        table: Identifier {
                            name: \"t\",
                            quote: None,
                            span: Some(16..17, ),
                        },
                        alias: None,
                        travel_point: None,
                        pivot: None,
                        unpivot: None,
                    },
                ],
                selection: None,
                group_by: None,
                having: None,
                window_list: None,
            },
    ),
    order_by: [],
    limit: [],
    offset: None,
    ignore_result: false,
}