一、前言

1.1 作者介紹

王波，SphereEx MeshLab 研發工程師，目前專注於 Database Mesh，Cloud Native 的研發。Linux，llvm，yacc，ebpf user。 Gopher & Rustacean and c bug hunter。

GitHub: https://github.com/wbtlb

1.2 背景

在上篇文章《Pisa-Proxy 之 SQL 解析實踐》中介紹了 Pisa-Proxy 的核心模塊之一 SQL 解析器的相關內容。在 MySQL 和 PostgreSQL 中 SQL 解析是通過 Yacc 實現的，同樣 Pisa- Proxy 的 SQL 解析器是由類似 Yacc 這樣的工具實現的，所以本篇文章會圍繞 SQL 解析器為大家介紹一些編譯原理和 Lex & Yacc 的使用，同時也會為讀者展示如何通過 Lex & Yacc 實現一個簡單的 SQL 解析器。從而幫助大家更好地理解 Pisa-Proxy 中 SQL 解析器是如何工作的。

二、編譯器初探

一個程序語言不論是我們常用的 Java，Golang 或者是 SQL 本質上都是一個記號系統，如同自然語言一樣，它的完整定義應該包括語法和語義兩個方面。一種語言的語法其實是對應的一組規則，用它可以形成和產生一個合適的程序。當前使用最廣泛的手段是上下文無關的文法，上下文無關的文法作為程序設計語言語法的描述工具。語法只是定義什麼樣的符號序列是合法的，與這些符號的含義毫無關係。然而在語義中分為兩類：靜態語義和動態語義。靜態語義是指一系列的限定規則，並確定哪些語法對於程序來説是合適的；動態語義也稱作運行語義或者執行語義，明確程序具體要計算什麼。

2.1 編譯器工作流程

如圖 2.1.1 中所示，通常編譯器將源代碼編譯成可執行文件主要有以下幾步：

1. 對源文件進行掃描，將源文件的字符流拆分分一個個的詞（token），此為詞法分析
2. 根據語法規則將這些記號構造出語法樹，此為語法分析
3. 對語法樹的各個節點之間的關係進行檢查，檢查語義規則是否被違背，同時對語法樹進行必要的優化，此為語義分析
4. 遍歷語法樹的節點，將各節點轉化為中間代碼，並按特定的順序拼裝起來，此為中間代碼生成
5. 對中間代碼進行優化
6. 將中間代碼轉化為目標代碼
7. 對目標代碼進行優化，生成最終的目標程序

對於 SQL 解析來説，就可以將上圖中的步驟簡化為如圖 2.1.2 的形式，源碼輸入（SQL 語句），將 SQL 語句進行詞法分析，生成 SQL 中特定的 token 記號流。然後拿到記號流後進行語法分析後生成最終的 SQL AST。

2.2 詞法分析

上文中提到，無論是編譯器還是 SQL 解析器有一個關鍵步驟就是要對源文件做詞法分析，詞法分析我們可以理解為對 SQL 語句本身做分詞處理。那麼在這個階段，SQL 解析器要做的工作就是從左到右掃描源文件，將 SQL 語句分割成一個個的 token，這裏説的 token 是指 SQL 中不能再進一步分割的一串字符。例如圖 2.1.2 中的 SQL 語句，經過詞法分析後，生成的 token 為：SELECT、*、FROM、pisa_proxy 等等。

在 SQL 語句中能用到的 token 類別也是有限的，比如保留字 SELECT、INSERT、DELETE 等等。還有操作符，比如：算術操作符、比較操作符。還有標識符，比如：內置函數名等等。在此階段每掃描一個 token 會被維護到一個數據結構中，然後在下個階段語法分析階段使用。
通常來説，詞法分析有直接掃描，正則匹配掃描方式。

2.2.1 直接掃描法

直接掃描法邏輯非常清晰，每次掃描根據第一個字符判斷屬於哪種類型的 token，然後採取不同的策略掃描出一個完整的 token，然後再進行下一輪掃描。在 Pisa-Proxy 中的 SQL 解析中，詞法分析就採用了這種實現方式，用 Python 展示如何實現一個簡單的 SQL 詞法分析器對 SQL 進行掃描，代碼如下：

# -*- coding: utf-8 -*-

single_char_operators_typeA = {
    ";", ",", "(", ")","/", "+", "-", "*", "%", ".",
}

single_char_operators_typeB = {
    "<", ">", "=", "!"
}

double_char_operators = {
    ">=", "<=", "==", "~="
}

reservedWords = {
    "select", "insert", "update", "delete", "show",
    "create", "set", "grant", "from", "where"
}

class Token:
    def __init__(self, _type, _val = None):
        if _val is None:
            self.type = "T_" + _type;
            self.val = _type;
        else:
            self.type, self.val = _type, _val

    def __str__(self):
        return "%-20s%s" % (self.type, self.val)

class NoneTerminateQuoteError(Exception):
    pass

def isWhiteSpace(ch):
    return ch in " \t\r\a\n"

def isDigit(ch):
    return ch in "0123456789"

def isLetter(ch):
    return ch in "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def scan(s):
    n, i = len(s), 0
    while i < n:
        ch, i = s[i], i + 1

        if isWhiteSpace(ch):
            continue

        if ch == "#":
            return

        if ch in single_char_operators_typeA:
            yield Token(ch)
        elif ch in single_char_operators_typeB:
            if i < n and s[i] == "=":
                yield Token(ch + "=")
            else:
                yield Token(ch)
        elif isLetter(ch) or ch == "_":
            begin = i - 1
            while i < n and (isLetter(s[i]) or isDigit(s[i]) or s[i] == "_"):
                i += 1
            word = s[begin:i]
            if word in reservedWords:
                yield Token(word)
            else:
                yield Token("T_identifier", word)
        elif isDigit(ch):
            begin = i - 1
            aDot = False
            while i < n:
                if s[i] == ".":
                    if aDot:
                        raise Exception("Too many dot in a number!\n\tline:"+line)
                    aDot = True
                elif not isDigit(s[i]):
                    break
                i += 1
            yield Token("T_double" if aDot else "T_integer", s[begin:i])
        elif ord(ch) == 34: # 34 means '"'
            begin = i
            while i < n and ord(s[i]) != 34:
                i += 1
            if i == n:
                raise Exception("Non-terminated string quote!\n\tline:"+line)
            yield Token("T_string", chr(34) + s[begin:i] + chr(34))
            i += 1
        else:
            raise Exception("Unknown symbol!\n\tline:"+line+"\n\tchar:"+ch)

if __name__ == "__main__":
    print "%-20s%s" % ("TOKEN TYPE", "TOKEN VALUE")
    print "-" * 50
    sql = "select * from pisa_proxy where id = 1;"
    for token in scan(sql):
        print token

最終的輸出結果如下：

TOKEN TYPE          TOKEN VALUE
--------------------------------------------------
T_select            select
T_*                 *
T_from              from
T_identifier        pisa_proxy
T_where             where
T_identifier        id
T_=                 =
T_integer           1
T_;                 ;

由上面的代碼我們可以看到，在一開始我們定義了幾個 token 類型，例如：reservedWords 數組中維護了 SQL 中的保留字，還有 SQL 中的操作符 single_char_operators_typeA。最終的執行結果我們可以看出，掃描器最終將一條 SQL 語句進行分詞最終拆成各自對應類型的 token。

2.2.2 正則表達式掃描法

其實程序的本質就是一組字符串，而語言可以看成合法程序的集合，因此編譯器或者説 SQL 解析的本質是判斷輸入的字符串是該語言的合法類型，另外也是將語言中的合法程序轉換成目標語言的合法程序。所以正則表達式掃描法的本質，也就是在一個有限狀態機裏來判斷字符串是否和正則表達式是否匹配，在後面的介紹中我們會提到 flex，flex 的本質其實是將用户用正則表達式寫的分詞匹配模式構造成一個有限狀態自動機。

2.3 語法分析

詞法分析結束後，SQL 語句的字符流被拆分成 token，那麼語法分析就是要分析出 SQL 的語法結構，將線性的 token 流轉化為樹狀結構，為後續的語義分析和 AST 生成做準備。在編譯器中，正則表達式還是難以表示程序語言所代表句子的集合，所以就引入的上下文無關文法，上下文無關文法能夠描述現今程序設計語言的語法結構。

以我們自然語言為例，假設有一種編程語言為 SQLX，它只包含主-謂-賓 這種結構來説，主語只有你、我、他，謂語只有愛，賓語有 Rust 和 Pisanix，那麼語法可以為以下這種形式：

語句 -> 主語 謂語 賓語
主語 -> 我
主語 -> 你
主語 -> 他
謂語 -> 愛
賓語 -> Rust
賓語 -> Pisanix

從上面的例子來看我們可以分別對主謂賓進行替換，從而寫出所有滿足此結構的語句。反過來講我們可以用任意語句和此結構對比來判斷它是否滿足 SQLX 語言。由此產生幾個概念，上面語法中形如“主語->謂語->賓語”的式子成為產生式

產生式左側的符號（語句、主語、謂語、賓語）稱為非終結符。而“我，你，他，愛，Rust，Pisanix”這些符號無法再產生新的符號，因此被稱為終結符，終結符只能出現在產生式右邊。語句這個詞為所有句子產生的起點，所以也被稱為起始符號。

通常把一個非 終結符的產生式寫在一起，用“｜”隔開，歸納如下：

語句 -> 主語 謂語 賓語
主語 -> 你｜我｜他
謂語 -> 愛
賓語 -> Rust | Pisanix

我們以一個 SQL 語句為例： SELECT 1 + 1，我們可以寫出這條語句的推到表達式為,分析樹如圖 2.3.1

Expr => Expr Expr + Expr => SELECT Expr + Expr => SELECT number + Expr => SELECT number + number => SELECT 1 + 2

2.3.1 兩種分析方法

語法分析包含兩種分析方法：

1. 自頂向下分析：自頂向下分析就是從起始符號開始，不斷的挑選出合適的產生式，將中間句子中的非終結符的展開，最終展開到給定的句子。
2. 自底向上分析：自底向上分析的順序和自頂向下分析的順序剛好相反，從給定的句子開始，不斷的挑選出合適的產生式，將中間句子中的子串摺疊為非終結符，最終摺疊到起始符號

在推導的過程中，每一步都只有唯一的一個產生式可以應用，每一步都可以排除掉其他所有的產生式。但在實際分析時，在中間過程中可能會遇到所有產生式都不可應用或者有多個產生式可以應用。對於第二種情況，需要採用回溯，先試探性的選擇一個產生式應用，若一直推導至最終句子（或起始符號），則表明此產生式是可用的，若推導下去遇到第一種情況，則回溯到此處，選擇另一個產生式。如果此處所有產生式都嘗試過了全部都遇到第一種情況，則表明最終句子不符合語法結構。如果此處有多條產生式可以推導至最終句子（或起始符號），則表明語法有歧義。回溯分析一般都非常慢，因此一般通過精心構造語法來避免回溯。

2.4 小結

以上內容主要介紹了編譯器的相關概念，和通過一個簡單的例子來直觀感受詞法分析的基本原理和工作過程，接下來我會為大家簡單介紹一下在詞法分析和語法分析中最常用到的兩個工具 Lex 和 Yacc。

三、認識 Lex 和 Yacc

3.1 認識 Lex

Flex（快速詞法分析器生成器）是 Lex 的免費開源軟件替代品。它是生成詞法分析器（也稱為“掃描器”或“詞法分析器”）的計算機程序。掃描儀是一種識別文本中的詞彙模式的程序，用來識別文本中的詞彙模式。

3.1.1 Lex由三部分組成

• 定義部分：定義段包括文字塊、定義、內部表聲明、起始條件和轉換。
• 規則部分：規則段為一系列匹配模式和動作，模式一般使用正則表達式書寫，動作部分為 C 代碼。
• 用户子程序段：這裏為 C 代碼，會被原樣複製到c文件中，一般這裏定義一些輔助函數等，如動作代碼中使用到的輔助函數。

這裏我們做一個簡單的例子，用 Lex 實現一個簡單的 SQL 詞法分析器，lex 代碼如下:

%{
#include <stdio.h>
%}

%%

select                 printf("KW-SELECT      : %s\n", yytext);
from                   printf("KW-FROM        : %s\n", yytext);
where                  printf("KW-WHERE       : %s\n", yytext);
and                    printf("KW-AND         : %s\n", yytext);
or                     printf("KW-OR          : %s\n", yytext);
[*]                    printf("IDENTIFIED     : %s\n", yytext);
[,]                    printf("IDENTIFIED     : %s\n", yytext);
[=]                    printf("OP-EQ          : %s\n", yytext);
[<]                    printf("KW-LT          : %s\n", yytext);
[>]                    printf("KW-GT          : %s\n", yytext);
[a-zA-Z][a-zA-Z0-9]*   printf("IDENTIFIED:    : %s\n", yytext);
[0-9]+                 printf("NUM:           : %s\n", yytext);
[ \t]+                 printf(" ");
.                      printf("Unknown : %c\n",yytext[0]);

%%

int main(int argc, char* argv[]) {
    yylex();
    return 0;
}

int yywrap() {
    return 1;
}

# flex sql.l # 用 flex 編譯 .l 文件生成 c 代碼
# ls
lex.yy.c sql.l
# gcc -o sql lex.yy.c # 編譯生成可執行二進制文件
# ./sql  # 執行二進制文件
select * from pisaproxy where id > 1 and sid < 2  # 輸入測試 sql
KW-SELECT      : select
IDENTIFIED     : *
KW-FROM        : from
IDENTIFIED:    : pisaproxy
KW-WHERE       : where
IDENTIFIED:    : id
KW-GT          : >
NUM:           : 1
KW-AND         : and
IDENTIFIED:    : sid
KW-LT          : <
NUM:           : 2

通過上面的例子我們可以看到，Lex 成功地將一條 SQL 語句拆分成了單獨的 token。

3.2 認識 Yacc

Yacc 是開發編譯器的工業級工具, 採用 LALR(1) 語法分析方法。LR(k) 分析方法，括號中的 k(k>=0) 表示向右查看輸入串符號的個數。LR 分析法給出一種能根據當前分析棧中的符號串和向右順序查看輸入串的 k 個符號就可唯一確定分析器的動作是移進還是規約和用哪個產生式規約。

Yacc 和 Lex 一樣，也包含由“%%”分隔的三個段：定義聲明、語法規則、C代碼段。

1. 定義段和預定義標記部分：

上面%{ %}的代碼和Lex一樣，一般稱為定義段。就是一些頭文件聲明，宏定義、變量定義聲明、函數聲明等。其中%left表示左結合，%right 表示右結合。最後列出的定義擁有最高的優先權。因此乘法和除法擁有比加法和減法更高的優先權。+ - * / 所有這四個算術符都是左結合的。運用這個簡單的技術，我們可以消除文法的歧義。

2. 規則部分：規則段由語法規則和包括C代碼的動作組成。規則中目標或非終端符放在左邊，後跟一個冒號（:），然後是產生式的右邊，之後是對應的動作（用{}包含）
3. 代碼部分：該部分是函數部分。當Yacc 解析出錯時，會調用 yyerror()，用户可自定義函數的實現。

這裏我們用一個簡單的例子通過 Yacc 和 Lex 來實現一個簡單的 SQL 解析器

sql.l 代碼示例

%{
#include <stdio.h>
#include <string.h>
#include "struct.h"
#include "sql.tab.h"
int numerorighe=0;
%}
%option noyywrap
%%
select                     return SELECT;
from                       return FROM;
where                      return WHERE;
and                        return AND;
or                         return OR;
[*]                        return *yytext;
[,]                        return *yytext;
[=]                        return *yytext;
[<]                        return *yytext;
[>]                        return *yytext;
[a-zA-Z][a-zA-Z0-9]*       {yylval.Mystr=strdup(yytext);return IDENTIFIER;}
[0-9]+                     return CONST;
\n                         {++yylval.numerorighe; return NL;}
[ \t]+                     /* ignore whitespace */

%%

sql.y 部分代碼示例

%{

%}

%token <numerorighe> NL
%token <Mystr> IDENTIFIER CONST '<' '>' '=' '*'
%token SELECT FROM WHERE AND OR
%type <Mystr> identifiers cond compare op

%%

lines:
    line
    | lines line
    | lines error
    ;
line: 
    select identifiers FROM identifiers WHERE cond NL 
    {
        ptr=putsymb($2,$4,$7);
    }
    ;
    
identifiers:
    '*' {$$="ALL";}
    | IDENTIFIER {$$=$1;}
    | IDENTIFIER','identifiers
        {
            char* s = malloc(sizeof(char)*(strlen($1)+strlen($3)+1));
            strcpy(s,$1);
            strcat(s," ");
            strcat(s,$3); $$=s;
        }
     ;
  
select: 
    SELECT
    ;

cond: 
    IDENTIFIER op compare
    | IDENTIFIER op compare conn cond;

compare: 
    IDENTIFIER
    | CONST
    ;

op:      
    '<'
    |'='
    |'>'
    ;

conn:   
    AND
    | OR
    ;
%%

# 此處由於編譯過程較為繁瑣，此處僅為大家展示關鍵結果
# ./parser "select id,name,age from pisaproxy1,pisaproxy2,pisaproxy3 where id > 1 and name = 'dasheng'"

''Row #1 is correct
 columns: id name age
 tables: pisaproxy1 pisaproxy2 pisaproxy3

可以看出通過 Lex 首先將 SQL 解析成 token，然後再由 yacc 做語法解析，根據 .y 中的規則將 column 和 tables 正確解出。

四、Pisa-Proxy SQL 解析實現淺析

在 Pisa-Proxy 中的 SQL 解析器是通過 Grmtools 這個工具實現的，Grmtools 是 Rust 實現的 lex 和 yacc 庫。Pisa-Proxy 的 SQL 解析主要包含兩部分內容，首先是 lex.rs 文件，這個文件是通過 Grmtools 提供的方法實現的手寫詞法分析器，如前文提到，這個模塊將 SQL 語句進行分詞，生成 token。然後是 grammar.y 文件，該文件中描述了 SQL 語句的推導過程，Grmtools 會通過該文件進行語法分析最終生成 SQL AST。

五、總結

本篇文章主要分享了編譯器的相關概念和一些原理，我們可以瞭解到 SQL 解析器對於 SQL 語句的意義是什麼，以及如何將 SQL 語句字符串形式轉化成我們需要的抽象語法樹。Lex 和 Yacc 是兩個非常強大的工具，他可以幫助開發者方便快捷地實現自己的解析器，但是編譯原理包羅萬象也是非常複雜的一門學科。Pisa-Proxy 的 SQL 解析器在實現過程中也遇到很多問題，比如如何解決衝突，二義性，優先級等等問題。後面會繼續有文章深度剖析 SQL 語句在 Rust 中的具體實現，本文就不再贅敍述。

六. 相關鏈接：

6.1 Pisanix:

項目地址：https://github.com/database-mesh/pisanix

官網地址：Hello from Pisanix | Pisanix

Database Mesh：https://www.database-mesh.io/

SphereEx 官網：https://www.sphere-ex.com

6.2 社區

開源項目千萬步，Pisanix 才剛起步。開源是一扇門，Pisanix 歡迎各位小夥伴一起參與進來，發表自己的想法，分享自己的見解，不管是代碼還是文檔，issue 還是 pull request，社區一樣歡迎。各位樂意幫助數據庫治理的小夥伴們，讓我們一起來建設 Pisanix 社區吧~

目前 Pisanix 社區每兩週都會組織線上討論，詳細安排如下，我們等你~

七、參考資料

1. 《編譯原理》
2. 《現代編譯原理》
3. https://github.com/mysql/mysql-server/blob/8.0/sql/sql_yacc.yy
4. http://web.stanford.edu/class/archive/cs/cs143/cs143.1128/